Proof that a Combination is an integer

From its definition a combination (nk), is the number of distinct subsets of size k from a set of n elements.

This is clearly an integer, however I was curious as to why the expression

n!k!(nk)! always evaluates to an integer.

So far I figured:

n!, is clearly divisible by k!, and (nk)!, individually, but I could not seem to make the jump to proof that that n! is divisible by their product.

Answer

Well, one noncombinatorial way is to induct on n using Pascal’s triangle; that is, using the fact that (nk)=(n1k1)+(n1k) (easy to verify directly) and that each (n10) is just 1.

Attribution
Source : Link , Question Author : Akusete , Answer Author : Zarrax

Leave a Comment