3

How many natural numbers with $n$ digits are there, where the sum of their digits is $\leq 7$?

So I said the following:

For the first digit (MSB) we can't have a zero, and all the other $n-1$ digits they can be anything from $[0,..9]$ so I said: $F(x) = (x + x^2 + ... + x^9) \cdot (1 + x^2 + ... + x^9)^{n-1}$ and we are searching for the coefficients of $x^7, x^6, ... x$ But how do we exactly start solving this generating function?

TheNotMe
  • 4,841
  • $7$ is a pretty little number, you can calculate the exact formulae for sums of $1,...,7$ and add them. Or you are interested in the common approach? – gukoff May 13 '13 at 18:51
  • In a common approach of course! That's why I asked this! – TheNotMe May 13 '13 at 18:53
  • 3
    If you keep your sum of digits to be below 9, you can add $x^{10}, x^{11} , etc$ to each term of your generating functions, and hence simplify it as $ \frac { x}{(1-x)^n} $, which is easily calculated. – Calvin Lin May 13 '13 at 18:58

0 Answers0