Pascal triangle

Pascal's triangle is a geometric arrangement of numbers produced recursively which generates the binomial coefficients. It is named after the French mathematician Blaise Pascal (who studied it in the 17^th century) in much of the Western world, although other mathematicians studied it centuries before him in Italy, India, Persia, and China. The triangle is thus known by other names, such as Tartaglia's triangle in Italy and much earlier (c. 500 BC) as the Yanghui triangle in China.

The rectangular version of Pascal's triangle
(Figurate Number Triangle)

$\scriptstyle n\,$ = 0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1
7	1	7	21	35	35	21	7	1
8	1	8	28	56	70	56	28	8	1
9	1	9	36	84	126	126	84	36	9	1
10	1	10	45	120	210	252	210	120	45	10	1
11	1	11	55	165	330	462	462	330	165	55	11	1
12	1	12	66	220	495	792	924	792	495	220	66	12	1
	$\scriptstyle d\,$ = 0	1	2	3	4	5	6	7	8	9	10	11	12

In the equilateral version of Pascal's triangle, we start with a cell (row 0) initialized to 1 in a staggered array of empty (0) cells. We then recursively evaluate the cells as the sum of the two staggered above. The triangle thus grows into an equilateral triangle.

In the rectangular version of Pascal's triangle, we start with a cell (row 0) initialized to 1 in a regular array of empty (0) cells. We then recursively evaluate the cells as the sum of the one above left and the one directly above. The triangle thus grows into a rectangular triangle.

The outermost nonzero cells on each rows are therefore set to 1. All the interior cells are necessarily greater than or equal to 2 and the number of cells from rows 0 to $\scriptstyle n\,$ which are equal to 1 is $\scriptstyle 2n+1\,$ (Cf. A005408) and the number of cells from rows 0 to $\scriptstyle n\,$ which are greater than or equal to 2 is $\scriptstyle P_{3}^{(2)}(n-1)\,$, the $\scriptstyle (n-1)\,$^th triangular number.

Recursion rule

Pascal's triangle recursion rule is

$T(n,0)=T(n,n)=1,\,$

$T(n,d)=T(n-1,d-1)+T(n-1,d),\quad 0<d<n,\,$

or equivalently, using binomial coefficient notation

${\binom {n}{0}}={\binom {n}{n}}=1,\,$

${\binom {n}{d}}={\binom {n-1}{d-1}}+{\binom {n-1}{d}},\quad 0<d<n.\,$

Pascal's triangle and binomial coefficients

Pascal's triangle is a table of binomial coefficients, i.e. the coefficients of the expanded binomial

$(1+x)^{n}=\sum _{d=0}^{n}{\binom {n}{d}}~x^{d}\equiv \sum _{d=0}^{n}{\frac {n!}{d!(n-d)!}}~x^{d}=\sum _{d=0}^{n}T(n,d)~x^{d},\quad n\geq 0,\,$

which is the generating function for the $\scriptstyle n\,$^th row (finite sequence) of Pascal's triangle.

Pascal's triangle rows

$\scriptstyle n\,$ = 0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1
7	1	7	21	35	35	21	7	1
8	1	8	28	56	70	56	28	8	1
9	1	9	36	84	126	126	84	36	9	1
10	1	10	45	120	210	252	210	120	45	10	1
11	1	11	55	165	330	462	462	330	165	55	11	1
12	1	12	66	220	495	792	924	792	495	220	66	12	1
	$\scriptstyle d\,$ = 0	1	2	3	4	5	6	7	8	9	10	11	12

Pascal's triangle rows give an infinite sequence of finite sequences

{{1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}, {1, 4, 6, 4, 1}, {1, 5, 10, 10, 5, 1}, {1, 6, 15, 20, 15, 6, 1}, {1, 7, 21, 35, 35, 21, 7, 1}, {1, 8, 28, 56, 70, 56, 28, 8, 1}, {1, 9, 36, 84, 126, 126, 84, 36, 9, 1}, ...}

The generating function for the $\scriptstyle d\,$^th, $\scriptstyle d\,\geq \,0\,$, member of the $\scriptstyle n\,$^th, $\scriptstyle n\,\geq \,0\,$, subsequence is

$G_{\{T_{(1,1)}(n,d)\}}(x)=(1+x)^{n}\,$

The concatenation of the infinite sequence of finite sequences gives the infinite sequence (Cf. A007318)

{1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1, 1, 6, 15, 20, 15, 6, 1, 1, 7, 21, 35, 35, 21, 7, 1, 1, 8, 28, 56, 70, 56, 28, 8, 1, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1, ...}

