6
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ The methodology seems good and does yield the correct result, here $\endgroup$
    – lulu
    Commented Jun 1, 2023 at 13:18
  • $\begingroup$ Is 5283 the number of 5-digit numbers whose sum of digits is equal to 25? $\endgroup$ Commented Jun 1, 2023 at 13:25

1 Answer 1

3
$\begingroup$

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?

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .