1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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

    Alkatran

    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]

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

    [tex]=\frac{(t-k)!}{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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Tough combinatorics problem
  1. Combinatorics problem (Replies: 6)

  2. Combinatorics problem (Replies: 3)

  3. Combinatorics problem (Replies: 8)

  4. Combinatorics problem (Replies: 4)

Loading...