How can I find the number of combinations of types from a set of multiple types when the number of each type is limited?
For example, I have a set of 3 chicken dishes, 4 beef dishes, and 5 lamb dishes. How many different 6 dish meat combinations are possible from this group of dishes?
I can't use combination with repetition (r+n-1)/r because that will count dishes of chicken, beef, and lamb that are not available.
I can't use permutation of types n!/k1!k2!k…! because I'm choosing an amount smaller then the total set.
Best Answer
Rephrasing the question into a more common form, you are asking for the number of integral solutions to the following system:
$$\begin{cases} x_1+x_2+x_3 = 6\\ 0\leq x_1\leq 3 \\ 0\leq x_2\leq 4 \\ 0\leq x_3\leq 5\end{cases}\\\text{where each of}~~x_1,x_2,x_3\in\mathbb{Z}$$
You correctly noted above that if there was not a maximum limit above that the solution would be $\binom{6+3-1}{6}$, as per the stars-and-bars method.
We will couple this knowledge with the principle of inclusion-exclusion. The combinations we are interested in will be the set of all possible combinations without restriction minus those combinations which violate one or more of the restrictions.
Let $A_1$ be the set of all combinations such that you violate the upper bound on $x_1$ (i.e. you have strictly more than 3 chicken dishes). How many combinations exist in $A_1$ that we will need to subtract from the total?
Well, since the upperbound condition is violated, that means $4\leq x_1$. By a change of variable $y_1=x_1-4$, we arrive at the system: $$\begin{cases} y_1+x_2+x_3 = 2\\ 0\leq y_1 \\ 0\leq x_2 \\ 0\leq x_3\end{cases}\\\text{where each of}~~y_1,x_2,x_3\in\mathbb{Z}$$
The number of which then is $\binom{2+3-1}{2}$.
Continue calculating $A_2$ and $A_3$ which will represent having violated $x_2$'s upper bound and $x_3$'s upper bound respectively (i.e. having sold too many beef and lamb dishes).
In general though, it is possible for these to intersect (that you could have simultaneously sold too many chicken and simultaneously sold too many lamb dishes). You will need then to calculate $A_{1,2}, A_{1,3}, A_{2,3}$ and possibly even $A_{1,2,3}$ denoting having violated each of the corresponding conditions simultaneously.
Letting $B$ denote no violated conditions, and $S$ denoting no conditions present in the first place, by principle of inclusion-exclusion the answer will be:
$|B| = |S| - |A_1| - |A_2| - |A_3| + |A_{1,2}| + |A_{1,3}| + |A_{2,3}| - |A_{1,2,3}|$
Which in this case is:
$=\binom{6+3-1}{6} - \binom{2+3-1}{2} - \binom{1+3-1}{1} - \binom{0+3-1}{0} + 0 +0 + 0 - 0$
(noting that it is impossible in this case to simultaneously sell too many of two types of dish at the same time)
To generalize this problem to the larger case, let $A_{i}$ denote violating the $i^{th}$ condition (and possibly more), $A_{i,j}$ denote violating the $i^{th}$ and $j^{th}$ conditions, ... $A_{i,j,\dots,p}$ denote violating each of the conditions $i$ through $p$, and even more generally for an index set $\Delta \subset \{1,2,\dots,k\}$ you will have $A_\Delta$ violating all of the conditions on $x_i$ for each $i\in\Delta$:
$$|B| = |S| + \sum\limits_{i=1}^k\left((-1)^i\sum\limits_{|\Delta|=i}|A_{\Delta}|\right)$$
And $|A_\Delta| = \binom{n +k - 1- \sum\limits_{i\in\Delta}(r_i+1)}{n}$, where $r_i$ is the upper bound for $x_i$