- Pascal's rule
In
mathematics , Pascal's rule is a combinatorial identity aboutbinomial coefficient s. It states that for anynatural number "n" we have:n-1choose k} + {n-1choose k-1} = {nchoose k} where 1 leq k < n and nchoose k} is a binomial coefficient.Combinatorial proof
Pascal's rule has an intuitive combinatorial meaning. Recall that achoose 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 nchoose 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-1choose 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-1choose k ways.
We conclude that the numbers of ways to get a "k"-subset from the "n"-set, which we know is nchoose k}, is also the numbern-1choose k-1} + {n-1choose k}.
See also
Bijective proof .Algebraic proof
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
:egin{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
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
: egin{align}& {} quad {n-1choose k_1-1,k_2,k_3, dots, k_p}+{n-1choose k_1,k_2-1,k_3,dots, k_p}+cdots+{n-1choose 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!}= {nchoose k_1, k_2, k_3, dots , k_p}.end{align}
ee also
*
Pascal's triangle ources
*planetmath|id=246|title=Pascal's rule
*planetmath|id=259|title= Pascal's rule proof
*Merris, Russell. [http://media.wiley.com/product_data/excerpt/6X/04712629/047126296X.pdf"Combinatorics"] . John Wiley & Sons. 2003 ISBN 978-0-471-26296-1External links
*
*
*
Wikimedia Foundation. 2010.