Combinatorial Proof of ${{n}\choose{k}} {{k}\choose{j}} = {{n}\choose{j}} {{n-j}\choose{k-j}}$ [closed]

How do I prove by a combinatorial argument that ${{n}\choose{k}} {{k}\choose{j}} = {{n}\choose{j}} {{n-j}\choose{k-j}}$

Solution 1:

Lets have this combinatorial problem: "Find out how many ways you can distribute $j$ apples and $k-j$ oranges among $n$ persons, when your task is to give anyone one piece of fruit at most."

One way to do that is to pick $k$ people, who will receive some fruit and of these people choose $j$ people, that will get apples. The rest of $k-j$ people will logically get oranges in only one way possible. That leads us to the number on the left side.

Other way to do that is to pick $j$ people that will get the apples, and from the rest of $n-j$ people, you can pick $k-j$ ways the rest, that will get the oranges". That gets us the number on the right side.

Both ways solve the same problem, so the numbers must be the same.

Solution 2:

We can proceed this way

For LHS, We are to permit $k$ people inside bus from a queue of $n$ people. And then choice is made for $j$ of those $k$ are provided a seat.

For RHS, We are to choose at first $j$ people from $n$ who can sit. Now from remaining $n-j$ people we choose $k-j$ people who will board without seat. Thus both cases are same.