1
$\begingroup$

Let $k$ be a positive integer. $\left \{ a_r \right \} _{r=0}^{\infty}$ is the number of integers which exist between $0$ and $10^k$ (i.e integers with no more than $k$ digits), such that the sum of their digits is no more than $r$.

Find the generating function for $\left \{ a_r \right \} _{r=0}^{\infty}$.

A very similar question has been asked here.

It is clear to me that we can define $f(x) = (1+x+x^2+\dots+x^9)^{k}$ and this would be a generating function for the problem "how many integers exist with exactly the sum $r$". Meaning that would be the coefficient of $x^r$.

So using this I believe we can express $a_r$, but the question is to find a generating function for $a_r$.

So is this still a good direction, or should I think about the problem differently?

$\endgroup$
1
  • 1
    $\begingroup$ Markus Scheuer’s answer to the question to which you linked contains the generating function that you want: just remove the initial $[x^r]$ (and the final $+1$, if you don’t want to include $10^k$) from the first blue expression. The reasoning is in the material above the formula. $\endgroup$ May 30, 2020 at 16:15

1 Answer 1

1
$\begingroup$

If we denote the number of integers with sum no more than $r$ by $a_r$ and the number of integers with sum exactly $r$ by $b_r$, we have

$$ a_r=\sum_{k=0}^rb_k\;. $$

You know the generating function for $b_k$. Summing a sequence corresponds to multiplying its generating function by $\sum_{k=0}^\infty x^k=\frac1{1-x}$. Thus the generating function you want is

$$ \frac{\left(1+\cdots+x^9\right)^k}{1-x}=\frac{\left(1-x^{10}\right)^k}{(1-x)^{k+1}}\;. $$

Note that this is also an intermediate result that Markus Scheuer arrived at in line $(6)$ in his answer to the question you linked to. He included $10^k$ instead of $0$, but the result is the same.

$\endgroup$
7
  • $\begingroup$ I lost you at "Summing a sequence corresponds to dividing its generating function by...". Can you explain what you mean by that? this material is pretty new to me $\endgroup$ May 30, 2020 at 16:48
  • $\begingroup$ @paxtibimarce: I added an intermediate step. Does that make it clearer? $\endgroup$
    – joriki
    May 30, 2020 at 16:50
  • $\begingroup$ I'm still not sure why summing a sequence is the same as multiplying its generating function by this sum. Is this something trivial or could you tell me where I could read about it maybe? $\endgroup$ May 30, 2020 at 16:56
  • 1
    $\begingroup$ I got it, very cool trick :) Thank you $\endgroup$ May 30, 2020 at 17:06
  • 1
    $\begingroup$ @paxtibimarce: \begin{eqnarray} \left[x^r\right]\frac{\left(1-x^{10}\right)^k}{(1-x)^{k+1}} &=& \left[x^r\right]\left(\sum_{j=0}^k\binom kj(-1)^jx^{10j}\right)\left(\sum_{m=0}^\infty\binom{k+m}kx^m\right) \\ &=& \sum_{j=0}^{\left\lfloor\frac r{10}\right\rfloor}\binom kj(-1)^j\binom{k+r-10j}k\;. \end{eqnarray} For $r=18$, this is $\binom{k+18}k-k\binom{k+8}k$. $\endgroup$
    – joriki
    May 30, 2020 at 18:03

You must log in to answer this question.

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