Prove that C(n, 2k)C(2k, k) = C(n, k)C(n − k, k), where n ≥ 2k > 0, by using (a) a combinatorial proof, (b) an algebraic proof

Question

So I am stuck on part a for this problem:

Prove that C(n, 2k)C(2k, k) = C(n, k)C(n − k, k), where n ≥ 2k > 0, by using

(a) a combinatorial proof,

(b) an algebraic proof

for part a, I'm pretty confused on using combinatorial proofs but for b this is what i got:

C(n, 2k)C(2k, k) = C(n, k)C(n − k, k)
n!/[(2k)!(n-2k)!] * (2k)!/[k!(2k-k)!]  = n!/[k!(n-k)!] * (n-k)!/[k!(n - k -k)!]
n!/[(2k)!(n-2k)!] * (2k)!/[k!(k)!]  = n!/[k!(n-k)!] * (n-k)!/[k!(n - 2k)!]
1/[(2k)!(n-2k)!] * (2k)!/[k!(k)!]  = 1/[k!(n-k)!] * (n-k)!/[k!(n - 2k)!]
1/[(2k)!] * (2k)!/[k!(k)!]  = 1/[k!(n-k)!] * (n-k)!/[k!]
1/[(2k)!] * (2k)!/[k!(k)!]  = 1/[k!] * 1/[k!]
1/[(2k)!] * (2k)!  = 1
1 = 1
QED

where at the end I was able to show that they are the same. Please tell me if I am correct on b and how to do a using combinatorial proof method.

Answer 1

Both expressions are the number of ways to choose two disjoint sets $A$ and $B$ of size $k$ from a set $S$ of size $n$.

Left side: first choose a set $C$ of $2k$ elements from $S$, then choose a set $A$ of $k$ elements of $C$, and take $B = C \backslash A$.

Right side: first choose a set $A$ of $k$ elements from $S$, then choose a set $B$ of $k$ elements from $S \backslash A$.

Answer 2

How many ways are there to place $k$ blue, $k$ white and $n-2k$ red marbles in a row ? Here are 2 equivalent ways:

• first way: you chose the $2k$ places where you will place the blue and the white marbles ($C(n,2k)$ ways). Then, for each of these ways, you choose among these $2k$ places those that will be occupied by the $k$ blue ones ($C(2k,k)$ ways to do that). There remain no choice for the red marbles. Because of the "for each of these ways", you have to multiply the number of choices.

• second equivalent way : you choose the $k$ places occupied by the blue marbles ($C(n,k)$ ways), then, for each of these ways, among the $n-k$ remaining places, you define the places occupied by the white marbles ($C(n-k,n)$ ways to do that). There remain no choice for the red marbles. Here again, you have to multiply the number of choices.