Pascal's triangle: Difference between revisions

Revision as of 07:51, 25 October 2007

The Pascal's triangle is a convenient tabular presentation for the binomial coefficients. Already known in the 11th century^[1], it was adopted in Western world under this name after Blaise Pascal published his Traité du triangle arithmétique ("Treatise on the Arithmetical Triangle") in 1654.

For instance, we can use Pascal's triangle to compute the binomial expansion of

(x+y)^{4}=1\times a^{4}+4\times a^{3}b+6\times a^{2}b^{2}+4\times ab^{3}+1\times b^{4}~

The coefficients 1, 4, 6, 4, 1 appear directly in the triangle.

${\begin{matrix}&&&&&1\\&&&&1&&1\\&&&1&&2&&1\\&&1&&3&&3&&1\\&1&&4&&6&&4&&1\\&&&&&\cdots \end{matrix}}$

Each coefficient in the triangle is the sum of the two coefficients over it^[2]. For instance, $6=3+3$ . The binomial coefficients relate to this construction by Pascal's rule, which states that if

{n \choose k}={\frac {n!}{k!(n-k)!}}

is the kth binomial coefficient in the binomial expansion of (x+y)ⁿ, then

{n \choose k}={n-1 \choose k-1}+{n-1 \choose k}

for any nonnegative integer n and any integer k between 0 and n.^[3]

Those coefficients have applications in algebra and in probabilities. From the triangle, we can equally compute the Fibonacci numbers and create the Sierpinski triangle. After studying it, Isaac Newton expanded it and found new methods to extract the square root and to calculate the natural logarithm of a number.

Properties

In order to ease the understanding of some properties, the triangle should be presented differently :

${\begin{array}{cccccccc}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\\...&...&...&...&...&...&...&...\\\end{array}}$

Each coefficient is the sum of the coefficient exactly over it and the other to its left. For instance, $3+3=6$ .

Let's call this rule the "addition rule"^[2].

Using this format, it is easy to apply an index to each row :

${\begin{array}{lcccccccc}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\\...&...&...&...&...&...&...&...&...\\\end{array}}$

Starting the indices at zero facilitates many calculations.

The sum of any row is $2^{r}~$ , with $r~$ being the row index : $0,1,2,\ldots ~$ For instance, the sum of row 4 is $1+4+6+4+1=16=2^{4}~$ .

Since there is a formula for summing a row, then maybe there is one for a column ? It is the case. Again, we index the triangle, but this time it will be the columns :

${\begin{array}{lcccccccc}&0&1&2&3&4&5&6&7\\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\\...&...&...&...&...&...&...&...&...\\\end{array}}$

Anyone familiar with the factorial function can easily find the general formula. The sum of a column $c~$ ending at row $r~$ is

{\frac {(r+1)\times r\,\times \cdots \times (r-c+1)}{(c+1)!}}{\text{ with }}r,c\in \mathbb {N} ^{*}

.

There is another method to compute this sum, see ^[4].

Up until now, we added along the rows and the columns. We can add along the diagonals. Adding from left to right gives :

${\begin{array}{ccccccccccr}1&&&&&&&&&=&1\\1&&&&&&&&&=&1\\1&+&1&&&&&&&=&2\\1&+&2&&&&&&&=&3\\1&+&3&+&1&&&&&=&5\\1&+&4&+&3&&&&&=&8\\1&+&5&+&6&+&1&&&=&13\\1&+&6&+&10&+&4&+&1&=&21\\...&&&&&&&&&=&...\\\end{array}}$

The numbers on the rigth are the Fibonacci numbers.

References

↑ Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji, School of Mathematics and Statistics, University of St Andrews. Consulted 2005-09-03.
↑ ^2.0 ^2.1 This rule does not apply to the ones bordering the triangle. We just insert them.
↑ By convention, the binomial coefficient $\scriptstyle {n \choose k}$ is set to zero if k is either less than zero or greater than n.
↑ Suppose we wish to add the terms in row 3, i.e. the fourth column, until row 6 ( $1+4+10+20=35~$ ). The sum is given by multiplying four terms at numerator, starting at $(r+1)=6+1=7~$ , and four terms at the denominator starting at $(c+1)=(3+1)=4~$ . The sum is equal to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{ 7 \times 6 \times 5 \times 4 }{ 4 \times 3 \times 2 \times 1 } = 35~} . In short, fourth column, four terms at numerator, four terms at denominator, all decreasing.

