Pascal's rule

From Wikipedia, the free encyclopedia
Jump to: navigation, search
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 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[edit]

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[edit]

We need to show

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

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


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

& {} \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}.

See also[edit]


External links[edit]