Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

N digit numbers with sum s

  1. Aug 25, 2008 #1
    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.
     
  2. jcsd
  3. Aug 25, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Do you mean with digit sum s?
     
  4. Aug 26, 2008 #3
    Yes..
    eg: 231 is a 3 digit number with sum 6.
     
  5. Aug 26, 2008 #4

    uart

    User Avatar
    Science Advisor

    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 catagory zero or more times. This is in no way limited to s less than 10.
     
  6. Aug 26, 2008 #5

    uart

    User Avatar
    Science Advisor

    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
     
  7. Aug 26, 2008 #6
    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.
     
  8. Aug 26, 2008 #7

    uart

    User Avatar
    Science Advisor

    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.
     
    Last edited: Aug 26, 2008
  9. Aug 26, 2008 #8

    uart

    User Avatar
    Science Advisor

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

    I don't know the solution off-hand, but the problem re-statement might help.
     
    Last edited: Aug 26, 2008
  10. Aug 26, 2008 #9

    uart

    User Avatar
    Science Advisor

    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 catagory.
     
  11. Aug 26, 2008 #10

    uart

    User Avatar
    Science Advisor

    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 catagory, that is when s>=20.
     
    Last edited: Aug 26, 2008
  12. Aug 26, 2008 #11
    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.
     
  13. Aug 27, 2008 #12
    Maybe my approach was not right. Maybe we should try it from some other direction or something.
     
  14. Aug 28, 2008 #13
    No one has other ideas? :confused:
     
  15. Aug 30, 2008 #14

    uart

    User Avatar
    Science Advisor

    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.

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

    Where [itex]C(n,r)[/itex] is the usual combination function,
    [tex]C(n,r) = \frac{n!}{r!\,(n-r)!}[/tex]

    BTW. This is an extension of my first attempt which was equivalent to the first two terms of this summation.
     
  16. Aug 30, 2008 #15
    Can you please tell me how you got this formula?
     
  17. Aug 31, 2008 #16

    uart

    User Avatar
    Science Advisor

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?