Pascal's triangle

Each entry is the sum of the two entries above it.

The Pascal's (or Pascal's ) triangle is a form of graphical representation of the binomial coefficients , which also allows a simple calculation of these. They are arranged in a triangle in such a way that each entry is the sum of the two entries above it. This fact is represented by the equation ${\ displaystyle {\ tbinom {n} {k}}}$

${\ displaystyle {\ binom {n + 1} {k + 1}} = {\ binom {n} {k}} + {\ binom {n} {k + 1}}}$

described. The variable can be interpreted as a row index and a column index, whereby the count starts with zero (i.e. first row , first column ). If you start at the margins with entries with the value , then exactly the binomial coefficients result. ${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle n = 0}$${\ displaystyle k = 0}$${\ displaystyle 1}$

 ${\ displaystyle {\ begin {pmatrix} 0 \\ 0 \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} 1 \\ 0 \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} 1 \\ 1 \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} 2 \\ 0 \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} 2 \\ 1 \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} 2 \\ 2 \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} 3 \\ 0 \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} 3 \\ 1 \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} 3 \\ 2 \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} 3 \\ 3 \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} 4 \\ 0 \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} 4 \\ 1 \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} 4 \\ 2 \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} 4 \\ 3 \ end {pmatrix}}}$ ${\ displaystyle {\ begin {pmatrix} 4 \\ 4 \ end {pmatrix}}}$

The name goes back to Blaise Pascal . The Pascal triangle was known earlier and is therefore still named after other mathematicians today. In China one speaks of the Yang-Hui triangle (after Yang Hui ), in Italy of the Tartaglia triangle (after Nicolo Tartaglia ) and in Iran of the Chayyām triangle (after Omar Chayyām ).

history

Yang-Hui triangle, as described in a book by Zhu Shijie from 1303.
Blaise Pascal's version of the right triangle

The earliest detailed representation of a triangle of binomial coefficients appeared in the 10th century in Commentaries on Chandas Shastra , an Indian book on the prosody of Sanskrit written by Pingala between the fifth and second centuries BC. While Pingala's work was only preserved in fragments, the commentator Halayudha used the triangle around 975 to establish dubious relationships with Meru-prastaara, the "steps of Mount Meru ". It was also known that the sum of the flat diagonals of the triangle gives the Fibonacci numbers. The first 17 lines of the triangle have come down to us from the Indian mathematician Bhattotpala (approx. 1068).

Almost at the same time, the Pascal triangle in the Middle East was treated by al-Karaji (953-1029), as-Samaw'al and Omar Chayyām and is therefore known as the Chayyām triangle in present-day Iran . Various mathematical theorems related to the triangle were known, including the binomial theorem . In fact, it is fairly certain that Chayyām used a method of calculating the -th root based on binomial expansion and hence binomial coefficients. ${\ displaystyle n}$

The earliest Chinese representation of an arithmetic triangle identical to Pascal's triangle can be found in Yang Hui's book Xiangjie Jiuzhang Suanfa from 1261, parts of which have been preserved in the Yongle encyclopedia . Yang writes in it that he has adopted the triangle from Jia Xian (around 1050) and his li cheng shi shuo ("Determination of coefficients using a diagram") method for calculating square and cube roots.

Peter Apian published the triangle in 1531/32 on the cover picture of his book on trade calculations, the earlier version of which from 1527 represents the first written evidence of Pascal's triangle in Europe.

In 1655 Blaise Pascal wrote the book "Traité du triangle arithmétique" (Treatise on the arithmetic triangle), in which he collected various results relating to the triangle and used them to solve problems of probability theory . The triangle was later named after Pascal by Pierre Rémond de Montmort (1708) and Abraham de Moivre (1730).

application

Pascal's triangle provides a means of quickly multiplying arbitrary powers of binomials . The second line ( ) contains the coefficients 1, 2, 1 of the first two binomial formulas : ${\ displaystyle n = 2}$

