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

Similar Threads for Tough combinatorics problem Date
I Combinatorics & probability density Apr 6, 2018
I Tough probability question Jun 7, 2017
Why translating language to propositional logic is tough? Feb 1, 2014
Simple, yet tough urn problem Mar 5, 2012
Tough probability problem (any takers?) Dec 29, 2009