Combinatorial mathematics question

Factual Questions
1

Let’s suppose a set of ‘n’ marbles are randomly dropped into ‘k’ urns. In how many different ways can this be done?
To take an easy example, if n=4 and k=2 then there are 5 ways:

  1. 4 in one urn 0 in the other:
  2. 0 4
  3. 3 1
  4. 1 3
  5. 2 2

And maybe an even more difficult question: in how many different ways can this be done so that all urns are “filled” ?
(In other words, each urn has at least one marble).

I’ve done a lot of searcing and still I’m not quite sure how to calculate this and there seems to be no general formula for it.

This thread:

got me started on all of this.

2

First question - (n+1)(k-1).

Second - It’s not that much more difficult a question - you just have to throw out some combinations. I think it’s (n)(k-1) instead.

3

bup
Just looking at the first formula, I deicded to run a quick test.
4 marbles into 3 urns by the formula is 10. However the actual number is 15:

  1. 4 0 0
  2. 0 4 0
  3. 0 0 4
  4. 3 1 0
  5. 3 0 1
  6. 1 3 0
  7. 0 3 1
  8. 1 0 3
  9. 0 1 3
  10. 2 1 1
  11. 1 2 1
  12. 1 1 2
  13. 2 2 0
  14. 2 0 2
  15. 0 2 2
4

I believe this problem reduces to that of calculating the number of integer partitions of n with length k. This sort of calculation can be done, at least formally, using a partition function.

5

I’m guessing bup dropped a “C”; the answer to the first question is the binomial coefficient C(n+1,k-1). The idea is that you imagine the marbles as occupying spaces 1, 3, 5, …, 2n-1; you want to add k-1 partitions, in the even spaces 0, 2, 4, …, 2n, to separate these into k sets of marbles. There are n+1 spaces for partitions, and k-1 partitions to be chosen.

For the second question, begin by putting one marble in each urn. Now you have n-k marbles left, to distribute as above: C(n-k+1,k-1).