This site is supported by donations to The OEIS Foundation.

Pascal triangle

From OeisWiki

(Redirected from (1,1)-Pascal triangle)
Jump to: navigation, search

Pascal's triangle is a geometric arrangement of numbers produced recursively which generates the binomial coefficients.[1] It is named after the French mathematician Blaise Pascal (who studied it in the 17th 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)
[2]
\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^{(2)}_{3}(n-1) \,, the \scriptstyle (n-1) \,th triangular number.

Contents

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[1]

\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 \ge 0, \,[3][1]

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 \,\ge\, 0 \,, member of the \scriptstyle n \,th, \scriptstyle n \,\ge\, 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 \,\ge\, 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.[4]

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 \,\ge\, 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 [2]
\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 \,\ge\, 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 \,\ge\, 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,[5] 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 3rd 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 \ge 0. \,

Similarly, in the 3rd 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 \ge 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 0th 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 \ge 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 \ge 1  \,
T_{(1,1)}(2m, m) = \binom{2m}{m} = \frac{(2m)!}{(m!)^2} = (m+1) C_m,\quad m \ge 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 \,\ge\, 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.)



Notes

  1. 1.0 1.1 1.2 Eric W. Weisstein, Binomial Coefficient, from MathWorld..
  2. 2.0 2.1 Eric W. Weisstein, Figurate Number Triangle, from MathWorld..
  3. www.vaxasoftware.com, Newton's binomial theorem and Pascal-Tartaglia's triangle.
  4. Eric W. Weisstein, Polyhedral Formula, from MathWorld..
  5. Eric W. Weisstein, Simplex, from MathWorld..

External links

Personal tools