Misplaced Pages

Pascal's rule

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Combinatorial identity about binomial coefficients Not to be confused with Pascal's law.

In mathematics, Pascal's rule (or Pascal's formula) is a combinatorial identity about binomial coefficients. It states that for positive natural numbers n and k, ( n − 1 k ) + ( n − 1 k − 1 ) = ( n k ) , {\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k},} where ( n k ) {\displaystyle {\tbinom {n}{k}}} is a binomial coefficient; one interpretation of the coefficient of the x term in the expansion of (1 + x). There is no restriction on the relative sizes of n and k, since, if n < k the value of the binomial coefficient is zero and the identity remains valid.

Pascal's rule can also be viewed as a statement that the formula ( x + y ) ! x ! y ! = ( x + y x ) = ( x + y y ) {\displaystyle {\frac {(x+y)!}{x!y!}}={x+y \choose x}={x+y \choose y}} solves the linear two-dimensional difference equation N x , y = N x − 1 , y + N x , y − 1 , N 0 , y = N x , 0 = 1 {\displaystyle N_{x,y}=N_{x-1,y}+N_{x,y-1},\quad N_{0,y}=N_{x,0}=1} over the natural numbers. Thus, Pascal's rule is also a statement about a formula for the numbers appearing in Pascal's triangle.

Pascal's rule can also be generalized to apply to multinomial coefficients.

Combinatorial proof

Illustrates combinatorial proof: ( 4 1 ) + ( 4 2 ) = ( 5 2 ) . {\displaystyle {\binom {4}{1}}+{\binom {4}{2}}={\binom {5}{2}}.}

Pascal's rule has an intuitive combinatorial meaning, that is clearly expressed in this counting proof.

Proof. Recall that ( n k ) {\displaystyle {\tbinom {n}{k}}} equals the number of subsets with k elements from a set with n elements. Suppose one particular element is uniquely labeled X in a set with n elements.

To construct a subset of k elements containing X, include X and choose k − 1 elements from the remaining n − 1 elements in the set. There are ( n − 1 k − 1 ) {\displaystyle {\tbinom {n-1}{k-1}}} such subsets.

To construct a subset of k elements not containing X, choose k elements from the remaining n − 1 elements in the set. There are ( n − 1 k ) {\displaystyle {\tbinom {n-1}{k}}} such subsets.

Every subset of k elements either contains X or not. The total number of subsets with k elements in a set of n elements is the sum of the number of subsets containing X and the number of subsets that do not contain X, ( n − 1 k − 1 ) + ( n − 1 k ) {\displaystyle {\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}} .

This equals ( n k ) {\displaystyle {\tbinom {n}{k}}} ; therefore, ( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) {\displaystyle {\tbinom {n}{k}}={\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}} .

Algebraic proof

Alternatively, the algebraic derivation of the binomial case follows. ( n − 1 k ) + ( n − 1 k − 1 ) = ( n − 1 ) ! k ! ( n − 1 − k ) ! + ( n − 1 ) ! ( k − 1 ) ! ( n − k ) ! = ( n − 1 ) ! [ n − k k ! ( n − k ) ! + k k ! ( n − k ) ! ] = ( n − 1 ) ! n k ! ( n − k ) ! = n ! k ! ( n − k ) ! = ( n k ) . {\displaystyle {\begin{aligned}{n-1 \choose k}+{n-1 \choose k-1}&={\frac {(n-1)!}{k!(n-1-k)!}}+{\frac {(n-1)!}{(k-1)!(n-k)!}}\\&=(n-1)!\left\\&=(n-1)!{\frac {n}{k!(n-k)!}}\\&={\frac {n!}{k!(n-k)!}}\\&={\binom {n}{k}}.\end{aligned}}}

Generalization

Pascal's rule can be generalized to multinomial coefficients. For any integer p such that p ≥ 2 {\displaystyle p\geq 2} , k 1 , k 2 , k 3 , … , k p ∈ N + , {\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,} and n = k 1 + k 2 + k 3 + ⋯ + k p ≥ 1 {\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1} , ( n − 1 k 1 − 1 , k 2 , k 3 , … , k p ) + ( n − 1 k 1 , k 2 − 1 , k 3 , … , k p ) + ⋯ + ( n − 1 k 1 , k 2 , k 3 , … , k p − 1 ) = ( n k 1 , k 2 , k 3 , … , k p ) {\displaystyle {n-1 \choose k_{1}-1,k_{2},k_{3},\dots ,k_{p}}+{n-1 \choose k_{1},k_{2}-1,k_{3},\dots ,k_{p}}+\cdots +{n-1 \choose k_{1},k_{2},k_{3},\dots ,k_{p}-1}={n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}} where ( n k 1 , k 2 , k 3 , … , k p ) {\displaystyle {n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}} is the coefficient of the x 1 k 1 x 2 k 2 ⋯ x p k p {\displaystyle x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{p}^{k_{p}}} term in the expansion of ( x 1 + x 2 + ⋯ + x p ) n {\displaystyle (x_{1}+x_{2}+\dots +x_{p})^{n}} .

The algebraic derivation for this general case is as follows. Let p be an integer such that p ≥ 2 {\displaystyle p\geq 2} , k 1 , k 2 , k 3 , … , k p ∈ N + , {\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,} and n = k 1 + k 2 + k 3 + ⋯ + k p ≥ 1 {\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1} . Then ( n − 1 k 1 − 1 , k 2 , k 3 , … , k p ) + ( n − 1 k 1 , k 2 − 1 , k 3 , … , k p ) + ⋯ + ( n − 1 k 1 , k 2 , k 3 , … , k p − 1 ) = ( n − 1 ) ! ( k 1 − 1 ) ! k 2 ! k 3 ! ⋯ k p ! + ( n − 1 ) ! k 1 ! ( k 2 − 1 ) ! k 3 ! ⋯ k p ! + ⋯ + ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ ( k p − 1 ) ! = k 1 ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! + k 2 ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! + ⋯ + k p ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = ( k 1 + k 2 + ⋯ + k p ) ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = n ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = n ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = ( n k 1 , k 2 , k 3 , … , k p ) . {\displaystyle {\begin{aligned}&{}\quad {n-1 \choose k_{1}-1,k_{2},k_{3},\dots ,k_{p}}+{n-1 \choose k_{1},k_{2}-1,k_{3},\dots ,k_{p}}+\cdots +{n-1 \choose k_{1},k_{2},k_{3},\dots ,k_{p}-1}\\&={\frac {(n-1)!}{(k_{1}-1)!k_{2}!k_{3}!\cdots k_{p}!}}+{\frac {(n-1)!}{k_{1}!(k_{2}-1)!k_{3}!\cdots k_{p}!}}+\cdots +{\frac {(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots (k_{p}-1)!}}\\&={\frac {k_{1}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}+{\frac {k_{2}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}+\cdots +{\frac {k_{p}(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={\frac {(k_{1}+k_{2}+\cdots +k_{p})(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}\\&={\frac {n(n-1)!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={\frac {n!}{k_{1}!k_{2}!k_{3}!\cdots k_{p}!}}={n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}.\end{aligned}}}

See also

References

  1. Mazur, David R. (2010), Combinatorics / A Guided Tour, Mathematical Association of America, p. 60, ISBN 978-0-88385-762-5
  2. ^ Brualdi, Richard A. (2010), Introductory Combinatorics (5th ed.), Prentice-Hall, ISBN 978-0-13-602040-0

Bibliography

External links

This article incorporates material from Pascal's triangle on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

This article incorporates material from Pascal's rule proof on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

Categories: