I need to find the amount of numbers between $1$ and $10^k$ (k-digits number) that their digits sum is not more than $r$.
I saw some questions solving similar problems, using generating functions, all of them used the generating function of the form: $F(x)=x+x^2+x^3...+x^9$.
I wonder how is it relevant to this question? How can I use it to solve this?
Many thanks!
On
We calculate the number of integers $1\leq x\leq 10^k, (k\geq 1)$ which have digit-sum $\leq r$ with the help of generating functions.
We have to consider all positive integers with $m$ digits, $1\leq m\leq k$ and the number $10^k$ which has $k+1$ digits and digit-sum $1$.
Left-most digit $1,\ldots,9$: We do not have leading zeros, so we encode the left-most digit as \begin{align*} x+x^2+\cdots+x^9=x\frac{1-x^{9}}{1-x} \end{align*}
$m-1$ digits $0,\ldots,9$: We encode the $m-1$ following digits as \begin{align*} \left(1+x+\cdots+x^9\right)^{m-1}=\left(\frac{1-x^{10}}{1-x}\right)^{m-1} \end{align*}
sum of digits via $\frac{1}{1-x}$: It is helpful to know that multiplication of a series $A(x)=a_0+a_1x+a_2x^2+a_3x^3+\cdots$ with $\frac{1}{1-x}$ transforms the series into \begin{align*} \frac{1}{1-x}A(x)=a_0+\left(a_0+a_1\right)x+\left(a_0+a_1+a_2\right)x^2+\left(a_0+a_1+a_2+a_3\right)x^3+\cdots \end{align*} so that the coefficient of $x^{n}$ is the sum $a_0+a_1+\cdots+a_n$. We use this technique to calculate the digit-sums $\leq r$ by multiplication of $\frac{1}{1-x}$ and extracting the coefficient of $x^r$.
Addition of $1$: We finally have to consider the number $10^k$ having $k+1$ digits and digit-sum $1$. We respect this by adding $1$.
It it convenient to use the coefficient of operator $[x^r]$ to denote the coefficient of $x^r$ of a series. We are now well-prepared to do the calculation.
We obtain \begin{align*} \color{blue}{[x^r]}&\color{blue}{\sum_{m=1}^k x\frac{1-x^9}{1-x}\left(\frac{1-x^{10}}{1-x}\right)^{m-1}\frac{1}{1-x}+1}\tag{1}\\ &=[x^{r-1}]\frac{1-x^9}{(1-x)^2}\sum_{m=1}^k\left(\frac{1-x^{10}}{1-x}\right)^{m-1}+1\tag{2}\\ &=[x^{r-1}]\frac{1-x^9}{(1-x)^2}\sum_{m=0}^{k-1}\left(\frac{1-x^{10}}{1-x}\right)^{m}+1\tag{3}\\ &=[x^{r-1}]\frac{1-x^9}{(1-x)^2}\,\frac{1-\left(\frac{1-x^{10}}{1-x}\right)^k}{1-\frac{1-x^{10}}{1-x}}+1\tag{4}\\ &=[x^r]\left(\frac{\left(1-x^{10}\right)^k}{(1-x)^{k+1}}-\frac{1}{1-x}\right)+1\tag{5}\\ &=[x^r]\frac{\left(1-x^{10}\right)^k}{(1-x)^{k+1}}\tag{6}\\ &=[x^r]\sum_{j=0}^\infty\binom{-(k+1)}{j}(-x)^j\left(1-x^{10}\right)^k\tag{7}\\ &=\sum_{j=0}^r\binom{k+j}{k}[x^{r-j}]\left(1-x^{10}\right)^k\tag{8}\\ &=\sum_{j=0}^r\binom{k+r-j}{k}[x^j]\sum_{q=0}^k\binom{k}{q}(-1)^qx^{10q}\tag{9}\\ &=\sum_{j=0}^{\lfloor r/10\rfloor}\binom{k+r-10j}{k}[x^{10j}]\sum_{q=0}^k\binom{k}{q}(-1)^qx^{10q}\tag{10}\\ &\,\,\color{blue}{=\sum_{j=0}^{\lfloor r/10\rfloor}\binom{k+r-10j}{k}\binom{k}{j}(-1)^j}\tag{11} \end{align*}
Comment:
In (1) we put the factors together accoding to the introduction above and want to extract the coefficient of $x^r$. We also add $1$ to respect $10^k$.
In (2) we do some rearrangements and apply the rule $[x^p]x^qA(x)=[x^{p-q}]A(x)$.
In (3) we shift the index to start with $m=0$.
In (4) we use the finite gemetric series formula.
In (5) we do some simplifications and apply the rule as in (2).
In (6) we use $[x^r]\frac{1}{1-x}=[x^r]\left(1+x+\cdots +x^r+\cdots \right)=1$.
In (7) we use the binomial series expansion.
In (8) we apply the binomial identity $\binom{-p}{q}=\binom{p+q-1}{p-1}(-1)^q$ and apply the rule as in (2). We also set the upper limit of the sum to $r$ since values $j>r$ do not contribute.
In (9) we change the order of summation $j\to r-j$ and expand the binomial, noting that the powers are multiples of $10$.
In (10) we restrict the index $j$ to multiples of $10$.
In (11) we finally select the coefficient of $x^{10j}$.
Two small examples:
Example $r=5, k=2$: (one summand)
The number of integers $x$ with $1\leq x\leq 10^2=100$ with digit-sum $\leq 5$ is \begin{align*} \left|\{1,2,3,4,5,10,11,12,13,14,20,21,22,23,30,31,32,40,41,50,100\}\right|=5+5+4+3+2+1+1\color{blue}{=21} \end{align*} We obtain from (12) \begin{align*} \sum_{j=0}^{\lfloor 5/10\rfloor}\binom{2+5-10j}{2}\binom{2}{j}(-1)^j=\binom{7}{2}\binom{2}{0}(-1)^0=\binom{7}{2}\color{blue}{=21} \end{align*}
Example $r=11, k=2$: (two summands)
The number of integers $x$ with $1\leq x\leq 10^2=100$ with digit-sum $\leq 11$ is \begin{align*} &\left|\{1,2,\ldots,9,10,11,\ldots,19,20,21,\ldots,29,30,31,\ldots,38,40,41,\ldots,47,\right.\\ &\qquad\left.50,51,\ldots,56,60,61,\ldots,65,70,71,\ldots,74,80,81,\ldots,83,90,91,92,100\}\right|\\ &\qquad=9+10+10+9+8+7+6+5+4+3+1\color{blue}{=72} \end{align*} We obtain from (12) \begin{align*} \sum_{j=0}^{\lfloor 11/10\rfloor}\binom{2+11-10j}{2}\binom{2}{j}(-1)^j&=\binom{13}{2}\binom{2}{0}-\binom{3}{2}\binom{2}{1}\\ &=78\cdot1-3\cdot 2\color{blue}{=72} \end{align*}
Yeah, that should work out fine for you (after a few corrections).
The basic idea is that you can create a correspondence between the number $1089$ and the term $x^1x^0x^8x^9$ and if you iterated over a range of numbers the coefficient of $x^{18}$ in your sum would be the number of integers in that range that had a digit sum of $18$.
In your case, you want to calculate $$\prod_{n=1}^k(1+x+x^2+x^3+x^4+x^5+x^6+x^7+x^8+x^9)$$ and then add all of the coefficients up through $x^r$. Note that you want to include a term of $1$ because that corresponds to a digit of $0$ in the numbers you are considering.