[Math] How many numbers between $0$ and $999,999$ are there whose digits sum to $r$

combinatoricsgenerating-functions

How many numbers between $0$ and $999,999$ are there whose digits sum to $r$

In generating a function for the answer, here is what I came to.

We have a maximum of 6 number slots to use to sum to r.

Then $e_1 + e_2 + e_3 + e_4 + e_5 + e_6 = r$

And since each slot has the capacity to be a number between $0$ and $9$, then $e_i = (1 + x^1 + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9) $,

and the generating function is therefore $(1 + x^1 + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9)^6$.

Do I have this generating function correct?

Best Answer

Note: Your derivation of the generating function is perfectly valid.

The generating function has following representation \begin{align*} (1+x^1+x^2+\cdots+x^9)^6&=\left(\sum_{j=0}^9x^j\right)^6\\ &=\left(\frac{1-x^{10}}{1-x}\right)^6\\ &=1+6x+21x^2+56x^3+126x^4+252x^5+\cdots \end{align*}

The exponents of the terms vary from $0$ which corresponds to the smallest sum of digits $r=0$ and the number $0$ up to $54$ which corresponds to the largest sum of digits $r=54$ and the number $999999$.

We calculate the coefficient of $x^r$ of the generating series. In order to do so we use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.

We obtain for $0\leq r\leq 54$ \begin{align*} [x^r]\left(\frac{1-x^{10}}{1-x}\right)^6 &=[x^r](1-x^{10})^6\sum_{k=0}^{\infty}\binom{-6}{k}(-x)^k\tag{1}\\ &=[x^r]\sum_{j=0}^{6}\binom{6}{j}(-1)^jx^{10j}\sum_{k=0}^{\infty}\binom{k+5}{5}x^k\tag{2}\\ &=\sum_{j=0}^{\lfloor\frac{r}{10}\rfloor}\binom{6}{j}(-1)^j[x^{r-10j}]\sum_{k=0}^{\infty}\binom{k+5}{5}x^k\tag{3}\\ &=\sum_{j=0}^{\lfloor\frac{r}{10}\rfloor}(-1)^j\binom{6}{j}\binom{r-10j+5}{5} \end{align*}

Comment:

  • In (1) we use the binomial series representation

  • In (2) we expand the left binom and use the identity $\binom{-n}{k}=\binom{n+k-1}{k}(-1)^k$

  • In (3) we use the rule $[x^{r+s}]A(x)=[x^r]x^{-s}A(x)$ and keep care of the upper limit of the sum to not add anything when $r-10j<0$.

Related Question