Voozh

From Wikipedia, the free encyclopedia

In mathematics, Pascal's rule (or Pascal's formula) is a combinatorial identity about binomial coefficients. The binomial coefficients are the numbers that appear in Pascal's triangle. Pascal's rule states that for positive integers n and k, 👁 {\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k},}
where 👁 {\displaystyle {\tbinom {n}{k}}}
is the binomial coefficient, namely the coefficient of the x^k term in the expansion of (1 + x)ⁿ. There is no restriction on the relative sizes of n and k;^[1] in particular, the above identity remains valid when n < k since 👁 {\displaystyle {\tbinom {n}{k}}=0}
whenever n < k.

Together with the boundary conditions 👁 {\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1}
for all nonnegative integers n, Pascal's rule determines that 👁 {\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},}
for all integers 0 ≤ k ≤ n. In this sense, Pascal's rule is the recurrence relation that defines the binomial coefficients.

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

Combinatorial proof

[edit]

👁 Image

Illustrates combinatorial proof: 👁 {\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.^[2]^: 44

Proof. Recall that 👁 {\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 👁 {\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 👁 {\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, 👁 {\displaystyle {\tbinom {n-1}{k-1}}+{\tbinom {n-1}{k}}}
.

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

Algebraic proof

[edit]

Alternatively, the algebraic derivation of the binomial case follows. 👁 {\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[{\frac {n-k}{k!(n-k)!}}+{\frac {k}{k!(n-k)!}}\right]\\&=(n-1)!{\frac {n}{k!(n-k)!}}\\&={\frac {n!}{k!(n-k)!}}\\&={\binom {n}{k}}.\end{aligned}}}

An alternative algebraic proof using the alternative definition of binomial coefficients: 👁 {\displaystyle {\tbinom {n}{k}}={\frac {n(n-1)\cdots (n-k+1)}{k!}}}
. Indeed

👁 {\displaystyle {\begin{aligned}{n-1 \choose k}+{n-1 \choose k-1}&={\frac {(n-1)\cdots ((n-1)-k+1)}{k!}}+{\frac {(n-1)\cdots ((n-1)-(k-1)+1)}{(k-1)!}}\\&={\frac {(n-1)\cdots (n-k)}{k!}}+{\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\\&={\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\left[{\frac {n-k}{k}}+1\right]\\&={\frac {(n-1)\cdots (n-k+1)}{(k-1)!}}\cdot {\frac {n}{k}}\\&={\frac {n(n-1)\cdots (n-k+1)}{k!}}\\&={\binom {n}{k}}.\end{aligned}}}

Since 👁 {\displaystyle {\tbinom {z}{k}}={\frac {z(z-1)\cdots (z-k+1)}{k!}}}
is used as the extended definition of the binomial coefficient when z is a complex number, thus the above alternative algebraic proof shows that Pascal's rule holds more generally when n is replaced by any complex number.

Generalization

[edit]

Pascal's rule can be generalized to multinomial coefficients.^[2]^: 144 For any integer p such that 👁 {\displaystyle p\geq 2}
, 👁 {\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {Z} ^{+}\!,}
and 👁 {\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1}
, 👁 {\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 👁 {\displaystyle {n \choose k_{1},k_{2},k_{3},\dots ,k_{p}}}
is the coefficient of the 👁 {\displaystyle x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{p}^{k_{p}}}
term in the expansion of 👁 {\displaystyle (x_{1}+x_{2}+\dots +x_{p})^{n}}
.

The algebraic derivation for this general case is as follows.^[2]^: 144 Let p be an integer such that 👁 {\displaystyle p\geq 2}
, 👁 {\displaystyle k_{1},k_{2},k_{3},\dots ,k_{p}\in \mathbb {N} ^{+}\!,}
and 👁 {\displaystyle n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}\geq 1}
. Then 👁 {\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}}}

References

[edit]

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