# Combinatorial proof for party-goers.

I'm doing a problem involving combinations as follows:

Consider a house with $n$ room-mates. Each weekend, one or more of the room-mates form a group to drive to a party. Of the group, one is the designated driver. How many ways can this be done? Do the calculation two ways:

The two ways are

1. where you pick the designated driver, then the rest of the room-mates going, and

2. where you pick everyone going, and you pick the designated driver from that group.

I am confused on how to calculate the left side. (I'm trying to show that they're equal.)

Thanks for helping!

Edit: I've come up with $C(n,1) \cdot C(n-1,k-1)$ for the left hand side, could be wrong though!

For #1. First we pick the designated driver. There are ${n \choose 1}=n$ ways to do this. Then from the remaining $n-1$ roommates, we want to find all subgroups that are in the group. There are $2^{n-1}$ to do this. Therefore, the total number of ways to form this group is $n2^{n-1}$.

For #2. We first pick the groups and from these pick a designated driver leading to $\sum_{k=1}^{n} {n \choose k} {k \choose 1}=n\sum_{k=1}^{n} {{n-1} \choose {k-1}}=n\sum_{s=0}^{n-1}{{n-1} \choose s} = n2^{n-1}$

So they are indeed equal

• This answer is quite useful as this problem represents an equation, and the right-hand-side is your final answer! Feb 16, 2017 at 18:29

For the first case you have done it correctly that is $\binom{n}{1} \times \binom{n-1}{k-1}$ ways.

For the next you have $\binom{n}{k}$ ways to form a group and then choose a driver amng them in $k$ ways. So the total ways is $k \times \binom{n}{k}$.

Now see that $$\binom{n}{1} \times \binom{n-1}{k-1} = n \times \frac{n-1!}{(n-k)! (k-1)!} = k \times \frac{n!}{(n-k)!k! } = k\times \binom{n}{k}$$

• Just wondering, in your second step, you say (n-k)!(k-1)!, but would it not be (n-(k-1))!(k-1)!? Feb 16, 2017 at 18:25
• @HowardP - It would be $((n-1) - (k-1))!(k-1)!$, but $(n-1)-(k-1) = n-k$, so it is correct as loneuser has written it. Feb 27, 2017 at 14:30
• What is $k$? There is no $k$ in the problem.
– bof
Feb 28, 2017 at 2:50
• Loneuser uses the variable k in his equation, it is an example and not entirely representative of the above question. Any variables could be used Mar 1, 2017 at 21:51