0

For how many natural numbers smaller then one million the sum of their digits is:

  1. $5$?
  2. a maximum of $6$?
  3. $47$?

The answers:

  1. ${5+6-1\choose 6-1}$
  2. ${5+7-1 \choose 7-1}$
  3. ${7+6-1 \choose 6-1}$

Can you help with understanding why they are correct?

user7777777
  • 453
  • 1
    Please check that I edited your question correctly. Does it say what you meant? – John Jan 13 '14 at 18:18
  • @John: I'm unable to make out the meaning in the Question. Perhaps we should wait for the OP to clarify before tidying things up. – hardmath Jan 13 '14 at 18:43
  • @user7777777 are you asking three separate questions? 1) For how many natural numbers, less than 1 million, is the sum of the digits equal to 5? 2) For how many natural numbers, less than 1 million, is the sum of the digits a maximum of 6? 3) For how many natural numbers, less than 1 million, is the sum of the digits equal to 47? Also, what do the answers mean? What is the definition of $C(m,n)$? – John Jan 13 '14 at 18:51
  • @ John, yes I'm asking three separate questions – user7777777 Jan 13 '14 at 19:12
  • A similar question has been asked recently. – Lucian Jan 14 '14 at 04:30

1 Answers1

1

  1. If a number is "smaller than one million", then we can write it using $6$ digits (perhaps with some leading zeroes). So $001310$ would be one such number, but we would typically write it $1310$. Fortunately, the presence of leading zeroes does not affect the sum of the digits.

    From here, these answers come from a stars and bars argument. The digits sum to $5$, so we have $5$ stars, and we can place the stars into six bins: bin $i$ containing $d$ stars if the $i$-th digit is $d$. The boundary of the bins are represented using bars. So the number $001310$ would correspond to $$\overbrace{ \phantom{\star}}^{0}|\overbrace{ \phantom{\star}}^{0}|\overbrace{\star}^1|\overbrace{\star\star\star}^3|\overbrace{\star}^1|\overbrace{ \phantom{\star}}^{0} \qquad\leftrightarrow\qquad 1310.$$ Other examples are: $$\overbrace{\star}^{1}|\overbrace{ \phantom{\star}}^{0}|\overbrace{\star}^1|\overbrace{\star}^1|\overbrace{\star}^1|\overbrace{\star}^1 \qquad\leftrightarrow\qquad 101111$$ and $$\overbrace{ \phantom{\star}}^{0}|\overbrace{ \phantom{\star}}^{0}|\overbrace{ \phantom{\star}}^{0}|\overbrace{ \phantom{\star}}^{0}|\overbrace{ \phantom{\star}}^{0}|\overbrace{\star\star\star\star\star}^{5} \qquad\leftrightarrow\qquad 5$$

    There are $5$ stars and $6-1=5$ bars, so we choose to position of the the $6-1$ bars, thus giving $\binom{5+6-1}{6-1}$.

  2. if we have the sum of digits being "a maximum of 6", we can introduce a "rubbish bin": stars in this bin are ignored. For example $$\underbrace{\overbrace{\star\star}^2}_{\text{ignore}}|\overbrace{ \phantom{\star}}^{0}|\overbrace{ \phantom{\star}}^{0}|\overbrace{\star}^1|\overbrace{\star}^1|\overbrace{\star}^1|\overbrace{ \phantom{\star}}^{0} \qquad\leftrightarrow\qquad 1110.$$

  3. The method is the same as in part 1., except instead of bin $i$ having $d$ stars implying the $i$-th digit is $d$, it implies the $i$-th digit is $9-d$. We have $6 \times 9=54$ is the maximum digit sum, and we subtract a total of $7$ from these digits to get a digit sum of $47$.

Rebecca J. Stones
  • 26,845