I have what I thought is a fairly simple problem: Count non-negative integer solutions to the equation
$$x_1 + x_2 + x_3 + x_4 + x_5 = 23$$
such that $0 \leq x_1 \leq 9$.
Not too hard, right? Simply ignore the upper-bound, count the
$$\begin{pmatrix}23 + (5-1) \\ (5-1)\end{pmatrix} = \begin{pmatrix}27 \\ 4\end{pmatrix} = 17550$$ solutions. Subtract from this all (non-negative integer) solutions to the equation
$$y_1 + 10 + x_2 + x_3 + x_4 + x_5 = 23,$$
and there are $\begin{pmatrix}17 \\ 4\end{pmatrix} = 2380$ of these "bad" solutions we shouldn't have counted earlier, but did. Thus we find $17550 – 2380 = 15170$ solutions.
Since this is a prohibitively large number of solutions to check by hand, I wrote a simple Python program to verify whether this answer is correct. It does indeed say there are $17550$ solutions without upper bounds, and $2380$ solutions to the equation for counting "bad" solutions.
However, when I ask it throw away all solutions to the non-upper-bounded problem for which $x_1 \geq 10$, it tells me it's found $15730$ solutions.
My question is: do I not understand the combinatorial calculation so that there are not actually $\begin{pmatrix}27\\4\end{pmatrix}-\begin{pmatrix}17\\4\end{pmatrix}$ solutions, or have I made some kind of programming mistake? Of course, both are also possible.
Best Answer
A nice way to mathematically check your work is with a generating function. We have $x_{1} \in \{0, ..., 9\}$. So our generating function for an $x_{1}$ is $\sum_{i=0}^{9} x^{i} = \dfrac{1-x^{10}}{1-x}$. The other terms don't have this restriction, so their generating functions are simply $\dfrac{1}{1-x}$.
So we multiply this result for each $x_{i}$ to get our generating function $f(x) = \dfrac{1-x^{10}}{(1-x)^{5}}$.
Using our binomial identities, we get $(1-x^{10}) = \sum_{i=0}^{1} \binom{1}{i} (-1)^{i} x^{10i} = (1 - x^{10})$
We then expand out the bottom term $\dfrac{1}{(1-x)^{5}} = \sum_{i=0}^{\infty} \binom{i + 5 - 1}{i} x^{i}$. And we multiply this with $(1 - x^{10})$, taking only terms $x^{23}$.
So that gives us $\binom{23 + 5 - 1}{23} - \binom{13 + 5 - 1}{13} = \binom{27}{4} - \binom{17}{4}$ as our answer.
Generating functions are nice, because they make it much easier to model the problem, and you don't have to crank out code and guess if it's right. Of course, seeing the stars and bars solution is nice, but takes more practice. Generating functions are more mechanical once you've figured out how to deal with them.