0
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ Just wondering, in your second step, you say (n-k)!(k-1)!, but would it not be (n-(k-1))!(k-1)!? $\endgroup$ – Howard P Feb 16 '17 at 18:25
  • 1
    $\begingroup$ @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. $\endgroup$ – Ben Blum-Smith Feb 27 '17 at 14:30
  • 3
    $\begingroup$ What is $k$? There is no $k$ in the problem. $\endgroup$ – bof Feb 28 '17 at 2:50
  • $\begingroup$ 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 $\endgroup$ – Howard P Mar 1 '17 at 21:51
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This answer is quite useful as this problem represents an equation, and the right-hand-side is your final answer! $\endgroup$ – Howard P Feb 16 '17 at 18:29
  • $\begingroup$ @HowardP That sentence makes no sense. Please clarify. $\endgroup$ – The Great Duck Feb 28 '17 at 19:33

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.