Pascal's rule

In mathematics, Pascal's rule is a combinatorial identity about binomial coefficients. It states that for any natural number n we have

${n-1\choose k} + {n-1\choose k-1} = {n\choose k}\quad\text{for }1 \le k \le n$

where ${n\choose k}$ is a binomial coefficient. This is also commonly written

${n \choose k} + {n \choose k-1} = {n + 1 \choose k} \quad\text{for } 1 \le k \le n + 1$

Combinatorial proof

Pascal's rule has an intuitive combinatorial meaning. Recall that ${a\choose b}$ counts in how many ways can we pick a subset with b elements out from a set with a elements. Therefore, the right side of the identity ${n\choose k}$ is counting how many ways can we get a k-subset out from a set with n elements.

Now, suppose you distinguish a particular element 'X' from the set with n elements. Thus, every time you choose k elements to form a subset there are two possibilities: X belongs to the chosen subset or not.

If X is in the subset, you only really need to choose k − 1 more objects (since it is known that X will be in the subset) out from the remaining n − 1 objects. This can be accomplished in $n-1\choose k-1$ ways.

When X is not in the subset, you need to choose all the k elements in the subset from the n − 1 objects that are not X. This can be done in $n-1\choose k$ ways.

We conclude that the numbers of ways to get a k-subset from the n-set, which we know is ${n\choose k}$, is also the number ${n-1\choose k-1} + {n-1\choose k}.$

See also Bijective proof.

Algebraic proof

We need to show

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

$\begin{align} { n \choose k } + { n \choose k-1} & = \frac{n!}{k! (n - k)!} + \frac{n!}{(k - 1)!(n - k + 1)!} \\ & = n! \left[ \frac{n + 1 - k}{k!(n + 1 - k)!} + \frac{k}{k!(n + 1 - k)!}\right] \\ & = \frac{n!(n+1)}{k!(n + 1 - k)!} = \binom{n+1}{k} \end{align}$

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

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 at PlanetMath.org.
• Binomial coefficient at PlanetMath.org.
• Pascal's triangle at PlanetMath.org.