Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
2  
@Nayefc: If you prefer a more symmetric expression, you can use the multinomial coefficient $\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}$. –  André Nicolas Apr 10 '12 at 20:26
add comment

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\;.$$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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