How Many N-Digit Numbers Have Sum S?

[T1000]

I want to calculate the amount of n digit numbers with sum s.
The idea was the number of ways to put s balls in n boxes. So there are C(n+s-1,n-1) ways to do that when n>1 and s<10. But this formula doesn't work when s>10.
I found a formula C(10n-s-1,n-1) that works for cases where s>=10 but I can't figure out how its obtained.

 

[HallsofIvy]

Do you mean with digit sum s?

 

[T1000]

Yes..
eg: 231 is a 3 digit number with sum 6.

 

[uart]

I want to calculate the amount of n digit numbers with sum s.
The idea was the number of ways to put s balls in n boxes. So there are C(n+s-1,n-1) ways to do that when n>1 and s<10. But this formula doesn't work when s>10.
I found a formula C(10n-s-1,n-1) that works for cases where s>=10 but I can't figure out how its obtained.

Can you please explain why you think that formula doesn't work for s>10?

C(n+s-1,n-1) gives the number of way of choosing s items from n catagories, where ordering of choices is unimportant and where you may choose from any category zero or more times. This is in no way limited to s less than 10.

 

[uart]

BTW. An example of the use of this formula might be something like the following :

Q. A shop sells three kinds of soft-drink, Lemonade, Coke and Ginger-Beer. Your are sent to the shop to buy a round of eleven drinks, in how many different ways can you do this?

A. Clearly the ordering is unimportant. That is, a round consisting of 7 cokes, 3 lemonade and 1 GB is clearly the same as one consisting of 3 lemonade 1 GB and 7 cokes etc. So C(n+s-1,n-1) is the appropriate formula to use.

Here n = 3 (number of categories) and s = 11 (number of items). So C(13,2) = 78 combinations of drinks.

Note that I just used the formula with s>10

 

[T1000]

I'm trying to get a formula to calculate the amount of n digit numbers with sum s.
The maximum value a digit can have is 9. When s>=10, using this formula the value of a digit can exceed 9.

 

[uart]

Ok, I thought it was all originally in relation to the "The idea was the number of ways to put s balls in n boxes" problem. In that case I think it was appropriate.

Yeah I see what you mean now, it was the digit sum thing that was the original problem and the ball in boxes thing was just the first attempt at solving it. My misunderstanding.

 

[uart]

So I think we can still reduce it to a "choose items from catagories" type of problem. I think the following is equivalent.

Choose s items from n catagories with ordering unimportant but the restriction that at most 9 items (0..9) can be chosen from any given category.

I don't know the solution off-hand, but the problem re-statement might help.

 

[uart]

I'm not 100% sure if this is correct but I just scratched out a quick solution and I think the following might work for s>=10

C(s+n-1,n-1) - n C(s+n-11,n-1)

The second term is supposed to subtract off all the combinations in which 10 or more items can get into a single category.

 

[uart]

I found a formula C(10n-s-1,n-1) that works for cases where s>=10 but I can't figure out how its obtained.

That formula is definitely incorrect. It's a little tedius but you can enumerate all the possiblilties for a small example like s=11 and n=3 and you get 8+9+10+9+8+7+6+5+4+3 = 69.

That formula gives C(18,2) = 153 so it must be wrong.

BTW. My solution gives C(13,2) - 3*C(3,2) = 69. It's correct for this case though I'm still not certain it works for all cases. I'm fairly certain it will work up to s=19, but I've got the feeling it might under-estimate the correction term (subtracted) when s is large enough to "overflow" more than one category, that is when s>=20.

 

[T1000]

You're right. Your formula does not work for cases where s>=20.
The formula C(10n-s-1,n-1) only works in cases where (10n-s) is generally less than 15.
Is this is a difficult problem? I thought it was an easy one which I couldn't do because I'm not strong in math.

 

[T1000]

Maybe my approach was not right. Maybe we should try it from some other direction or something.

 

[T1000]

No one has other ideas?

 

[uart]

No one has other ideas?

Yes I think I've cracked it.

Problem.

How many combinations (order unimportant) are there of "s" items drawn from "n" categories, when we can choose at most "m" items from each category.

Result.

\sum_{r=0}^{\lfloor s/m \rfloor} \, (-1)^r \, C(n,r) \, C(s+n-1-m r,n-1)

Where C(n,r) is the usual combination function,
C(n,r) = \frac{n!}{r!\,(n-r)!}

BTW. This is an extension of my first attempt which was equivalent to the first two terms of this summation.

 

[T1000]

Can you please tell me how you got this formula?

 

[uart]

Can you please tell me how you got this formula?

My working was pretty messy and I haven't formally proved it, but I can give a rough outline of how I arrived there.

I started with the standard proof of the C(s+n-1,n-1) formula, for the case where there is no limit on the number drawn from each category. Are you familiar with this method where you represent each possible combination as a different binary code? Take for instance the 11 soft drink problem I posted earlier when I gave the example of an order placed for 7 cokes, 3 lemonade and one ginger-beer. Once we agree on the order of the categories as for example "coke,lemon,ginger" then that particular order can be encoded as the binary number "0000000100010". The "s" zeros denote the repeated items in each category while the "n-1" ones represent the category boundaries. So in this case every different binary number constructed from 11 zeros and 2 ones represents a different possible round of 11 drinks and it's simply a matter of noting that there are C(s+n-1,n-1) different ways of placing the "n-1" ones.

Next I tried to account for the restriction that at most 9 items could be chosen from any given category (and later I generalized this from 9 to m). First I attempted to subtract away (from the earlier result) the number of combinations where a given category had 10 or more items. At first I just considered the case where s<=19 so that at most one category could equal or exceed 10 items. I imagined removing 10 zeros from the binary number and then forming all the combinations that I could with the remaining "s-10" zeros and "n-1" ones, then multiplying that by the number of ways that I could re-insert the block of 10 zeros. That's how I arrived at the C(s+n-1,n-1) - n C(s+n-11,n-1) formula.

When I analysed why this failed for n>=20 I realized that the "n C(s+n-11,n-1)" term incorrectly counted "the number of combinations where a given category had 10 or more items" when two or more categories each exceed 10 items. Eventually I worked out the correction that I needed to add to make the result hold for s<=29 (that is, a maximum of two categories exceeding 10 items) was to add C(n,2) C(s+n-21,n-1). I basically just proceded like this until I saw the pattern.