# How many possible sums of the digits of an n-digit number?

Suppose I have a seven-digit positive number (allowing leading zeroes): How might I go about finding the total number of possible sums of those seven digits?

My first instinct was to say it's simply $10^7$, as there are seven slots with ten possible choices per slot. But I instantly realized this would overcount by a great deal, because, for e.g.

 1234567 = 7654321 = 28


I'm currently thinking about $$\frac{10!}{(10-7)!} = \frac{10!}{3!}$$

as this would be the number of different combinations of seven digits. But won't this still overcount numbers such as

1220000 = 1400000 = 5


We've just begun to talk about partitioning and the pigeonhole principle in this class, and I'm wondering if the concept I'm looking for is found there. If so, please articulate why it is necessary.

HINT:

• What’s the smallest possible sum?
• What’s the largest possible sum?
• Can you make every sum between those extremes?
• Okay, interesting... the largest minus the smallest. But how do I prove that every possible value between them is reachable? – drew moore Dec 2 '14 at 4:58
• Ah, I see you've posed that very question in your edit... :) – drew moore Dec 2 '14 at 4:59
• @aqaeous: Not quite largest minus smallest: if the largest were $9$ and the smallest $0$, you’d have $10$ possibilities, not $9$. For your question: you can do it by induction on the number of digits. – Brian M. Scott Dec 2 '14 at 5:00
• Interesting point. So $max - min + 1$. My intuition is screaming about the similarity between this and the ${n + k -1 \choose k}$ formula for the number of combinations of size k with entries from a set of size n. Is that related to what we're talking about here? If it is, could you help me wrap my head around how so? – drew moore Dec 2 '14 at 5:05
• @aqaeous: No, not at all. This is just the simple (but useful) fact that if $m$ and $n$ are integers, and $m\le n$, then the number of integers in the interval $[m,n]$ is $m-n+1$. – Brian M. Scott Dec 2 '14 at 5:07

The smallest sum is $$0$$. The largest is $$9N$$, where $$N$$ is the number of digits in the number.

Suppose you want to show that the number $$47$$ is possible in a $$7$$-digit number. Well, $$47 = 9+9+9+9+9+2$$. So $$9999920 \mapsto 47$$. This should make it clear that every number from $$0$$ to $$9N$$ is achievable. So the answer is $$9N+1$$.

$$\begin{array}{c} \text{number} & \text{digit sum} \\ 000 \cdots 00 & 0 \\ 100 \cdots 00 & 1 \\ 200 \cdots 00 & 2 \\ \vdots \\ 900 \cdots 00 & 9 \\ \hline 910 \cdots 00 & 10 \\ 920 \cdots 00 & 11 \\ 930 \cdots 00 & 12 \\ \vdots \\ 990 \cdots 00 & 18 \\ \hline 991 \cdots 00 & 19 \\ 992 \cdots 00 & 20 \\ 993 \cdots 00 & 21 \\ \vdots \\ 999 \cdots 00 & 27 \\ \hline \vdots & \vdots \\ \hline 999 \cdots 90 & 9N-9 \\ 999 \cdots 91 & 9N-8 \\ 999 \cdots 92 & 9N-7 \\ \vdots \\ 999 \cdots 99 & 9N \\ \hline \end{array}$$