The Spine of Pascal’s Triangle

We are all familiar with Pascal’s Triangle, also known as the Arithmetic Triangle (AT). Each entry in the AT is the sum of the two closest entries in the row above it. The ${k}$ -th entry in row ${n}$ is the binomial coefficient ${\binom{n}{k}}$ (read ${n}$ -choose- ${k}$ ), the number of ways of selecting ${k}$ elements from a set of ${n}$ distinct elements.

We can represent the AT as follows:

The Spine of the Triangle

The AT has an endless variety of curious and interesting properties. Here we focus on the central column, or spine, of the triangle, with entries

$\displaystyle \binom{0}{0}, \binom{2}{1}, \binom{4}{2}, \binom{6}{3}, \binom{8}{4}, \dots \binom{2n}{n}, \dots$

or, in numerical terms,

$\displaystyle 1, 2, 6, 20, 70, \dots , (2n)!/(n!)^2, \dots \,.$

The entries in this sequence are the central binomial coefficients, and ${\binom{2n}{n}}$ is the coefficient of ${x^n}$ in the binomial expansion of ${(1+x)^{2n}}$ .

The quantity ${\binom{2n}{n}}$ is the number of ways of dividing a set of ${2n}$ elements into two subsets of equal size. If we have a class of 8 students, we can separate them into two groups of 4 in ${\binom{8}{4} = 70}$ different ways.

It is a simple matter to show that

$\displaystyle \binom{2n+2}{n+1} = \frac{2(2n+1)}{n+1}\binom{2n}{n}$

This implies that, for large ${n}$ ,

$\displaystyle \binom{2n+2}{n+1} \approx 4\times\binom{2n}{n}$

showing that the terms increase in magnitude exponentially, becoming four times larger with each step. With 12 students there are close to 1000 different divisions into two equal groups. With a class of 24 students, there are more than 2.7 million.

Here is another application: suppose you are in Manhattan and wish to walk to a point 8 streets north and 8 avenues East, always walking either Northward or Eastward. Or think of a chessboard, but focus on the edges of squares rather than the interiors. There are ${\binom{16}{8} = 12,870}$ different possible advancing routes from the bottom-left corner to the top-right corner. This can easily be explained: at each junction you must choose North or East, and there must be 8 eastward and 8 northward segments in the route.

Numerical Evaluation of the Coefficients

Upper and lower bounds on the central binomial coefficients can be established without too much difficulty (for details, see Griffiths, 2008, Ch. 2):

$\displaystyle \frac{2^{2n}}{2n} < \binom{2n}{n} < 2^{2n} \quad\mbox{for}\quad n > 1 \,.$

Considering an extreme example, let us take ${n=500}$ . The lower and upper bounds are

$\displaystyle \frac{2^{1000}}{1000} \approx 1.7\times 10^{298} \quad\mbox{and}\quad 2^{1000} \approx 1.7\times 10^{301} \,.$

My calculator gives the value ${\binom{1000}{500} \approx 2.7\times 10^{299}}$ , sitting snugly between the bounds. But eventually the calculator will suffer an overflow.

We can derive integral expressions for the coefficients:

$\displaystyle \binom{2n}{n} = \frac{2^{2n}}{\pi} \int_0^{\pi/2} \sin^{2n}\theta\,\mathrm{d}\theta = \frac{2^{2n}}{\pi} \int_0^{\infty}\frac{\mathrm{d}x}{(1+x^2)^{n+1}} \,.$

For details, see Griffiths (2008, Ch. 5). More results can be found in that book.

Stirling’s Formula for the factorial is

$\displaystyle n! \approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n} \,.$

We can use this in the definition of the binomial coefficients to get the asymptotic expression

$\displaystyle \binom{2n}{n} \equiv \frac{(2n)!}{(n!)^2} \approx \sqrt{\frac{1}{\pi n}}\cdot 2^{2n}$

It is clear that this is between the lower and upper bounds given above. In the following table, we give a selection of exact and approximate values of the central binomial coefficients ${\binom{2n}{n}}$ .These values are close enough for many purposes but, if greater accuracy is required, Stirling’s asymptotic formula with more terms can be used.

One final result: the central binomial coefficients can be generated as the coefficients of the expansion in powers of ${x}$ of a simple function, the generating function ${G(x)}$ :

$\displaystyle G(x) \equiv \frac{1}{\sqrt{1-4x}} = \sum_0^\infty \binom{2n}{n} x^n \,.$

The story continues with the Catalan Numbers, but they will have to be left for another day.

Sources

${\bullet}$ Griffiths, 2008: The Backbone of Pascal’s Triangle. Excursions on Mathematics, Vol 1. United Kingdom Mathematics Trust. 163pp. ISBN: 978-1-9060-0104-9.

ThatsMaths