6
$\begingroup$

How to prove $C(15,4) \cdot C(11,5) = C(15,5) \cdot C(10,4)$ combinatorially?

I understand how to prove this algebraically but I'm uncertain of what exactly I'm supposed to be showing to prove it combinatorially.

By $C(n,k)$, I am referring to $n$ choose $k$, i.e., $\dbinom{n}k$.

$\endgroup$
9
$\begingroup$

Let us prove the following combinatorially: $$\dbinom{n}k \dbinom{n-k}r = \dbinom{n}r \dbinom{n-r}k$$ Given a set of $n$ students, we want to choose $k$ of them to be in team $1$ and $r$ of them to be in team $2$.

First let us choose the students to go to team $1$ and then to team $2$. The number of ways of doing this is $$\dbinom{n}k \dbinom{n-k}r$$

Now let us choose the students to go to team $2$ first and then to team $1$. The number of ways of doing this is $$\dbinom{n}r \dbinom{n-r}k$$

Both have to be equal. Take $n=15$, $k=5$ and $r=4$ for your case.

It also worth noting that there is another way to count the same. First choose $k+r$ students from $n$ students, and choose $k$ of them to go to team $1$ and the rest $r$ of them to go to team $2$. This can be done in $$\dbinom{n}{k+r} \dbinom{k+r}k$$

Hence, we have $$\color{red}{\dbinom{n}k \dbinom{n-k}r} = \color{blue}{\dbinom{n}r \dbinom{n-r}k} = \color{green}{\dbinom{n}{k+r} \dbinom{k+r}k}$$

$\endgroup$
  • $\begingroup$ Thank you, that makes a lot of sense! I'm a little confused how to set up my argument to show that combinatorally now. I feel like I am still proving it algebraically and I need to distinguish one from the other. Would I just provide an explanation instead of actual number crunching? $\endgroup$ – user104203 Dec 2 '13 at 6:57
  • 1
    $\begingroup$ @user104203 Yes, in a combinatorial argument, you count things on one side in one way and in another side in another way. You do not need to explicitly work out the algebraic simplifications. The main emphasis is to come up with two different methods to count the same thing. $\endgroup$ – user17762 Dec 2 '13 at 7:04
  • $\begingroup$ Very helpful and informative. Thanks! $\endgroup$ – user104203 Dec 2 '13 at 7:09
3
$\begingroup$

HINT: I have $15$ white balls, numbered $1$ through $15$. There are $\binom{15}4$ ways to pick $4$ of them and paint them blue. That leaves $11$ white balls, and there are $\binom{11}5$ ways to choose $5$ of them and paint them red. There are therefore $\binom{15}4\binom{11}5$ ways to perform the two tasks in succession, so there are $\binom{15}4\binom{11}5$ ways to paint $4$ of the $15$ balls blue and $5$ of them red.

Now suppose that you do the choosing and painting in the other order: first choose $5$ balls to paint red, then choose $4$ of the remaining white balls to paint blue. In how many ways can you do that?

Of course you’re getting the same results in each case: every possible way of painting $4$ of the balls blue and $5$ of them red. Thus, the two computations must yield the same result. Counting the same thing in two different ways like this is the essence of a combinatorial proof that two calculations yield the same result.

$\endgroup$
  • $\begingroup$ So to show this combinatorally, I am just showing that it can be counted in two different ways and they are equal? How do I show that not algebraically? $\endgroup$ – user104203 Dec 2 '13 at 7:06
  • $\begingroup$ @user104203: Half of the combinatorial argument is my first paragraph; the other half is what you get when you write up the same sort of argument for the second paragraph. Both arguments clearly count the same thing, but one results in a total of $\binom{15}4\binom{11}5$ and the other in a total of $\binom{15}5\binom{10}4$, so these two totals must be the same. That’s a purely combinatorial argument. $\endgroup$ – Brian M. Scott Dec 2 '13 at 18:56
0
$\begingroup$

You can interpret the lhs as the number of ways to split 15 things into 4|11 and then split the 11 into 5|6, giving 4|5|6. Similarly the rhs is the number of ways to split 15 things into 5|10 and then split the 10 into 4|6. Therefore combinatorially both the rhs and the lhs therefore give the number of ways to split 15 things into 4|5|6.

$\endgroup$
  • $\begingroup$ Is this what combinatorally means? To divide it like that? $\endgroup$ – user104203 Dec 2 '13 at 7:04
0
$\begingroup$

As a kind of answer / amusing aside, there is a variation of this problem presented as a "self-working" magic trick in Martin Gardner's Hexaflexagons and Other Mathematical Diversions:

The magician, who is seated at a table directly opposite a spectator, first reverses 20 cards anywhere in the deck. That is, he turns them face up in the pack. The spectator thoroughly shuffles the deck so that these reversed cards are randomly distributed. He then holds the deck underneath the table, where it is out of sight of everyone, and counts off 20 cards from the top. This packet of 20 cards is handed under the table to the magician.

The magician takes the packet but continues to hold it beneath the table so that he cannot see the cards. "Neither you nor I," he says, "knows how many cards are reversed in this group of 20 that you handed me. However, it is likely that the number of such cards is less than the number of reversed cards amoung the 32 that you are holding. Without looking at my cards, I am going to turn a few more face-down cards face up and attempt to bring the number of reversed cards in my packet to exaclty the same number as the number of reversed cards in yours."

The magician fumbles with his cards for a moment, pretending that he can distinguish the fronts and backs of the cards by feeling them. Then he brings the packet into view and spreads it on the table. The face-up cards are counted. Their number proves to be identical with the number of face-up cards among the 32 held by the spectator!

I will leave it as an exercise to the reader to figure out how the trick is done, but suffice it to say it involves the same basic combinatoric problem stated here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.