The generating function for the $\scriptstyle i\,$^th, $\scriptstyle i\,\geq \,0\,$, member is

$G_{\{T_{(1,1)}(i={\frac {n(n+1)}{2}}+d)\}}(x)=\sum _{n=0}^{\infty }x^{\tfrac {n(n+1)}{2}}~(1+x)^{n}\,$

Pascal's triangle rows sums

The sums of the respective finite sequences give the infinite sequence (Cf. A000079)

{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, ...}

The sum for the $\scriptstyle n\,$^th row gives the powers of 2, $\scriptstyle 2^{n}\,$

$\sum _{d=0}^{n}T(n,d)=\sum _{d=0}^{n}{\binom {n}{d}}=2^{n},\,$

which corresponds to $\scriptstyle (1+x)^{n}\,$ evaluated at $\scriptstyle x\,=\,1.\,$

The generating function is

$G_{\{\sum _{d=0}^{n}T(n,d)\}}(x)=G_{\{2^{n}\}}(x)={\frac {1}{1-2x}}\,$

The partial sums across rows of Pascal's triangle, i.e. partial sums of binomial coefficients, give Bernoulli's triangle.

Pascal's triangle rows alternating sign sums

The alternating sign sums of the respective finite sequences give the infinite sequence (Cf. A000007)

{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...}

The alternating sign sum for the $\scriptstyle n\,$^th row gives the powers of 0, $\scriptstyle 0^{n}\,$ (which equals 1 for $\scriptstyle n\,=\,0\,$ and 0 for $\scriptstyle n\,>\,0)\,$

$\sum _{d=0}^{n}(-1)^{d}\ T(n,d)=\sum _{d=0}^{n}(-1)^{d}~{\binom {n}{d}}=0^{n},\,$

which corresponds to $\scriptstyle (1+x)^{n}\,$ evaluated at $\scriptstyle x\,=\,-1\,$.

The generating function is

$G_{\{\sum _{d=0}^{n}(-1)^{d}\ T(n,d)\}}(x)=G_{\{0^{n}\}}(x)=1\,$

Pascal's triangle rows and Schläfli's (n-1)-dimensional polytopic formula

Schläfli's $\scriptstyle (n-1)\,$-dimensional polytopic formula (for convex polytopes of genus 0) is a generalization of the Descartes-Euler polyhedral formula (for convex polyhedrons of genus 0) to dimensions higher than 3.

The alternate sum for row $\scriptstyle n\,$ of the interior numbers equals the Euler-Poincaré characteristic for convex $\scriptstyle (n-1)\,$-dimensional polytopes of genus 0, e.g.

$\sum _{d=1}^{n-1}(-1)^{d+1}~T(n,d)=\chi _{n-1}(0)=1-(-1)^{n-1},\,$

which is 0 for $\scriptstyle n-1\,$ even and 2 for $\scriptstyle n-1\,$ odd.

If we consider $\scriptstyle d\,=\,0\,$ (the one way of choosing the empty vertex set) and $\scriptstyle d\,=\,n\,$ (the one way of choosing the full vertex set, which is the polytope itself) then we get

$\sum _{d=0}^{n}(-1)^{d+1}~T(n,d)=0^{n},\,$

thus showing that $\scriptstyle \chi _{n-1}(0)\,=\,1-(-1)^{n-1}\,$ is simply the result of not counting the one way of choosing the empty vertex set and the one way of choosing the full vertex set.

Pascal's triangle rows and the number of (d-1)-dimensional elements of the (n-1)-dimensional simplex

The number of $\scriptstyle (d-1)\,$-dimensional elements of the $\scriptstyle (n-1)\,$-dimensional simplex is

${\binom {n-1}{d-1}}=T(n-1,d-1),\,$

where 0-dimensional elements are points, 1-dimensional elements are edges, 2-dimensional elements are faces, ...

Pascal's triangle rows and primes (and prime powers?)

$\scriptstyle n\,$ is prime iff the GCD of all the interior cells of the $\scriptstyle n\,$^th row is $\scriptstyle n\,$.

Actually, it seems that $\scriptstyle n\,$ is a prime power $\scriptstyle p^{\alpha },\,\alpha \,\geq \,1\,$, iff the GCD of all the interior cells of the $\scriptstyle n\,$^th row is $\scriptstyle p\,$, else it is 1. (THIS NEED TO BE CONFIRMED...)

GCD of all the interior cells of the $\scriptstyle n\,$^th row for $\scriptstyle n\,=\,$ 2 to 12

{2, 3, 2, 5, 1, 7, 2, 3, 1, 11, 1, ...} (Cf. A014963$\scriptstyle (n)\,$)

