Pascal's rule

{{Short description|Combinatorial identity about binomial coefficients}}

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,

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

where $\tbinom{n}{k}$ is the binomial coefficient, namely the coefficient of the {{math|x^k}} term in the expansion of {{math|(1 + x)ⁿ}}. There is no restriction on the relative sizes of {{mvar|n}} and {{mvar|k}};{{citation| first=David R.|last=Mazur| title=Combinatorics / A Guided Tour| year=2010| publisher=Mathematical Association of America| page=60| isbn=978-0-88385-762-5}} in particular, the above identity remains valid when {{math|n < k}} since $\tbinom{n}{k} = 0$ whenever {{math|n < k}}.

Together with the boundary conditions $\tbinom{n}{0} = \tbinom{n}{n}= 1$ for all nonnegative integers n, Pascal's rule determines that

$\binom{n}{k} = \frac{n!}{k!(n-k)!},$

for all integers {{math|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

File:Pascal's rule 4c1 plus 4c2 equals 5c2.svg

Pascal's rule has an intuitive combinatorial meaning, that is clearly expressed in this counting proof.{{rp|p=44}}

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

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

Algebraic proof

Alternatively, the algebraic derivation of the binomial case follows.

$\begin{align}
{ 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{align}$

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

$\begin{align}
{ 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{align}$

Since $\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

Pascal's rule can be generalized to multinomial coefficients.{{citation|first=Richard A.|last=Brualdi| title=Introductory Combinatorics| edition=5th| year=2010| publisher=Prentice-Hall| isbn=978-0-13-602040-0}}{{rp|p=144}} For any integer p such that $p \ge 2$ , $k_1, k_2, k_3, \dots, k_p \in \mathbb{N}^{+}\!,$ and $n = k_1 + k_2 + k_3 + \cdots + k_p \ge 1$ ,

${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\choose k_1, k_2, k_3, \dots , k_p}$ is the coefficient of the $x_1^{k_1}x_2^{k_2}\cdots x_p^{k_p}$ term in the expansion of $(x_1 + x_2 + \dots + x_p)^{n}$ .

The algebraic derivation for this general case is as follows.{{rp|p=144}} Let p be an integer such that $p \ge 2$ , $k_1, k_2, k_3, \dots, k_p \in \mathbb{N}^{+}\!,$ and $n = k_1 + k_2 + k_3 + \cdots + k_p \ge 1$ . Then

$\begin{align}
& {} \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{align}$

References

Bibliography

Merris, Russell. [http://media.wiley.com/product_data/excerpt/6X/04712629/047126296X.pdfCombinatorics]. John Wiley & Sons. 2003 {{ISBN|978-0-471-26296-1}}

External links

{{planetmath reference|urlname=CentralBinomialCoefficient|title=Central binomial coefficient}}
{{planetmath reference|urlname=BinomialCoefficient|title=Binomial coefficient}}

{{PlanetMath attribution|title=Pascal's triangle|urlname=PascalsTriangle}}

{{PlanetMath attribution|title= Pascal's rule proof|urlname=pascalsruleproof}}

Category:Combinatorics

Category:Algebraic identities

Category:Articles containing proofs