Number of combinations of k types from set n with limited number of each type

probability combinatorics statistics permutations combinations

1,393

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$

1,393

padawn

Updated on August 01, 2022

Comments

padawn over 1 year

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.
- Prasun Biswas over 8 years
  
  Doesn't $\dfrac{^n\mathrm{P}_6}{3!\cdot 4!\cdot 5!}$ work? Considering that you want to preserve order of arrangement.
- padawn over 8 years
  
  I think that only works if the you are trying to get a permutation of length (k1+k2+k...) i.e. the sum of all available selections. If you are picking a permutation less then that, this formula doesn't work.
- Prasun Biswas over 8 years
  
  I used $^n\mathrm{P}_6$ for that purpose. It denotes that we're permuting $6$ elements out of $n$ elements at a time. Thus, we'll get the total number of $6$-tuple arrangements possible (taking arrangement into consideration).
- true blue anil over 8 years
  
  Are the dishes in a particular type of meat distinguishable ?
- padawn over 8 years
  
  no, all the dishes of the same type of meat are the same, only way to distinguish a dish is the meat type