Pascal's (rectangular) triangle columns (or falling diagonals, due to symmetry) and simplicial polytopic numbers

(Symplicial Polytopic) Figurate Number Triangle

$\scriptstyle n\,$ = 0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1
7	1	7	21	35	35	21	7	1
8	1	8	28	56	70	56	28	8	1
9	1	9	36	84	126	126	84	36	9	1
10	1	10	45	120	210	252	210	120	45	10	1
11	1	11	55	165	330	462	462	330	165	55	11	1
12	1	12	66	220	495	792	924	792	495	220	66	12	1
	$\scriptstyle d\,$ = 0	1	2	3	4	5	6	7	8	9	10	11	12

The partial sums of the $\scriptstyle d\,$^th column, $\scriptstyle d\,\geq \,0\,$, build the entries of the $\scriptstyle (d+1)\,$^th column, thus begetting the $\scriptstyle (d+1)\,$-dimensional simplicial polytopic numbers from the $\scriptstyle d\,$-dimensional ones

$\sum _{i=0}^{n}T(i,d)=\sum _{i=d}^{n}T(i,d)=T(n+1,d+1)=\left({\frac {n+1}{d+1}}\right)~T(n,d).\,$

The partial sums of the $\scriptstyle f\,$^th falling diagonal from the right, $\scriptstyle f\,\geq \,0\,$, build the entries of the $\scriptstyle (f+1)\,$^th falling diagonal, thus begetting the $\scriptstyle (d+1)\,$-dimensional simplicial polytopic numbers from the $\scriptstyle f\,$-dimensional ones

$\sum _{i=0}^{n}T(i,n-f)=\sum _{i=f}^{n}T(i,n-f)=T(n+1,n-(f+1))=\left({\frac {n+1}{f+1}}\right)~T(n,n-f).\,$

The $\scriptstyle d\,$^th column gives the $\scriptstyle d\,$-dimensional (the $\scriptstyle f\,$^th falling diagonal from the right gives the $\scriptstyle f\,$-dimensional) simplicial polytopic numbers, forming simplex polytopes, e.g.

d=0, f=0	0-dimensional simplicial numbers	Point numbers	(1 (-1)-cells facets)	(0-simplex)
d=1, f=1	1-dimensional simplicial numbers	Triangular gnomonic numbers	(2 0-cells facets)	(1-simplex)
d=2, f=2	2-dimensional simplicial numbers	Triangular numbers	(3 1-cells facets)	(2-simplex)
d=3, f=3	3-dimensional simplicial numbers	Tetrahedral numbers	(4 2-cells facets)	(3-simplex)
d=4, f=4	4-dimensional simplicial numbers	Pentachoron numbers	(5 3-cells facets)	(4-simplex)
d=5, f=5	5-dimensional simplicial numbers	Hexateron numbers	(6 4-cells facets)	(5-simplex)
d=6, f=6	6-dimensional simplicial numbers	Heptapeton numbers	(7 5-cells facets)	(6-simplex)
d=7, f=7	7-dimensional simplicial numbers	Octahexon numbers	(8 6-cells facets)	(7-simplex)
d=8, f=8	8-dimensional simplicial numbers	Nonahepton numbers	(9 7-cells facets)	(8-simplex)

where (-1)-cells correspond to the empty set, 0-cells are vertices, 1-cells are edges, 2-cells are faces, and so on...

Pascal's (rectangular) triangle third column (d = 2) or falling diagonal from the right (f = 2) and square numbers

In the 3^rd column ($\scriptstyle d\,=\,2\,$,) the sum of 2 stacked cells gives the square numbers

$T(2+j,2)+T(2+j+1,2)=(2+j+2)^{2},\quad j\geq 0.\,$

Similarly, in the 3^rd falling diagonal from the right ($\scriptstyle f\,=\,2\,$,) the sum of 2 stacked cells gives the square numbers

$T(2+j,j)+T(2+j+1,j+1)=(2+j+2)^{2},\quad j\geq 0.\,$

Pascal's (rectangular) triangle rising diagonals and Fibonacci numbers

$\scriptstyle n\,$ = 0	1
1	1	1
2	1	2	1
3	1	3	3	1
4	1	4	6	4	1
5	1	5	10	10	5	1
6	1	6	15	20	15	6	1
7	1	7	21	35	35	21	7	1
8	1	8	28	56	70	56	28	8	1
9	1	9	36	84	126	126	84	36	9	1
10	1	10	45	120	210	252	210	120	45	10	1
11	1	11	55	165	330	462	462	330	165	55	11	1
12	1	12	66	220	495	792	924	792	495	220	66	12	1
	$\scriptstyle d\,$ = 0	1	2	3	4	5	6	7	8	9	10	11	12

