Samiksha Jaiswal (Editor)

Pascal's rule

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In mathematics, Pascal's rule is a combinatorial identity about binomial coefficients. It states that for any natural number n we have

Contents

( n − 1 k ) + ( n − 1 k − 1 ) = ( n k ) for  1 ≤ k ≤ n

where ( n k ) is a binomial coefficient. This is also commonly written

( n k ) + ( n k − 1 ) = ( n + 1 k ) for  1 ≤ k ≤ n + 1

Combinatorial proof

Pascal's rule has an intuitive combinatorial meaning. Recall that ( a 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 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 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 k ) ways.

We conclude that the numbers of ways to get a k-subset from the n-set, which we know is ( n k ) , is also the number ( n − 1 k − 1 ) + ( n − 1 k ) .

See also Bijective proof.

Algebraic proof

We need to show

( n k ) + ( n k − 1 ) = ( n + 1 k ) . ( n k ) + ( n k − 1 ) = n ! k ! ( n − k ) ! + n ! ( k − 1 ) ! ( n − k + 1 ) ! = n ! [ n − k + 1 k ! ( n − k + 1 ) ! + k k ! ( n − k + 1 ) ! ] = n ! ( n + 1 ) k ! ( n − k + 1 ) ! = ( n + 1 k )

Generalization

Let n , k 1 , k 2 , k 3 , … , k p , p ∈ N ∗ and n = k 1 + k 2 + k 3 + ⋯ + k p . Then

( n − 1 k 1 − 1 , k 2 , k 3 , … , k p ) + ( n − 1 k 1 , k 2 − 1 , k 3 , … , k p ) + ⋯ + ( n − 1 k 1 , k 2 , k 3 , … , k p − 1 ) = ( n − 1 ) ! ( k 1 − 1 ) ! k 2 ! k 3 ! ⋯ k p ! + ( n − 1 ) ! k 1 ! ( k 2 − 1 ) ! k 3 ! ⋯ k p ! + ⋯ + ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ ( k p − 1 ) ! = k 1 ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! + k 2 ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! + ⋯ + k p ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = ( k 1 + k 2 + ⋯ + k p ) ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = n ( n − 1 ) ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = n ! k 1 ! k 2 ! k 3 ! ⋯ k p ! = ( n k 1 , k 2 , k 3 , … , k p ) .

References

Pascal's rule Wikipedia
(Text) CC BY-SA