[1] Abu Bekr ibn Muhammad ibn al-Husayn Al-Karaji, School of Mathematics and Statistics, University of St Andrews. Consulted 2005-09-03.

[not_for_ones-2] 2.0 ^2.1 This rule does not apply to the ones bordering the triangle. We just insert them.

[3] By convention, the binomial coefficient $\scriptstyle {n \choose k}$ is set to zero if k is either less than zero or greater than n.

[4] Suppose we wish to add the terms in row 3, i.e. the fourth column, until row 6 ( $1+4+10+20=35~$ ). The sum is given by multiplying four terms at numerator, starting at $(r+1)=6+1=7~$ , and four terms at the denominator starting at $(c+1)=(3+1)=4~$ . The sum is equal to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{ 7 \times 6 \times 5 \times 4 }{ 4 \times 3 \times 2 \times 1 } = 35~} . In short, fourth column, four terms at numerator, four terms at denominator, all decreasing.

[1]

[2]

[3]

[4]

@@ Line 98: / Line 98: @@
 Anyone familiar with the [[factorial]] function can easily find the general formula. The sum of a column <math>c~</math> ending at row <math>r~</math> is
-:<math>\frac{(r+1)  \times r \, \times \cdots \times (r-c+1)}{(c + 1)!} \text{ with } r, c \in \N^*</math>
+:<math>\frac{(r+1)  \times r \, \times \cdots \times (r-c+1)}{(c + 1)!} \text{ with } r, c \in \N^*</math>.
-There is another method to compute this sum. Suppose we wish to add the terms in row 3, i.e. the fourth column, until row 6 (<math>1 + 4 + 10 + 20 = 35 ~</math>). The sum is given by multiplying four terms at [[numerator]], starting at <math>(r + 1) = 6 + 1 = 7~</math>, and four terms at the [[denominator]] starting at <math>(c + 1) = (3 + 1) = 4~</math>. The sum is equal to <math>\frac{ 7 \times 6 \times 5 \times 4 }{ 4 \times 3 \times 2 \times 1 } = 35~</math>. In short, fourth column, four terms at numerator, four terms at denominator, all decreasing.
+There is another method to compute this sum, see <ref>Suppose we wish to add the terms in row 3, i.e. the fourth column, until row 6 (<math>1 + 4 + 10 + 20 = 35 ~</math>). The sum is given by multiplying four terms at [[numerator]], starting at <math>(r + 1) = 6 + 1 = 7~</math>, and four terms at the [[denominator]] starting at <math>(c + 1) = (3 + 1) = 4~</math>. The sum is equal to <math>\frac{ 7 \times 6 \times 5 \times 4 }{ 4 \times 3 \times 2 \times 1 } = 35~</math>. In short, fourth column, four terms at numerator, four terms at denominator, all decreasing.</ref>.
+Up until now, we added along the rows and the columns. We can add along the diagonals. Adding from left to right gives :
+<math>
+    \begin{array}{ccccccccccr}
+&   &   &   &   &   &   &   &   & = & 1  \\
+&   &   &   &   &   &   &   &   & = & 1  \\
+& + & 1 &   &   &   &   &   &   & = & 2  \\
+& + & 2 &   &   &   &   &   &   & = & 3  \\
+& + & 3 & + & 1 &   &   &   &   & = & 5  \\
+& + & 4 & + & 3 &   &   &   &   & = & 8  \\
+& + & 5 & + & 6 & + & 1 &   &   & = & 13 \\
+& + & 6 & + &10 & + & 4 & + & 1 & = & 21 \\
+       ...&   &   &   &   &   &   &   &   & = &... \\
+    \end{array}
+</math>
+The numbers on the rigth are the [[Fibonacci number]]s.
 == References ==

Pascal's triangle: Difference between revisions

Revision as of 07:51, 25 October 2007

Properties

References

Navigation menu

Search