Results 1 to 6 of 6

Math Help - counting: sum of 1..1000015, how many numbers are there?

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    20

    [solved] counting: sum of 1..1000015, how many numbers are there?

    i have an advanced counting problem:

    given the intergers 1..1000015, how many intergers are there, whose sum of digits equals 15?

    i solved this problem brute force in ocaml, but this wasn't really the task ^^ (solution is 13992)

    i think that i have to use the formula for the problem which can be illustrated by asking: " how many possibilites are there to give n coins to m children?"
    formula:
    {m+n-1 \choose n-1}

    i have no clue how to apply the formula to my current problem.
    Last edited by dayscott; December 13th 2009 at 10:36 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2
    I can see 2 ways to count the # of solutions. In both of these, I count from 0 to 999,999 and manually count the number of ways from 1,000,000 to 1,000,015.

    First, list the number of ways to write 15 = 9+6 =8+7, = 5+5+5, etc. Then find the number of ways to put these digits into the 6 slots that form the numbers from 0-999,999. for instance, there are 6 choose 2 ways to put a 9 and a 6 into a list of 6 slots. The other slots are 0. This way seems a bit tedious.

    The 2nd way is to consider the number 15 as 15 coins, and the division between digits as lines that you insert between coins. There should be 5 lines, making 20 items total. Then the number of ways to insert 5 lines into 20 slots is 20 choose 5. The resulting number is the number of coins between lines. For instance, line, coin, coin, line, line, coin is the number 0201. The bad point about this method is that you might have 15 coins between 2 lines, indicating a digit with value 15. There is of course no such digit base 10.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by dayscott View Post
    i have an advanced counting problem:

    given the intergers 1..1000015, how many intergers are there, whose sum of digits equals 15?

    i solved this problem brute force in ocaml, but this wasn't really the task ^^ (solution is 13992)

    i think that i have to use the formula for the problem which can be illustrated by asking: " how many possibilites are there to give n coins to m children?"
    formula:
    {m+n-1 \choose n-1}

    i have no clue how to apply the formula to my current problem.
    Here is an approach via generating functions.

    By inspection, there are no solutions in the range 1,000,000 to 1,000,015.
    So consider the equation

    x_1 + x_2 + x_3 + \dots + x_6 = r

    where 0 \leq x_i \leq 9 for all i, with x_i an integer.

    We want the number of solutions when r = 15. But let's see if we can solve the more general problem. So let the number of solutions be a_r, and define f(x) = \sum_{r=0}^{\infty} a_r x^r. It's easy to see that
    f(x) = (1 + x + x^2 + \dots + x^9)^6 = [(1-x^{10}) (1-x)^{-1}]^6 = (1-x^{10})^6 \cdot (1-x)^{-6}.
    (If you have trouble seeing this, think about what happens when you expand (1 + x + x^2 + \dots + x^9)^6).

    Applying the binomial theorem,
    f(x) = \sum_i (-1)^i \binom{6}{i} x^{10i} \cdot \sum_j \binom{6+j-1}{j} x^j.
    Extracting the coefficient of x^{15}, we find that

    a_{15} = \binom{20}{15} - \binom{6}{1} \binom{10}{5} = 13,992
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,390
    Thanks
    1476
    Awards
    1
    Quote Originally Posted by awkward View Post
    By inspection, there are no solutions in the range 1,000,000 to 1,000,015.
    ok
    Last edited by Plato; December 13th 2009 at 02:57 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    .
    Last edited by Defunkt; December 13th 2009 at 02:39 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2009
    Posts
    20
    excercise has been solved:

    you just count {20 \choose 15} = 15504 than you subtract {9 \choose 5}+ {8 \choose 4}+{7 \choose 3}+{6 \choose 2}+{5 \choose 1} + {4 \choose 0}

    explanation of {9 \choose 5} which is {5-1+5 \choose 5} is: you have got 5 which you have to distribute to 5 digits.

    thx for help!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. counting numbers...
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: November 14th 2011, 04:58 PM
  2. Counting Numbers
    Posted in the Statistics Forum
    Replies: 3
    Last Post: September 6th 2011, 05:51 PM
  3. Set of all counting numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 16th 2009, 05:43 PM
  4. Integers and counting numbers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 15th 2009, 08:52 PM
  5. counting numbers
    Posted in the Algebra Forum
    Replies: 4
    Last Post: September 16th 2006, 02:11 PM

Search Tags


/mathhelpforum @mathhelpforum