Stars and Bars with a maximum number per tuple I have 4-tuples of numbers, each consisting of 1 to 10. How do I find the number of permutations possible to reach a total sum of 21? I tried using the formula given in https://en.wikipedia.org/wiki/Binomial_coefficient and plotted it against a graph, problem is, my graph should look like an n-shaped graph, but instead, I got an exponential graph instead.
 A: An approach using generating functions:
In order to count up the number of solutions that sum to $n$, we can look at the coefficient of $x^n$ in the generating function $f(x)$:
$$[x^{n}]f(x) = [x^{n}]\left(\sum_{n=1}^{10}x^n\right)^4$$
The $[x^n]$ operator refers to the coefficient of $x^n$.
Use the identity $\displaystyle \sum_{n=0}^{k}x^n = \frac{1-x^{k+1}}{1-x}$ to convert this expression:
$$[x^{n}]f(x) = [x^{n}]\left(\frac{1-x^{11}}{1-x} - x^0\right)^4 = [x^{n}]\left(\frac{x-x^{11}}{1-x}\right)^4$$
Simplify:
$$[x^{n}]f(x) = [x^{n}]\left(\frac{x^{44} - 4 x^{34} + 6 x^{24} - 4 x^{14} + x^4}{(1-x)^4}\right)$$
Factor out $\dfrac{1}{(1-x)^4}$ and use the identity $\displaystyle \frac{1}{(1-x)^{m+1}} = \sum_{n=0}^{\infty}\binom{n+m}{m}x^n$:
$$[x^{n}]f(x) = [x^{n}]\left(x^{44} - 4 x^{34} + 6 x^{24} - 4 x^{14} + x^4\right)\sum_{n=0}^{\infty}\binom{n+3}{3}x^n$$
Distribute:
$$[x^{n}]f(x) = [x^{n}]\left(\sum_{n=0}^{\infty}\binom{n+3}{3}x^{n+44}-4\sum_{n=0}^{\infty}\binom{n+3}{3}x^{n+34}+6\sum_{n=0}^{\infty}\binom{n+3}{3}x^{n+24}-4\sum_{n=0}^{\infty}\binom{n+3}{3}x^{n+14} + \sum_{n=0}^{\infty}\binom{n+3}{3}x^{n+4}\right)$$
Shift indices:
$$[x^{n}]f(x) = [x^{n}]\left(\sum_{n=44}^{\infty}\binom{n-41}{3}x^{n}-4\sum_{n=34}^{\infty}\binom{n-31}{3}x^{n}+6\sum_{n=24}^{\infty}\binom{n-21}{3}x^{n}-4\sum_{n=14}^{\infty}\binom{n-11}{3}x^{n} + \sum_{n=4}^{\infty}\binom{n-1}{3}x^{n}\right)$$
If we look at the lower bounds of the indices, the smallest $x^n$ that we could get the coefficient for is $x^{4}$. This is because $4$ is the smallest possible value of $n$ under the $x_i$ constraints, which occurs when each value of the tuple is $1$. The coefficients for all $n<4$ are simply $0$.
Now we can invoke the coefficient operator:
$$[x^n]f(x) = \binom{n-41}{3}-4\binom{n-31}{3}+6\binom{n-21}{3}-4\binom{n-11}{3}+\binom{n-1}{3}$$
Set $n=21$ to get the number of solutions to the original problem:
$$[x^{21}]f(x) = 660$$
