Massive Math Stuff: Pascal's rule - Wikipedia, the free encyclopedia

Monday, July 28, 2014

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

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

Massive Math Stuff