The rising diagonals (starting with the 0^th diagonal) give an infinite sequence of finite sequences

{{1}, {1}, {1, 1}, {1, 2}, {1, 3, 1}, {1, 4, 3}, {1, 5, 6, 1}, {1, 6, 10, 4}, {1, 7, 15, 10, 1}, {1, 8, 21, 20, 5}, ... }

whose respective sums give

{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, ...}.

which are the $\scriptstyle k+1\,$^th Fibonacci numbers (Cf. A000045$\scriptstyle (k+1)\,$)

$\sum _{n+d=k}T(n,d)=\sum _{n+d=k}{\binom {n}{d}}=F_{k+1},\quad k\geq 0.\,$

The concatenated infinite sequence of finite sequences gives the infinite sequence (cf. A011973)

{1, 1, 1, 1, 1, 2, 1, 3, 1, 1, 4, 3, 1, 5, 6, 1, 1, 6, 10, 4, 1, 7, 15, 10, 1, 1, 8, 21, 20, 5, 1, 9, 28, 35, 15, 1, 1, 10, 36, 56, 35, 6, ...}

Pascal's triangle central elements

The central (or almost/quasi central for $\scriptstyle n\,$ odd) elements give the sequence (Cf. A001405$\scriptstyle (n)\,$)

{1, 1, 2, 3, 6, 10, 20, 35, 70, 126, 252, 462, 924, 1716, 3432, 6435, 12870, 24310, 48620, 92378, 184756, 352716, 705432, 1352078, 2704156, 5200300, 10400600, 20058300, 40116600, ...}

which is given by the formulae

$T_{(1,1)}(2m-1,m-1)={\binom {2m-1}{m-1}}=T_{(1,1)}(2m-1,m)={\binom {2m-1}{m}}={\frac {T_{(1,1)}(2m,m)}{2}}={\frac {\binom {2m}{m}}{2}},\quad m\geq 1\,$

$T_{(1,1)}(2m,m)={\binom {2m}{m}}={\frac {(2m)!}{(m!)^{2}}}=(m+1)C_{m},\quad m\geq 1\,$

where

$C_{m}={\frac {T_{(1,1)}(2m,m)}{m+1}}={\frac {\binom {2m}{m}}{m+1}}={\frac {(2m)!}{m!(m+1)!}}\,$

is the $\scriptstyle m\,$^th, $\scriptstyle m\,\geq \,0\,$, Catalan number (also called Segner number) (Cf. A000108$\scriptstyle (m)\,$)

{1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, ...}

The generating function is

$G_{\{T_{(1,1)}(n,{\big \lfloor }{\tfrac {n}{2}}{\big \rfloor })\}}(x)=G_{\{T_{(1,1)}(n,{\big \lceil }{\tfrac {n}{2}}{\big \rceil })\}}(x)={\frac {1}{1-x-x^{2}C(x^{2})}}={\frac {1}{{\tfrac {1}{2}}-x+{\sqrt {{\tfrac {1}{4}}-x^{2}}}}},\,$

where $\scriptstyle C(x)\,$ is the generating function of the Catalan numbers

$C(x)={\frac {1-{\sqrt {1-4x}}}{2x}}\,$

Generalizations

Pascal's triangle has higher dimensional generalizations. The three-dimensional version is called Pascal's pyramid or Pascal's tetrahedron, while the general versions are called Pascal's simplices.

See also

• A007188 Multiplicative encoding of Pascal triangle: Product p(i+1)^C(n,i).
• A003590 Rows written as a single base 10 number (the first five terms of that sequence match powers of 11; in general we can say that the first b/2 rows written as a single number give the powers of b + 1 in base b.
• A006046 Total number of odd entries in first n rows of Pascal's triangle.
• A003015 Numbers that appear five or more times in Pascal's triangle (at this point it's not known whether any terms appear exactly five times.)

• (1,1)-Pascal triangle or Pascal's triangle
• (1,2)-Pascal triangle or Lucas triangle
• (1,k)-Pascal triangle
• (2,1)-Pascal triangle
• (k,1)-Pascal triangle
• (a,b)-Pascal triangle
• (a(n),b(n))-Pascal triangle
• Bernoulli's triangle

• Pascal's pyramid or Pascal's tetrahedron
• Pascal's simplices

External links

• Eric W. Weisstein, Pascal's Triangle, from MathWorld..
• Pascal, Blaise, Picture of Pascal's triangle, Traité du triangle arithmétique, 1665.