Digital orbit

We can count this using generating functions. We create a generating funciton where the exponent counts the digit sum and the coefficient counts how many numbers have that digit sum. For a single digit, the generating series is $1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9$ , so for 4 digits, the generating series will be $(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9)^4$ . We want the coefficient of $x^{15}$ from this expression. We provide 2 methods for calculating this.

Method 1:

We can write $(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9)^4$ as

$\begin{array}{cl} & (1+x^5)^4(1 + x + x^2 + x^3 + x^4)^4\\ = & (1 + 4x^5 + 6x^{10} + 4x^{15} + x^{20})(1 + 2x + 3x^2 + 4x^3 + 5x^4 + 4x^5 + 3x^6 + 2x^7 + x^8)^2\\ \end{array}$

Since we want the coefficient of $x^{15}$ from this expression, we just need the coefficients of $x^{15}, x^{10}, x^{5}, x^{0}$ from the second term, since only terms that multiply with terms from the first expression to give $x^{15}$ are relevant.

The coefficient of $x^{0}$ is 1.

The coefficient of $x^{5}$ is $1 \times 4+ 2 \times 5 + 3 \times 4 + 4 \times 3 + 5 \times 2 + 4 \times 1 = 52$ .

The coefficient of $x^{10}$ is $3 \times 1 + 4 \times 2 + 5 \times 3 + 4 \times 4 + 3 \times 5 + 2 \times 4 + 1 \times 3 = 68$ .

The coefficient of $x^{15}$ is $2 \times 1 + 1 \times 2 = 4$ .

So, the coefficient of $x^{15}$ in the whole expression is $1 \times 4 + 4 \times 68 + 6 \times 52 + 4 \times 1 = 592$ .

Method 2:

We can write $(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9)^4$ as $\left( \frac{1 - x^{10}} {1-x} \right)^4 = (x^{40} - 4x^{30} + 6x^{20} - 4x^{10} + 1)(1-x)^{-4}$

Since we want the coefficient of $x^{15}$ from the expression, we only need the coefficients of $x^{15}$ and $x^{5}$ from $(1-x)^{-4}$ to calculate this. Using the negative binomial theorem, the coefficient of $x^{15}$ is $\binom{18}{3} = 816$ and the coefficient of $x^{5}$ is $\binom{8}{3} = 56$ . So the coefficient of $x^{15}$ in the overall expression is $1 \times 816 + (-4) \times 56 = 592$