${\ displaystyle (a \ pm b) ^ {2} = a ^ {2} \ \ pm \ 2 \ cdot from \ + \ b ^ {2}.}$

The next, third line contains the coefficients 1, 3, 3, 1 for : ${\ displaystyle (a \ pm b) ^ {3}}$

${\ displaystyle (a \ pm b) ^ {3} = a ^ {3} \ \ pm \ 3 \ cdot a ^ {2} b ^ {1} \ + \ 3 \ cdot a ^ {1} b ^ { 2} \ \ pm \ b ^ {3}.}$

This list can be continued indefinitely, whereby it should be noted that for the binomial always the minus sign is to be taken from " " and that while the exponent of always decreases by 1 in every formula, the exponent of increases by 1. The binomial theorem provides a generalization . ${\ displaystyle (ab)}$${\ displaystyle \ pm}$${\ displaystyle a}$${\ displaystyle b}$

Furthermore, when Pascal's triangle is applied to the binomial, the signs - and + alternate with any exponent (there is always a minus if the exponent is odd). That means z. B. ${\ displaystyle (ab)}$${\ displaystyle b}$

${\ displaystyle (ab) ^ {4} = a ^ {4} \ - \ 4 \ times a ^ {3} b ^ {1} \ + \ 6 \ times a ^ {2} b ^ {2} \ - \ 4 \ cdot a ^ {1} b ^ {3} \ + \ b ^ {4}.}$

A two-dimensional generalization is the trinomial triangle , in which every number is the sum of three (instead of two in Pascal's triangle ) entries. The Pascal pyramid is an extension into the third dimension .

Consequences in Pascal's triangle

Many well-known sequences of numbers can be found in Pascal's triangle.

The diagonals

The first diagonal contains only ones and the second diagonal the sequence of natural numbers. The third diagonal contains the triangular numbers and the fourth the tetrahedral numbers . Generally one finds the regular figured numbers of the order in the -th diagonal . In each diagonal there is the sequence of the partial sums to the sequence that is on the diagonal above. Conversely, every diagonal sequence is the difference sequence to the sequence below in the diagonal. ${\ displaystyle r}$${\ displaystyle r}$

So generally applies to the triangular numbers

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

for the tetrahedral numbers

${\ displaystyle T (n) = \ sum _ {k = 1} ^ {n} \ Delta (k) = {\ binom {n + 2} {3}}}$

and for the regular figured numbers of the order ${\ displaystyle r}$

${\ displaystyle R (r, n) = \ sum _ {k = 1} ^ {n} R (r-1, k) = {\ binom {n + r-1} {r}}}$.

The Fibonacci Numbers

Alternative representation: The Fibonacci numbers as the sum of the diagonals (red lines).
 ${\ displaystyle 1}$ ${\ displaystyle 1}$ ${\ displaystyle 1}$ ${\ displaystyle 1}$ ${\ displaystyle 2}$ ${\ displaystyle 1}$ ${\ displaystyle \ color {OliveGreen} 1}$ ${\ displaystyle 3}$ ${\ displaystyle 3}$ ${\ displaystyle 1}$ ${\ displaystyle \ color {blue} 1}$ ${\ displaystyle \ color {red} 4}$ ${\ displaystyle \ color {OliveGreen} 6}$ ${\ displaystyle 4}$ ${\ displaystyle 1}$ ${\ displaystyle 1}$ ${\ displaystyle 5}$ ${\ displaystyle \ color {blue} 10}$ ${\ displaystyle \ color {red} 10}$ ${\ displaystyle \ color {OliveGreen} 5}$ ${\ displaystyle 1}$ ${\ displaystyle 1}$ ${\ displaystyle 6}$ ${\ displaystyle 15}$ ${\ displaystyle 20}$ ${\ displaystyle \ color {blue} 15}$ ${\ displaystyle \ color {red} 6}$ ${\ displaystyle \ color {OliveGreen} 1}$ ${\ displaystyle 1}$ ${\ displaystyle 7}$ ${\ displaystyle 21}$ ${\ displaystyle 35}$ ${\ displaystyle 35}$ ${\ displaystyle 21}$ ${\ displaystyle \ color {blue} 7}$ ${\ displaystyle \ color {red} 1}$ ${\ displaystyle 1}$ ${\ displaystyle 8}$ ${\ displaystyle 28}$ ${\ displaystyle 56}$ ${\ displaystyle 70}$ ${\ displaystyle 56}$ ${\ displaystyle 28}$ ${\ displaystyle 8}$ ${\ displaystyle \ color {blue} 1}$ ${\ displaystyle 1}$ ${\ displaystyle 9}$ ${\ displaystyle 36}$ ${\ displaystyle 84}$ ${\ displaystyle 126}$ ${\ displaystyle 126}$ ${\ displaystyle 84}$ ${\ displaystyle 36}$ ${\ displaystyle 9}$ ${\ displaystyle 1}$ ${\ displaystyle 1}$ ${\ displaystyle 10}$ ${\ displaystyle 45}$ ${\ displaystyle 120}$ ${\ displaystyle 210}$ ${\ displaystyle 252}$ ${\ displaystyle 210}$ ${\ displaystyle 120}$ ${\ displaystyle 45}$ ${\ displaystyle 10}$ ${\ displaystyle 1}$

The sums of the flat "diagonals" marked here in green, red and blue each result in a Fibonacci number (1, 1, 2, 3, 5, 8, 13, 21, 34, ...). In this example the sum of the green diagonal equals 13, the sum of the red diagonal equals 21, the sum of the blue diagonal equals 34. That the "diagonal" sometimes cannot be "drawn through" from one end to the other, as in the case of the red diagonal, does not matter.

So generally applies

${\ displaystyle F (n) = \ sum _ {k = 0} ^ {\ lfloor {\ frac {n} {2}} \ rfloor} {\ binom {nk-1} {k}} = \ sum _ { k = 0} ^ {\ lfloor {\ frac {n} {2}} \ rfloor} {\ binom {nk-1} {n-2k-1}}, n \ geq 1}$

The lines

The total of the entries in a line is called the line total. From top to bottom, the line totals double from line to line. This comes from the law of formation of Pascal's triangle. Each entry in a line is used in the following line to calculate two entries. Here you have to generalize the formation law by adding imaginary zeros to the left and right of each line, so that the outer ones of each line are also generated by adding the entries above. Since the line total of the first line is equal to one, the line total of the -th line is equal . This corresponds to the following law for binomial coefficients: ${\ displaystyle n}$${\ displaystyle 2 ^ {n-1}}$

${\ displaystyle \ sum _ {k = 0} ^ {n} {\ binom {n} {k}} = {\ binom {n} {0}} + {\ binom {n} {1}} + \ dotsb + {\ binom {n} {n}} = 2 ^ {n}}$

If you put the digits of the first five lines of Pascal's triangle next to one another, you get the first powers of 11 with 1, 11, 121, 1331 and 14641.

The alternating sum of each row is zero: , . ${\ displaystyle \ sum _ {k = 0} ^ {n} (- 1) ^ {k} {\ binom {n} {k}} = 0}$${\ displaystyle n> 0}$

Formally, the three above formulas follow from the binomial theorem for , and . ${\ displaystyle (1 + x) ^ {n} = \ sum _ {k = 0} ^ {n} {\ binom {n} {k}} x ^ {k}}$${\ displaystyle x = 1}$${\ displaystyle x = 10}$${\ displaystyle x = -1}$

Mean binomial coefficients

The sequence of mean binomial coefficients begins with 1, 2, 6, 20, 70, 252, ... (sequence A000984 in OEIS ).

Connection with the Sierpinski triangle

Pascal's triangle is related to the Sierpinski triangle , which was named in 1915 after the Polish mathematician Wacław Sierpiński . Both triangles use a simple but slightly different iteration rule , which produces a geometric similarity .

Powers with any base

For powers with any base there is a different kind of triangle:

${\ displaystyle {\ begin {matrix} _ {i} \ backslash ^ {j} & {n \ choose 1} & {n \ choose 2} & {n \ choose 3} & {n \ choose 4} & {n \ choose 5} \\ n ^ {1} & 1 &&&& \\ n ^ {2} & 1 & 2 &&& \\ n ^ {3} & 1 & 6 & 6 && \\ n ^ {4} & 1 & 14 & 36 & 24 & \\ n ^ {5} & 1 & 30 & 150 & 240 & 120 \ end {matrix}} }$

This triangular matrix is ​​obtained by inverting the matrix of the coefficients of those terms which represent the combinations without repeating the form for etc. ${\ displaystyle {\ begin {pmatrix} n \\ k \ end {pmatrix}}}$${\ displaystyle k = 1,2,3, \ dots}$

example
${\ displaystyle {\ begin {pmatrix} n \\ 2 \ end {pmatrix}} = {\ frac {n \, (n-1)} {2}} = - 0 {,} 5 \, n + 0 { ,} 5 \, n ^ {2}}$.
${\ displaystyle n ^ {5} = 1 \, {\ begin {pmatrix} n \\ 1 \ end {pmatrix}} + 30 \, {\ begin {pmatrix} n \\ 2 \ end {pmatrix}} + 150 \, {\ begin {pmatrix} n \\ 3 \ end {pmatrix}} + 240 \, {\ begin {pmatrix} n \\ 4 \ end {pmatrix}} + 120 \, {\ begin {pmatrix} n \ \ 5 \ end {pmatrix}}}$
example
${\ displaystyle 6 ^ {5} = 1 \ cdot 6 + 30 \ cdot 15 + 150 \ cdot 20 + 240 \ cdot 15 + 120 \ cdot 6 = 7 \ .776}$

The law of formation of the coefficients for the coefficient in the row and column is: ${\ displaystyle i}$${\ displaystyle j}$

${\ displaystyle E (i, j) = [E (i-1, j-1) + E (i-1, j)] \ cdot j}$

it therefore also applies to the Stirling number . ${\ displaystyle E (i, j) = j! S (i, j)}$ ${\ displaystyle S (i, j)}$

With the help of this triangle one gains direct insights into the divisibility of powers. So every prime power for is congruent modulo . This is essentially the content of Fermat's Little Theorem ; however, it is also shown that the expression is not only divisible by 6 for all , but also for 6. The greatest common divisor of the matrix coefficients from the second coefficient of the prime exponent for always corresponds to the denominator of the respective Bernoulli number (example :: denominator = 6  ;: denominator = 30 etc.) ${\ displaystyle n ^ {p}}$${\ displaystyle p> 3}$${\ displaystyle n}$${\ displaystyle 6p}$${\ displaystyle a ^ {p} -a}$${\ displaystyle a}$${\ displaystyle p}$${\ displaystyle p> 3}$${\ displaystyle n}$${\ displaystyle p = 3}$${\ displaystyle p = 5}$

With this number triangle, for example, you can easily prove that is divisible by 24: ${\ displaystyle \ forall n \ in \ mathbb {N}: n ^ {5} -n ^ {3}}$

${\ displaystyle 0 \ times a + 24 \ times b + 144 \ times c + 240 \ times d + 120 \ times e}$(with , , and so forth.)${\ displaystyle a = {\ begin {pmatrix} n \\ 1 \ end {pmatrix}}}$${\ displaystyle b = {\ begin {pmatrix} n \\ 2 \ end {pmatrix}}}$

is always divisible by 24, because there are also. ${\ displaystyle n \ in \ mathbb {N}}$${\ displaystyle a, b, c, d, e \ in \ mathbb {N}}$

Connection with the Wallis product

In 1655, John Wallis used a chessboard-like interpolation between the figured sequences of numbers (for each dimension) to calculate a representation of 4 / as an infinite product for the first time . ${\ displaystyle \ pi}$

Others

There is the Singmaster conjecture about the numbers with which a number occurs in Pascal's triangle .