Pascal's rule

Not to be confused with Pascal's law.

In mathematics, Pascal's rule is a combinatorial identity about binomial coefficients. It states that for any natural number n, ${n-1 \choose k}+{n-1 \choose k-1}={n \choose k}$ for $1\leq k\leq n$ where ${n \choose k}$ is the binomial coefficient of the x^k term in the expansion of (1 + x)ⁿ.

Combinatorial proof

Pascal's rule has an intuitive combinatorial meaning. See also bijective proof.

Proof. Recall that ${n \choose 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, choose X and k-1 elements from the remaining n-1 elements in the set. There are ${n-1 \choose 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 \choose 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 \choose k-1}+{n-1 \choose k}$.

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

Algebraic proof

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

Generalization

Let $n,k_{1},k_{2},k_{3},\dots ,k_{p},p\in \mathbb {N} ^{*}$ and $n=k_{1}+k_{2}+k_{3}+\cdots +k_{p}$. Then

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

• Pascal's triangle

Sources

• This article incorporates material from Pascal's rule 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.
• Merris, Russell. Combinatorics. John Wiley & Sons. 2003 ISBN 978-0-471-26296-1

External links

• "Central binomial coefficient". PlanetMath.
• "Binomial coefficient". PlanetMath.
• "Pascal's triangle". PlanetMath.