combinatorics

[qbert]

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?

[Alkatran]

The trick here is to subtract the invalid orderings.

first, let t = n+m-1 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:

N_{all} = \frac{t!}{m!(n-1)!}

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):

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

=\frac{(n+m-k-1)!}{m!(n-1)!}

=\frac{(t-k)!}{m!(n-1)!}

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

N = N_{all} - N_{remove}

=\frac{t!}{m!(n-1)!} - \frac{(t-k)!}{m!(n-1)!}}

=\frac{t! - (t-k)!}{m!(n-1)!}

not counting any stupid errors I made, of course.

EDIT: Fixed a mistake (forgot to include balls within weird ball in the denominator)

[qbert]

so we meet again, subtraction--my arch enemy!

That was exceedingly clever. Thanks for your help.