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 Answers 2

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$
1
  • $\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, 2017 at 18:29
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$
4
  • $\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, 2017 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$ Feb 27, 2017 at 14:30
  • 3
    $\begingroup$ What is $k$? There is no $k$ in the problem. $\endgroup$
    – bof
    Feb 28, 2017 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, 2017 at 21:51

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.