Combinatorial Argument with Natural Numbers

Question

Give a combinatorial argument to show that all natural numbers n ≥ k ≥ m

c(n,k) * c(k,m) = c(n,m) * c((n-m),(k-m)) where c stands for combination.

Answer 1

We have $n$ different doughnuts, and want to choose $k$ of them to eat today, of which $m$ are to be eaten this morning. We count the number of ways to do it. Here are two ways to do the counting.

Way 1: We choose the $k$ doughnuts for today, then choose the ones for this morning from the $k$ selected. The $k$ doughnuts for today can be chosen in $\binom{n}{k}$ ways, and for each of these the ones for this morning can be chosen in $\binom{k}{m}$ ways.

Way 2: We choose the ones for this morning. This can be done in $\binom{n}{m}$ ways. Then we choose the ones for the rest of the day, $\binom{n-m}{k-m}$ ways.

Answer 2

Supposing $m\leq k\leq n$, these are two different expressions for the trinomial coefficient $\binom n{m,k-m,n-k}$, the number of ways to colour $n$ points so $m$ are red, $k-m$ are white, and the remaining $n-k$ are blue. (1) Select the blue points, then among the remaining points the red points, respectively (2) select the red points, then among the remaining points the white points.

Answer 3

since we know c(n,k)=n!/(n-k)!k!

L.H.S= c(n,k) * c(k,m) = (n!/(n-k)!k!)*(k!/(k-m)!m!) =n!/(n-k)!(k-m)!m!=trinomial coefficient (n m,k−m,n−k)

R.H.S=c(n,m) * c((n-m),(k-m)) =(n!/(n-m)!m!)*((n-m)!/(n-k)!(k-m)!) =n!/(n-k)!(k-m)!m!=trinomial coefficient (n m,k−m,n−k)

so c(n,k) * c(k,m) = c(n,m) * c((n-m),(k-m))=trinomial coefficient (n m,k−m,n−k)