8
$\begingroup$

Calculate how many natural numbers $n$ where $ 0\leq n \leq 10,000,000$ such that the sum of their digits is AT MOST $34$

And I said the following:

We have 8 digits in numbers between $0$ and $10,000,000$. For the first digit there can be only $0$ or $1$. For all rest digits we have all possibilties $[0,...,9]$. So let us do a generating function: $F(x) = (1+x)(1+x+x^2+...+x^9)^7$. We are searching for the coefficients of $1$ and $x$ and $...$ and $x^{34}$. But that is like searching for the coefficient of $x^{34}$ in the generating function $G(x) = (1+x+x^2+...)(1+x)(1+x+x^2+...+x^9)^7$

But how do I continue from there? How can I know the coefficient of $x^{34}$ in $G(x)$?

$\endgroup$
  • 1
    $\begingroup$ It would be wiser to set the case $n=10,000,000$ apart, find the coefficient of $x^{34}$ in $(1+x+\cdots+x^9)^7$, and add one at then end (what you describe in the question instead counts numbers $0\leq n\leq19,999,999$). $\endgroup$ – Marc van Leeuwen May 14 '13 at 11:47
  • 2
    $\begingroup$ Also note that you title says "is at most $34$" but the body of you question contradicts this by saying "is $34$". But then later "coefficients of $1$ and $x^2$ and.. $x^{34}$" suggests the title has it right (but in that case you also want the coefficient of $x^1$). $\endgroup$ – Marc van Leeuwen May 14 '13 at 11:48
  • $\begingroup$ Fixed it. it is "at most." And I did not understand your point $\endgroup$ – TheNotMe May 14 '13 at 11:54
  • 3
    $\begingroup$ @TheNotMe : What he means is that instead of counting those $n$ between $0$ and $10,000,000$ that satisfy the property, since $n=10,000,000$ doesn't satisfy the property, might as well assume $0 \le n \le 9,999,999$ because the generating function is easier to construct when you assume that. $\endgroup$ – Patrick Da Silva May 14 '13 at 11:56
  • 1
    $\begingroup$ @PatrickDaSilva: Actually with the corrected question $n=10,000,000$ does satisfy the condition, but I proposed to still concentrate on counting the other solutions (since this is simpler) and then just add one at the end for the one omitted solution. (But my first comment was incoherent in that it talked about the coefficient of $x^{34}$ only). $\endgroup$ – Marc van Leeuwen May 14 '13 at 11:59
4
$\begingroup$

In comments you have correctly reduced the question to determining the coefficient of $x^{34}$ in $(1-x^{10})^7(1-x)^{-8}$. We can reduce modulo $x^{35}$, in which case the first factor becomes $1-\binom71x^{10}+\binom72x^{20}-\binom73x^{30}=1-7x^{10}+21x^{20}-35x^{30}$. Then it suffices to determine in the factor $(1-x)^{-8}$ the terms of degree $34-10k$ for $k=0,1,2,3$, which can be seen to be repectively $\binom{-8}{34}(-x)^{34}=\binom{41}7x^{34}=22481940x^{34}$, $\binom{-8}{24}(-x)^{24}=\binom{31}7x^{24}=2629575x^{24}$, $\binom{21}7x^{14}=116280x^{14}$, and $\binom{11}7x^4=330x^4$. Utlimately I find the coefficient $$ 22{,}481{,}940x-7\times2{,}629{,}575+21*116{,}280-35*330=6{,}505{,}245. $$ Just a sanity check: that's more than half of all numbers $n<10^7$; indeed the average sum of $7$ digits is $7\times4.5=31.5$, so it is more likely the sum is at most $34$ than the contrary. The final outcome of course is $6{,}505{,}245+1=6{,}505{,}246$.

$\endgroup$
  • 1
    $\begingroup$ Another easy and more precise sanity check can be obtained by a gaussian approximation: each digit has mean 4.5 and variance 33/4, the sum is approximately normal with $\mu=31.5$,$\sigma=7.6$, which we integrate till $x=34.5$, which gives $0.6534678$ $\endgroup$ – leonbloy May 14 '13 at 14:09
  • $\begingroup$ Just noting out that in the 3rd line, the sign of ${7 \choose 3 }\cdot x^{30}$ should be $-$ and not $+$. Please edit! $\endgroup$ – TheNotMe Jun 30 '13 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.