Number of ways to distribute 15 indistinguishable balls to 7 kids such that each kid gets a maximum of 3 toys? I want to find the number of ways to distribute 15 indistinguishable balls to 7 kids such that each kid gets a maximum of 3 toys.
I tried splitting to different cases: first determining how many kids get 3 balls, then the number or kids that get 2, than the kids that get 1. But I got lost and it seemed to be too long anyway (this question was taken from an exam).
The answer is 728.
Any help would be appreciated.
 A: One approach is to use generating functions:
Assuming the kids are distinguishable, this is the coefficient of $x^{15}$ in the expansion of $(1+x+x^2+x^3)^7$ and is indeed $728$.
It would be possible to do the expansion manually in an exam.  A slight short-cut is to notice that by symmetry it is also the coefficient of $x^{3\times7-15}=x^6$ in the expansion of $(1+x+x^2+x^3)^7$ and that can be found from the table below.  Without the shortcut, this table would need nine more columns.
            0   1   2   3   4   5   6   ...
            _   _   _   _   _   _   _
0   :       1   0   0   0   0   0   0
1   :       1   1   1   1   0   0   0
2   :       1   2   3   4   3   2   1
3   :       1   3   6   10  12  12  10
4   :       1   4   10  20  31  40  44
5   :       1   5   15  35  65  101 135
6   :       1   6   21  56  120 216 336
7   :       1   7   28  84  203 413 728

where each term is the sum of the four values above to the left: for example $728=56+120+216+336$
A: Representation of the original problem -
$\displaystyle \sum\limits_{i=1}^{7} x_i = 15, 0 \leq x_i \leq 3$
To make the working easier, we now define  a variable $y_i = 3 - x_i$ and we derive $0 \leq y_i \leq 3$ from the original constraint. Please note that as the new variable $y_i$ varies from $0$ to $3$ for $i \in (1,7)$, the solutions directly map to permissible solutions of the original problem.
So we rewrite the problem as,
$\displaystyle \sum\limits_{i=1}^{7} (3-y_i) = 15, 0 \leq y_i \leq 3 \ $ or, $\displaystyle \sum\limits_{i=1}^{7} y_i = 6, 0 \leq y_i \leq 3$
Without restriction, we have ${{7 + 6 - 1} \choose {7-1}} = 924$ solutions.
Now for exclusions,

*

*There are $7$ combinations if one of the numbers is $6$.

*There are $7 \cdot 6 = 42$ combinations if one of the numbers is $5$ (one of the other numbers is $1$)

*If one of the numbers is $4$, we either have other number as $2$ which is $7 \cdot 6 = 42$ combinations or we have two other numbers that are $1$ each. That is $7 \cdot {6 \choose 2} = 105$ combinations.

So total number of valid solutions $ = 924 - (7 + 42 + 42 + 105) = \fbox{728}$.
A: As there are $15$ balls and $7$ children at least one child has to get $3$ balls. Let's count in how many ways we can distribute the balls depending on how many children get $3$ balls.

*

*$1$ child gets $3$ balls: then you have to distribute $12$ balls among $6$ children and each of them has to get at most (and actually exactly) $2$ balls. You can do this in $1$ way (the balls are indistinguishable);

*$2$ children get $3$ balls: we have to distribute $9$ balls among $5$ children and each of them has to get at most $2$ balls. You can do this in $5$ ways (you have to choose the one that gets $1$ ball);

*$3$ children get $3$ balls: we have to distribute $6$ balls among $4$ children and each of them has to get at most $2$ balls. You can do this in $4+6=10$ ways (either there is one child without any balls, or everyone has at least $1$ ball).

*$4$ children get $3$ balls: we have to distribute $3$ balls among $3$ children and each of them has to get at most $2$ balls. You can do this in $1+6 = 7$ ways (either there is a child without any balls, one with $1$ ball, and one with $2$, or everyone has $1$ ball).

*$5$ children get $3$ balls: there are no other balls to distribute.

Now let us sum the numbers taking into account the number of choices we have for which children get $3$ balls:
$$ 7 \cdot 1 + 21 \cdot 5 + 35 \cdot 10 + 35 \cdot 7 + 21 = 728.$$
