How many integer solutions are there for the equation $c_1 + c_2 + c_3 + c_4 = 25$, where $c_i \ge 0$ for all $1 \le i \le 4$

Question

Question Statement: How many integer solutions are there for the equation $c_1 + c_2 + c_3 + c_4 = 25$, where $c_i \ge 0$ for all $1 \le i \le 4$.

I would like to solve this problem using combinatorics and I've read generating functions can be used as a method to find the solution. However, I have no idea how to do this.

My first attempt at solving this problem is below,

Observe the missing constraint $c_i \le 21$. The solution can be obtained by reasoning using Principle of Exclusion and Inclusion.

Applying the theorem to the above problem yeilds,

$N(\bar{c_1}\bar{c_2}\bar{c_3}\bar{c_4}) = N - \sum N(c_i) + \sum N(c_i c_j) - \sum N(c_i c_j c_k) + \sum N(c_1 c_2 c_3 c_4)$

For all $i,j,k = 1,...,4$.

Since, $N=H(4,25)=C(28,25)$, $N(c_i)=H(4,4)=C(7,4)$ and $N(c_i c_j) = N(c_i c_j c_k) = N(c_1 c_2 c_3 c_4) = 0$. Hence, the result is 3248.

Answer 1

Generating functions is the hard way for this question, but here goes.

The answer is the coefficient of $x^{25}$ in $(1+x+x^2+\cdots)^4$. We find $$(1+x+x^2+\cdots)^4=(1-x)^{-4}={3\choose0}+{4\choose1}x+{5\choose2}x^2+\cdots$$ so the answer is ${28\choose25}={28\choose3}=3276$.

Answer 2

Generating Function Method

Associate to each variable the polynomial $p(x) = \sum_{i=0}^{25} x^i$. Then the product $$ \left(p(x)\right)^4 = 1 + 4 x + 10 x^2 + \cdots + 3276 x^{25} + \cdots $$ exhibits the fact that there are $3276$ solutions to the equation. It also exhibits the number of solutions of \begin{align*} c_1 + c_2 + c_3 + c_4 &= 0 & :& & 1 \\ c_1 + c_2 + c_3 + c_4 &= 1 & :& & 4 \\ c_1 + c_2 + c_3 + c_4 &= 2 & :& & 10 \\ & & \vdots& & \end{align*} Our polynomial encodes the choices for the variable in the powers of $x$, so we have one term for each of the integers $0$ through $25$. When you multiply two of these polynomials, you get generic terms $x^i x^j$ for $0\leq i,j \leq 25$. But consider the terms we get for $i+j = 5$, for instance, they are $$ x^0 x^5, x^1 x^4, x^2 x^3, x^3 x^2, x^4 x^1, x^5 x^0, $$ that is, we have one term in the product for each way to write $5$ as a sum of two nonnegative integers, so the resulting product of two polynomials records the number of ways to produce $n$ as the sum of two nonnegative integers in the coefficient of $x^n$. Multiplying in the other two polynomials, the coefficient of $x^n$ records the number of ways to write $n$ as the sum of four nonnegative integers (each less than $25$).

(One might wonder how to compute that massive product. You don't, exactly. You only need terms of degree up to $25$ throughout the computation, so you only keep track of the leading terms and ignore the rest. For me, this computation went as \begin{align*} p^1 &= 1 + x + x^2 + \cdots + x^{25} + \text{(don't care)} \\ p^2 &= 1 + 2x + 3x^2 + \cdots + 26 x^{25} + \text{(don't care)} \\ p^3 &= 1 + 3x + 6x^2 + \cdots + 351 x^{25} + \text{(don't care)} \\ p^4 &= 1 + 4x + 10x^2 + \cdots + 3276 x^{25} + \text{(don't care)} \end{align*} It helped that I am familiar with figurate numbers and recognized the coefficients were, successively, constantly one, sequential integers, sequental triangular numbers, and sequential tetrahedral numbers.)

Answer 3

Two methods to solve this are "Stars and Bars" and Generating Functions.

---

Stars and Bars

we put $25$ $\star$s and $3$ $|$s to separate the $\star$s into $4$ areas. For example, $6+4+8+7$ would be represented by $$ \overbrace{\star\star\star\star\star\,\star}^6|\overbrace{\star\star\star\,\star}^4|\overbrace{\star\star\star\star\star\star\star\,\star}^8|\overbrace{\star\star\star\star\star\star\star}^7 $$ each arrangement of the $25$ $\star$s and $3$ $|$s will give a unique sum. The number of such arrangements is $$ \binom{28}{3}=3276 $$

---

Generating Functions

Each choice of $x_k$ so that $x_1+x_2+x_3+x_4=25$ corresponds to an $x^{25}$ term of $$ \overbrace{\left(1+x+x^2+\cdots\right)}^{\frac1{1-x}}\overbrace{\left(1+x+x^2+\cdots\right)}^{\frac1{1-x}}\overbrace{\left(1+x+x^2+\cdots\right)}^{\frac1{1-x}}\overbrace{\left(1+x+x^2+\cdots\right)}^{\frac1{1-x}} $$ and since $$ \begin{align} (1-x)^{-4} &=\sum_{k=0}^\infty\binom{-4}{k}(-x)^k\\ &=\sum_{k=0}^\infty\binom{k+3}{3}x^k \end{align} $$ the coefficient of $x^{25}$ is $$ \binom{28}{3}=3276 $$