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.
Good question.
You cannot apply the same reasoning in the case when we have repetitions, because the $4!$ ways you can arrange $4$ objects assume different objects.
Let's look at your example of choosing $4$ objects from $10$ possible objects (with repetition) and say that our $10$ possible choices are letters A to J.
One possible permutation is ABBA
, which is different to the permutation BABA
. Now think about how many ways do we have to arrange two As and two Bs. It is not $4!$ (we do not have 4 ways to choose the first letter, nor 3 choices for the second letter etc).
In the extreme case where we have say CCCC
(this is one permutation), we also have only one combination.
So when you divide by $r!$, you are potentially overestimating the number of ways you can arrange the objects in a permutation, because you might have repeated objects in this permutation. Moreover, it is difficult to calculate the average arrangements because it depends on the permutation we have each time. So instead of trying to solve the problem this way, we attack it differently (stars and bars for example).
This method is not a problem when repetitions are not allowed because you can easily count the possible arrangements for any permutation. They are always the same, independent of the permutation we have.
Best Answer
You should think of your final example as the number of ways to choose $11$ objects, each of which is of one of $3$ types: $x_1$ is the number of Type $1$ objects that you choose, $x_2$ the number of Type $2$ objects, and $x_3$ the number of Type $3$ objects that you select. Thus, you have $r=11$ and $n=3$. This is actually very similar to your example with the fruit.
I prefer a slightly different model: $r$ is the number of indistinguishable objects that you’re distributing amongst $n$ numbered containers. The $r$ objects are the stars, and the $n$ containers are the spaces between $n-1$ bars. This fits your last example very well, and it’s not hard to make it fit your other examples as well. In your first example the types of fruit are the containers: imagine labelling a jar with each of the types and distributing $20$ pebbles amongst the $4$ jars to describe a given selection. In your second example the containers are the numbers $1,2,3$, and $4$, and you’re distributing $3$ pebbles amongst those containers.