Question is : Find all $5$-digit numbers that sum of digits is $25$.
I write this:
All numbers like $\overline {a_{1}a_{2}a_{3}a_{4}a_{5}}$ that
$a_{1}+a_{2}+a_{3}+a_{4}+a_{5}=25$.
constraint is:
$ a_1 = 1,\cdots, 9\qquad a_i = 0,\cdots,9 \quad ; \quad\forall i\in\{2,3,4,5\}$.
The related generating function is:
\begin{align}
f(x)&=\left(x+x^2+\cdots+x^9\right)\cdot\left(1+x+x^2+\cdots+x^9\right)^4 \\
&=x\cdot\left(1+x+x^2+\cdots+x^8\right)\cdot\left(1+x+x^2+\cdots+x^9\right)^4\\
&=x\cdot\frac{1-x^9}{1-x}\cdot\left(\frac{1-x^{10}}{1-x}\right)^4\\
&=x\cdot\left(1-x^9\right)\cdot\left(1-x^{10}\right)^4\cdot\frac{1}{(1-x)^5}\\
&=x\cdot\left(1-x^9\right)\cdot(1 – 4 x^{10} + 6 x^{20} – 4 x^{30} + x^{40})\cdot
\sum_{k=0}^{\infty}{\left[\binom{4}{0}+\binom{5}{1}x+\binom{6}{2}x^2+\binom{7}{3}x^3+\cdots\right]}.
\end{align}
Coefficient of $x^{25}$:
| Product | ||||
|---|---|---|---|---|
| $x$ | $1$ | $1$ | $\binom{28}{24}x^{24}$ | $\binom{28}{24} \times x^{25}$ |
| $x$ | $1$ | $-4x^{10}$ | $\binom{18}{14}x^{14}$ | $-4 \times \binom{18}{14} \times x^{25}$ |
| $x$ | $1$ | $6x^{20}$ | $\binom{8}{4}x^{4}$ | $6 \times \binom{8}{4} \times x^{25}$ |
| $x$ | $-x^9$ | $1$ | $\binom{19}{15}x^{15}$ | $-\binom{19}{15} \times x^{25}$ |
| $x$ | $-x^9$ | $-4x^{10}$ | $\binom{8}{4}x^{4}$ | $4 \times \binom{8}{4} \times x^{25}$ |
So, the answer is:
$$
\binom{28}{24} – 4\binom{18}{14} + 6\binom{8}{4} – \binom{19}{15} + 4\binom{8}{4} = 5059
$$
But, I write all answers of the question in Excel and true answer is $5283$. What part of above answer is wrong?
Best Answer
Look at your last term. $x ( -x^9)(-4x^{10}) { 8 \choose 4} x^4$ gives you $x^{24}$ not $x^{25}$.
Fixing the incorrect value to ${ 9 \choose 5 } x^5$, the total becomes 5283.
If you're starting to learn about Generating Functions, I encourage you to relate it back to what you know with other forms of counting. In this case, if we approached it via Principle of Inclusion and Exclusion, what expression would we get?