Suppose we need to choose 5 out of 8 types of objects, how many ways are there for doing this? The problem can be seen as one of separation:
1|222|3|||||
In the above example, we have 1 object of type 1, 3 objects of type 2, 1 object of type 3, and 0 objects of other types. Essentially, we need to pick 5 out of 12 positions for objects, and all the rest are separators, hence the solution is $12 \choose 5$.
Now, what if we additionally require that for each type of objects, the number of repetition should be less than a certain limit, 3 for example?
Best Answer
Reworded, you ask for the number of integral solutions to the system:
$\begin{cases} x_1+x_2+x_3+\dots+x_8=5\\ 0\leq x_1\leq 3\\ 0\leq x_2\leq 3\\ \vdots\\ 0\leq x_8\leq 3\end{cases}$
Let $\Omega$ denote the set of solutions to the problem without upper bounds. Let $A_i$ denote the set of solutions to the problem without upper bounds where $x_i\not\leq 3$. Similarly, let $A_{i,j}$ and $A_{i,j,k}$ denote the set of solutions to the problem without upper bounds where $x_i$ and $x_j$ (and $x_k$) are not less than or equal to three. In other words, are greater than or equal to four.
You can see then that the number of solutions satisfying all upper bound conditions simultaneously can be written as:
$$|A_1^c\cap A_2^c\cap \dots \cap A_8^c|$$
Applying inclusion-exclusion:
$$\left|\bigcap_{i=1}^8 A_i^c\right| = \left|\Omega \setminus (\bigcup_{i=1}^8 A_i)\right| = |\Omega| - |A_1|-|A_2|-\cdots +|A_{1,2}|+|A_{1,3}|+\dots-|A_{1,2,3}|-|A_{1,2,4}|-\dots+\dots$$
How do we count something like $|\Omega|$?
This is the usual format for the question, asking for the number of integral solutions to the system:
$\begin{cases} x_1+\dots+x_8=5\\ 0\leq x_1\\ \vdots\\ 0\leq x_8\end{cases}$
By earlier example (seen by stars and bars) there are $\binom{5+8-1}{8-1}=\binom{5+8-1}{5}=\binom{12}{5}=\binom{12}{7}$ number of solutions (depending on your preferred notation, they are all equal).
How do we count something like $|A_1|$?
This corresponds to the system:
$\begin{cases} x_1+x_2+\dots+x_8=5\\ 4\leq x_1\\ 0\leq x_2\\ \vdots\\ 0\leq x_8\end{cases}$
Making a change of variable:
$\begin{cases} y_1+y_2+\dots+y_8=1\\ 0\leq y_1\\ 0\leq y_2\\ \vdots\\ 0\leq y_8\end{cases}$
and thus has a total of $\binom{1+8-1}{8-1}=\binom{8}{7}=8$ solutions.
How do we count something like $|A_{1,2}|$?
This corresponds to the number of solutions to the following system:
$\begin{cases} x_1+x_2+\dots+x_8=5\\ 4\leq x_1\\ 4\leq x_2\\ 0\leq x_3\\ \vdots\\ 0\leq x_8\end{cases}$
We could approach similarly to before by making a change of variable, but we can stop early this time since we can already see that there are no solutions since it is impossible for them to sum to five (their sum will be at least eight).
Putting all of this together, we have for the specific problem at hand:
$\binom{12}{5}-8\cdot 8$ solutions. The above method generalizes to any set of upper-bounds. Be warned that if there is not a great deal of symmetry with the upper bounds, each term of the inclusion-exclusion expansion may need to be dealt with individually. In the current problem, as the upper bound was the same for each, we had $|A_1|=|A_2|=\dots=8$, and $|A_{1,2}|=\dots=0$ making for quick simplifications.