How to find the coefficient without a calculator?

Question

I wanted to solve this question without using a calculator.

Question: The number of non-negative integer solutions to

$$3x+y+z=24$$

By creating generating functions you have to find the coefficient of $x^{24}$ in the expression: $$\left(\frac{1}{1-x}\right)^{2}\left(\frac{1}{1-x^3}\right)$$ Using the theory I know about now, I would just split the problem into smaller parts adding all the combinations together while using the extended binomial theorem. But this takes a lot of time and I was wondering if there is a faster/easier way to find coefficients in terms of multiple generating functions by hand? If so, what are some recommended places to read about it?

Answer 1

Here's an alternative approach that uses stars and bars instead of generating functions. Condition on the number of solutions with $x=k$, which reduces to the number of nonnegative integer solutions to $y+z=24-3k$: \begin{align} \sum_{k=0}^8 \binom{24-3k+2-1}{2-1} &= \sum_{k=0}^8 (25-3k) \\ &= 9\cdot 25 - 3\sum_{k=0}^8 k \\ &= 9\cdot 25 - 3\cdot 9 \cdot \frac{0+8}{2} \\ &= 9(25 - 12) \\ &= 117 \end{align}

Answer 2

Pen, paper, and effort is what is required outside of a computer to calculate higher terms in expansions. In this case \begin{align} \frac{1}{(1-x)^2} &= \sum_{n=0}^{\infty} (n+1) \, x^n \\ \frac{1}{1-x^3} &= \sum_{n=0}^{\infty} x^{3 n} \end{align} for which the product of these series gives $$ P = \frac{1}{(1-x)^2 (1-x^3)} = \sum_{r=0}^{\infty} (r+1) \, x^r \times \sum_{m=0}^{\infty} x^{3 m}. $$ Expanding to powers of $x^{24}$ gives \begin{align} P &= (1 + 2 x + 3 \, x^2 + \cdots + 25 \, x^{24})(1 + x^3 + \cdots + x^{24}) \\ &= \cdots + (1 + 4 + 7 + 10 + 13 + 16 + 19 + 22 + 25 ) \ x^{24} + \cdots \\ &= \cdots + 108 \, x^{23} + 117 \, x^{24} + 126 \, x^{25} + \cdots. \end{align} The resulting value is then $[x^{24}] P = 117$.

Answer 3

As the number 24 is reasonably small a direct approach (also called brute force method) would work and be transparent.

As $3x$ is a multiple of 3, it can take any value from $\{0,3,6,9,\dots,24\}$. For each such value count how many (ordered) pairs of non-negative integers $y,z$ give that sum.

The number of pairs of non-negative integers $y,z$ giving a prescribed positive integer $n$ as sum is easily found to be $n+1$.

So the final answer is $(0+1) +(3+1) + (6+1)+(9+1) +\cdots (24+1)$ . And this reduces to the well-known problem of summing an arithmetic progression. Actually this shows one can find the answer even for big RHS value like 9630, not just small 24.