0
$\begingroup$

Assume we have three friends and we want to invite each to dinner for 6 days. I want to invite one for 3 days, another for 2 days and another for 1 day.

The answer is $P(3,3) \times \binom{6}{3} \times \binom{3}{1} $

I understand that there are three ways to decide which person to invite for three nights, and then we want to choose a person to invite for 3 nights out of 6 and another person to invite for one night out of three. I kind of don't like this approach of "leaving out" a possibility. So first, how does the above equation take into the account the two remaining days and what would be a different way to account for those two days in the equation?

2 Answers 2

2

There 3 three people, 1 takes 3 days, 1 takes 2 days, 1 takes 1 day.

We can understand the above answer as :

First you can permute 3 people's days after you choose their schedule.

As you said, we choose 3 out of 6 days for the first person. We remain 3 days.

Then we choose 1 out of 3 days for the third person.

Then we choose the last two days for the second person. The answer is:

3! * C(6,3) * C(3,1) * C(2,2)

C(2,2) = 1, and they did not put it in the answer.

  • 2
    @Nayefc: If you prefer a more symmetric *expression*, you can use the [multinomial coefficient](http://en.wikipedia.org/wiki/Multinomial_theorem) $\binom{6}{1,2,3}$. This is $\frac{6!}{1!2!3!}$, which is the same $60$ as your $\binom{6}{3}\binom{3}{1}$.2012-04-10
0

You can explicitly take everyone into account as follows.

  1. First choose which of the three friends is to be invited for three nights; you can do this in $3$ ways.

  2. Then choose which $3$ of the $6$ nights you’ll invite that friend; you can do this in $\binom63$ ways.

  3. Now choose which of the remaining friends is to be invited for two nights; you can do this in $2$ ways.

  4. Now choose which $2$ of the remaining $3$ nights you’ll invite that friend; you can do this in $\binom32$ ways.

  5. Now choose which of the one remaining friends you’ll invite for just one night; you can do this in only $1$ way, since only one friend remains.

  6. Finally, choose which of the one remaining nights you’ll invite that friend; you can do this in $\binom11$ ways.

The total number of ways of making these choices is therefore $3\cdot\binom63\cdot2\cdot\binom32\cdot1\cdot\binom11=3\cdot20\cdot2\cdot3\cdot1\cdot1=360\;.$

Of course, you could have started with the two-night friend, say, continued with the one-night friend, and finished with the three-night friend. Then the calculation, if performed in the same manner, would have yielded $3\cdot\binom62\cdot2\cdot\binom41\cdot1\cdot\binom33=3\cdot15\cdot2\cdot4\cdot1\cdot1=360\;.$ The factors of $3,2$, and $1$ are the same, corresponding to your $P(3,3)$, but every single one of the binomial coefficients looks different. And depending on the order in which you choose the one-, two-, and three-night friends and their nights, you can also get the following calculations:

$\begin{align*}&3\cdot\binom63\cdot2\cdot\binom31\cdot1\cdot\binom22\\ &3\cdot\binom62\cdot2\cdot\binom43\cdot1\cdot\binom11\\ &3\cdot\binom61\cdot2\cdot\binom53\cdot1\cdot\binom22\\ &3\cdot\binom61\cdot2\cdot\binom52\cdot1\cdot\binom33\;. \end{align*}$

The $3!$ is the same in all six versions, so why do the six different products of binomial coefficients yield the same result? It’s because they’re all counting the same thing: the number of ways to divide the $6$ available nights into a set of $3$ nights, a set of $2$ nights, and a set of $1$ night. Each product corresponds to a different order of making the choices. If I choose the set of $3$ first, then the set of $2$, and finally the set of $1$, I can make my choices in $\binom63\binom32\binom11$ ways. If, on the other hand, I choose the set of $2$ first, then the set of $1$, and finally the set of $3$, I can make my choices in $\binom62\binom51\binom33$ ways. And so on. Say that $a,b$, and $c$ are $1,2$, and $3$ in some order. If I pick the set of $a$ nights first, then the set of $b$ nights, and finally the set of $c$ nights, I can make the first choice in $\binom6a$ ways. That leaves $6-a$ nights, so I can make the second choice in $\binom{6-a}b$ ways. That leaves $6-a-b$ nights, and I can make the final choice in $\binom{6-a-b}c$ ways. That’s a total of

$\begin{align*} \binom6a\binom{6-a}b\binom{6-a-b}c&=\frac{6!}{a!\color{red}{(6-a)!}}\cdot\frac{\color{red}{(6-a)!}}{b!\color{blue}{(6-a-b)!}}\cdot\frac{\color{blue}{(6-a-b)!}}{c!(6-a-b-c)!}\\ &=\frac{6!}{a!b!c!} \end{align*}$

ways, since $6-a-b-c=0$, and $0!=1$. Clearly $\dfrac{6!}{a!b!c!}$ is the same no matter what permutation of $1,2$, and $3$ the $a,b$, and $c$ are, so all of these products of binomial coefficients boil down to the same quantity. This $\dfrac{6!}{a!b!c!}$ is the multinomial coefficient that André Nicolas mentioned in the comments; it’s written $\binom6{1,2,3}=\binom6{2,1,3}=\binom6{1,3,2}=\binom6{2,3,1}=\binom6{3,1,2}=\binom6{3,2,1}\;,$ all meaning $6!$ divided by the product of the factorials of the numbers listed on the bottom, which of course is the same in any order: $\frac{6!}{3!2!1!}=60\;.$