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

Tough combinatorics problem

  1. Jun 17, 2006 #1
    I've just managed to stump myself. Lets say you have
    M (identical) marbles and N boxes. How many ways
    can you put the marbles in the boxes if each box
    can have at most k (k <= M) marbles?

    for k=M we can take M .'s to be the marbles
    and N-1 |'s to be the boxes so a valid configuration
    is a sequence like ..|.|...||.. so we end up with
    (M+N-1) choose M.

    for k=1, we must have M<N, and
    we have N choices for the first marble,
    N-1 choices for the second, ...
    which is just N choose M possibilities.

    is there a formula for arbitrary k?
  2. jcsd
  3. Jun 19, 2006 #2


    User Avatar
    Science Advisor
    Homework Helper

    The trick here is to subtract the invalid orderings.

    first, let [tex]t = n+m-1[/tex] to simplify things a bit.

    If we can seperate the m balls into n boxes without restriction we get n-1 bars and m balls:

    [tex]N_{all} = \frac{t!}{m!(n-1)!}[/tex]

    If we want to make sure we have at least k+1 balls in a box, we group k+1 balls together and treat them like they're a single weird ball. An example of this is ".|..|{...}.|||", where three of the balls are placed in a set. Then we have n-1 bars, m-(k+1) balls, and 1 weird ball (note that I still divide by m! because you can swap balls within the weird ball with balls outside of it):

    [tex]N_{remove} = \frac{((n-1)+(m-(k+1))+(1))!}{m!(n-1)!}[/tex]



    Now, all the permutations we want to remove just happen to have at least k+1 balls together, so:

    [tex]N = N_{all} - N_{remove}[/tex]

    [tex]=\frac{t!}{m!(n-1)!} - \frac{(t-k)!}{m!(n-1)!}}[/tex]

    [tex]=\frac{t! - (t-k)!}{m!(n-1)!}[/tex]

    not counting any stupid errors I made, of course.

    EDIT: Fixed a mistake (forgot to include balls within weird ball in the denominator)
    Last edited: Jun 19, 2006
  4. Jun 19, 2006 #3
    so we meet again, subtraction--my arch enemy!

    That was exceedingly clever. Thanks for your help.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook