Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By Plato

Math Help - n balls in d bins (non-standard?)

  1. #1
    Newbie
    Joined
    Sep 2011
    Posts
    21

    n balls in d bins (non-standard?)

    In how many ways can we distribute n balls over d bins where bin i contains no more balls than bin i-1 (i = 2,..., d)?

    For instance with n = 4 balls and d = 3 bins, the solution is 4: (4, 0, 0), (3, 1, 0), (2, 2, 0) and (2, 1, 1). Matlab generated the table below (rows fix d, columns fix n).

    Can anybody help me with an explicit formula?

    Thanks in advance,
    Sander

    d\n 1 2 3 4 5 6 7 8 9 10
    1 1 1 1 1 1 1 1 1 1 1
    2 1 2 2 3 3 4 4 5 5 6
    3 1 2 3 4 5 7 8 10 12 14
    4 1 2 3 5 6 9 11 15 18 23
    5 1 2 3 5 7 10 13 18 23 30
    6 1 2 3 5 7 11 14 20 26 35
    7 1 2 3 5 7 11 15 21 28 38
    8 1 2 3 5 7 11 15 22 29 40
    9 1 2 3 5 7 11 15 22 30 41
    10 1 2 3 5 7 11 15 22 30 42


    Last edited by sander; March 18th 2012 at 03:49 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,966
    Thanks
    1785
    Awards
    1

    Re: n balls in d bins (non-standard?)

    Frankly, I am confused by what you are asking.
    This is a well know problem: the partitions of an integer into summands.
    In order to program MathLab to produce that table, you must know that the function is recursively defined. So there is no simple closed form solution for this.
    Thanks from sander
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: October 7th 2011, 05:58 PM
  2. Replies: 0
    Last Post: July 19th 2011, 12:45 PM
  3. Entropy increases as number of bins increases
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 24th 2011, 01:14 PM
  4. probability of balls falling to bins
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: January 20th 2011, 03:02 PM
  5. a basket contains 5 red balls, 3 blue balls, 1 green balls
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: May 28th 2010, 03:39 AM

Search Tags


/mathhelpforum @mathhelpforum