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-1choose\; k\}\; +\; \{n-1choose\; k-1\}\; =\; \{nchoose\; k\}$where 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 number$\{n-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

:

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

:

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-1

External links

*
*
*