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

Let us begin by writing the left-hand side as

 \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-(k-1))!}.

Getting a common denominator and simplifying, we have

\begin{align}
& {} \qquad \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-k+1)!} \\\\
& = \frac{(n-k+1)n!}{(n-k+1)k!(n-k)!}+\frac{kn!}{k(k-1)!(n-k+1)!} \\\\
& = \frac{(n-k+1)n!+kn!}{k!(n-k+1)!} \\\\
& = \frac{(n+1)n!}{k!((n+1)-k)!} \\\\
& = \frac{(n+1)!}{k!((n+1)-k)!} \\\\
& = { n+1 \choose k }.
\end{align}

Generalization[edit]

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

Sources[edit]

External links[edit]