Combinations: People want a beer, there are certain kinds of beer, but limited numbers of each kind

Question

Four people go to a pub and each wants to drink a pint of either the lager, ale, or porter. However, there are only 2 pints of lager, 1 ale, and 1 porter available to drink.

How many combinations of people and drinks are there, given that each person wants a drink?

My guess is that the answer is $_{4}C_{2}\times2\times1$

What I really want though is a general expression for this sort of problem.

Here is my thinking:

There are $m$ people and $p$ categories. $\sum_{k=1}^{p}p_{k}=m$ where $p_{k}$ is the number of available spots in each category, for $k=1,...p$.

Number of total combinations is $_{m}C_{p_{1}}\times_{m-p_{1}}C_{p_{2}}\times...\times_{m-\sum_{k=1}^{p-1}}C_{p_{k}}$

Is my thinking correct? Thanks every1.

Answer 1

4 distinct drinks can be distributed to 4 people in $4!$ ways, but the 2 lagers are not distinct (it doesn't matter which pint of lager a person gets), you must divide by $2!$ - the permutations of the lager among themselves.

To be precise the answer is a multinomial coefficient.

$${4 \choose 2, 1, 1} = \frac{4!}{2!1!1!}$$

Another approach is to choose 2 of 4 people to get the lager, 1 of 2 people to get the ale and give the porter to the last remaining person.

$${4\choose 2}{2\choose 1}{1 \choose 1} = \frac{4!}{2!2!}\frac{2!}{1!1!}\frac{1!}{1!1!}$$

Which is, of course, mathematically identical.

In general, if you have a multiset of elements and multiplicity, $\{(a_1,m_1),\ldots,(a_k, m_k),\ldots,(a_n,m_n)\}$, then the permutations are counted by:

$${\sum_{k=1}^n m_k\choose m_1,\ldots,m_k,\ldots, m_n} = \frac{(\sum_{k=1}^n m_k)!}{\prod_{k=1}^n (m_k!)}$$

Answer 2

I think of your general problem as follows. We have a bunch of letters. Among these, there are exactly $p_1$ $A_1$'s, $p_2$ $A_2$'s, and so on up to $p_w$ $A_w$'s. I substituted $k=1,2,\dots,w$ for your $k=1,2,\dots,p$, since in a lecture $p_p$ would be distracting.

We want to make an $m$-letter word, where $m=\sum p_k$.

Imagine painting the identical letters different colours, to make them distinct.Then there are $m!$ words. Now "uncolour" the $A_1$'s. Then $p_1!$ words that used to be distinct collapse into one. So now we have $\frac{m!}{p_1!}$ words. Uncolour the $A_2$'s. Again there is a collapsing, and we now have $\frac{m!}{p_1!p_2!}$ words. Continue. We end up with $$\frac{m!}{p_1!p_2!\cdots p_w!}\tag{1}$$ words. There is a standard abbreviation for this: $\binom{m}{p_1,p_2,\dots,p_w}$. For a detailed discussion, please see Wikipedia, Multinomial Coefficients.

Your approach will also work. Choose $p_1$ locations for the $A_1$'s. This can be done in $\binom{m}{p_1}$ ways. For each of these, there are $\binom{m-p_1}{p_2}$ ways to choose the locations of the $A_2$'s. And then there are $\binom{m-p_1-p_2}{p_3}$ ways to choose the locations of the $A_3$'s. And so on. Now multiply.

If we express the binomial coefficients above in terms of factorials, we have a lot of cancellation, and we end up with Formula (1).