# 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.

• @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