Content deleted Content added
Tags: Reverted blanking Visual edit |
Undid revision 1288155245 by 1.187.216.59 (talk) |
||
Line 120:
[[File:pascal_triangle_compositions.svg|thumb|upright=1|The numbers of [[composition (combinatorics)|compositions]] of ''n'' +1 into ''k'' +1 ordered partitions form Pascal's triangle.]]
=== Rows ===
* The sum of the elements of a single row is twice the sum of the row preceding it. For example, row 0 (the topmost row) has a value of 1, row 1 has a value of 2, row 2 has a value of 4, and so forth. This is because every item in a row produces two items in the next row: one left and one right. The sum of the elements of row <math> n</math> equals to <math> 2^n</math>.
*Taking the product of the elements in each row, the sequence of products {{OEIS|id=A001142}} is related to the base of the natural logarithm, ''[[E (mathematical constant)|e]]''.<ref>{{citation
| last = Brothers | first = H. J.
| doi = 10.4169/math.mag.85.1.51
| journal = [[Mathematics Magazine]]
| pages = 51
| title = Finding e in Pascal's triangle
| volume = 85
| year = 2012| issue = 1
| s2cid = 218541210
}}.</ref><ref>{{citation
| last = Brothers | first = H. J.
| doi =10.1017/S0025557200004204
| journal = [[The Mathematical Gazette]]
| pages = 145–148
| title = Pascal's triangle: The hidden stor-''e''
| volume = 96
| year = 2012| issue = 535
| s2cid = 233356674
}}.</ref> Specifically, define the sequence <math> s_{n}</math> for all <math>n \ge 0</math> as follows: <math>s_{n} = \prod_{k = 0}^{n} {n \choose k} = \prod_{k = 0}^{n} \frac{n!}{k!(n-k)!}</math> {{pb}} Then, the ratio of successive row products is <math display="block">\frac{s_{n+1}}{s_{n}} =
\frac{ \displaystyle (n+1)!^{n+2} \prod_{k = 0}^{n + 1} \frac{1}{k!^2}}{\displaystyle n!^{n+1}\prod_{k=0}^{n}{\frac{1}{k!^2}}} = \frac{(n + 1)^n}{n!}</math> and the ratio of these ratios is <math display="block">\frac{s_{n + 1} \cdot s_{n - 1}}{s_{n}^{2}} =
\left( \frac{n + 1}{n} \right)^n, ~ n\ge 1.</math> The right-hand side of the above equation takes the form of the limit definition of [[e (mathematical constant)|<math>e</math>]] <math display="block">e =\lim_{n \to \infty} \left( 1 + \frac{1}{n} \right)^{n}.</math>
* [[pi|<math>\pi</math>]] can be found in Pascal's triangle by use of the [[Nilakantha Somayaji|Nilakantha]] infinite series.<ref>{{citation
| last = Foster | first = T.
| doi = 10.5951/mathteacher.108.4.0246
| journal = [[Mathematics Teacher]]
| pages = 247
| title = Nilakantha's Footprints in Pascal's Triangle
| volume = 108
| year = 2014}}</ref> <math display="block">\pi = 3 + \sum_{n = 1}^{\infty} (-1)^{n + 1} \frac{{2n + 1 \choose 1}}{{2n + 1 \choose 2}{2n + 2 \choose 2}}</math>
* Some of the numbers in Pascal's triangle correlate to numbers in [[Lozanić's triangle]].
* The sum of the squares of the elements of row {{mvar|n}} equals the middle element of row {{math|2''n''}}. For example, {{math|1=1<sup>2</sup> + 4<sup>2</sup> + 6<sup>2</sup> + 4<sup>2</sup> + 1<sup>2</sup> = 70}}. In general form, <math display="block">\sum_{k=0}^n {n \choose k}^2 = {2n \choose n}.</math>
* In any even row <math>n=2m</math>, the middle term minus the term two spots to the left equals a [[Catalan number]], specifically <math>C_{m-1} = \tbinom{2m}{m} - \tbinom{2m}{m-2}</math>. For example, in row 4, which is 1, 4, 6, 4, 1, we get the 3rd Catalan number <math>C_3 = 6-1 = 5 </math>.
* In a row {{mvar|p}}, where {{mvar|p}} is a [[prime number]], all the terms in that row except the 1s are divisible by {{mvar|p}}. This can be proven easily, from the multiplicative formula <math>\tbinom pk = \tfrac{p!}{k!(p-k)!} </math>. Since the denominator <math>k!(p-k)!</math> can have no prime factors equal to {{mvar|p}}, so {{mvar|p}} remains in the numerator after integer division, making the entire entry a multiple of {{mvar|p}}.<!--
[[Image:Exp binomial grey.svg|thumb|upright=1.25|left|Binomial matrix as matrix exponential (illustration for 5×5 matrices). All the dots represent 0.]] Comment: picture hidded since useless rescaling, also wrong paragraph for the pic -->
* ''Parity'': To count [[odd number|odd]] terms in row {{mvar|n}}, convert {{mvar|n}} to [[binary numeral system|binary]]. Let {{mvar|x}} be the number of 1s in the binary representation. Then the number of odd terms will be {{math|2<sup>''x''</sup>}}. These numbers are the values in [[Gould's sequence]].<ref>{{citation
| last = Fine | first = N. J.
| doi = 10.2307/2304500
| journal = [[American Mathematical Monthly]]
| mr = 0023257
| pages = 589–592
| title = Binomial coefficients modulo a prime
| volume = 54
| issue = 10
| year = 1947| jstor = 2304500
}}. See in particular Theorem 2, which gives a generalization of this fact for all prime moduli.</ref>
* Every entry in row 2<sup>''n''</sup> − 1, ''n'' ≥ 0, is odd.<ref>{{citation
| last = Hinz | first = Andreas M.
| doi = 10.2307/2324061
| issue = 6
| journal = The American Mathematical Monthly
| mr = 1166003
| pages = 538–544
| title = Pascal's triangle and the Tower of Hanoi
| volume = 99
| year = 1992| jstor = 2324061
}}. Hinz attributes this observation to an 1891 book by [[Édouard Lucas]], ''Théorie des nombres'' (p. 420).</ref>
*''Polarity'': When the elements of a row of Pascal's triangle are alternately added and subtracted together, the result is 0. For example, row 6 is 1, 6, 15, 20, 15, 6, 1, so the formula is 1 − 6 + 15 − 20 + 15 − 6 + 1 = 0.
=== Diagonals ===
[[File:Pascal_triangle_simplex_numbers.svg|thumb|upright=1.25|Derivation of [[simplex]] numbers from a left-justified Pascal's triangle]]
The diagonals of Pascal's triangle contain the [[Figurate numbers#Triangular numbers and their analogs in higher dimensions|figurate numbers]] of simplices:
* The diagonals going along the left and right edges contain only 1's.
* The diagonals next to the edge diagonals contain the [[natural number]]s in order. The 1-dimensional simplex numbers increment by 1 as the line segments extend to the next whole number along the number line.
* Moving inwards, the next pair of diagonals contain the [[triangular number]]s in order.
* The next pair of diagonals contain the [[tetrahedral number]]s in order, and the next pair give [[pentatope number]]s.
::<math>\begin{align}
P_0(n) &= P_d(0) = 1, \\
P_d(n) &= P_d(n-1) + P_{d-1}(n) \\
&= \sum_{i=0}^n P_{d-1}(i) = \sum_{i=0}^d P_i(n-1).
\end{align}</math>
The symmetry of the triangle implies that the ''n''<sup>th</sup> d-dimensional number is equal to the ''d''<sup>th</sup> ''n''-dimensional number.
An alternative formula that does not involve recursion is
<math display="block">P_d(n)=\frac{1}{d!}\prod_{k=0}^{d-1} (n+k) = {n^{(d)}\over d!} = \binom{n+d-1}{d},</math>
where ''n''<sup>(''d'')</sup> is the [[rising factorial]].
The geometric meaning of a function ''P''<sub>''d''</sub> is: ''P''<sub>''d''</sub>(1) = 1 for all ''d''. Construct a ''d''-[[dimensional]] triangle (a 3-dimensional [[triangle]] is a [[tetrahedron]]) by placing additional dots below an initial dot, corresponding to ''P''<sub>''d''</sub>(1) = 1. Place these dots in a manner analogous to the placement of numbers in Pascal's triangle. To find P<sub>''d''</sub>(''x''), have a total of ''x'' dots composing the target shape. P<sub>''d''</sub>(''x'') then equals the total number of dots in the shape. A 0-dimensional triangle is a point and a 1-dimensional triangle is simply a line, and therefore ''P''<sub>0</sub>(''x'') = 1 and ''P''<sub>1</sub>(''x'') = ''x'', which is the sequence of natural numbers. The number of dots in each layer corresponds to ''P''<sub>''d'' − 1</sub>(''x'').
=== Calculating a row or diagonal by itself ===
There are simple algorithms to compute all the elements in a row or diagonal without computing other elements or factorials.
To compute row <math>n</math> with the elements <math>\tbinom{n}{0}, \tbinom{n}{1}, \ldots, \tbinom{n}{n}</math>, begin with <math>\tbinom{n}{0}=1</math>. For each subsequent element, the value is determined by multiplying the previous value by a fraction with slowly changing numerator and denominator:
:<math> {n\choose k}= {n\choose k-1}\times \frac{n+1-k}{k}.</math>
For example, to calculate row 5, the fractions are <math>\tfrac{5}{1}</math>, <math>\tfrac{4}{2}</math>, <math>\tfrac{3}{3}</math>, <math>\tfrac{2}{4}</math> and <math>\tfrac{1}{5}</math>, and hence the elements are <math>\tbinom{5}{0}=1</math>, <math>\tbinom{5}{1}=1\times\tfrac{5}{1}=5</math>, <math>\tbinom{5}{2}=5\times\tfrac{4}{2}=10</math>, etc. (The remaining elements are most easily obtained by symmetry.)
To compute the diagonal containing the elements <math>\tbinom{n}{0}, \tbinom{n+1}{1}, \tbinom{n+2}{2},\ldots,</math> begin again with <math>\tbinom{n}{0} = 1</math> and obtain subsequent elements by multiplication by certain fractions:
| |||