Multinomial sets

Question

I'm having a problem figuring out this problem, it is similar to combining sets of non-unique letters, but is slightly different.

Let k, m, and n be positive integers. We have nm balls, m colors, n balls, and k uniquely labeled bins. How many different ways are there to select n balls to put into the k bags?

For example, if m = 3, n = k = 2, the result is 21. There are 3 colors where we are choosing 2 balls out of the total 6 to place into 2 bins.

(-, WW), (-,WR), (-, WB) ...

(WW, -), (WR, -) ...

(W,W), (W,R) ...

(B,W), (B,R) ...

The normal version of this problem does not require the selection of a subset of the total elements. That problem yields n! / x₁! x₂! x₃! ... where x₁, x₂, x₃ are groups of duplicated letters.

correction (clarity) -> you have a total of nm balls. n balls of each color where there are m colors; from here you then choose n of these total nm balls randomly and place them into the k distinct bins.

Answer 1

Let me be sure I have the question right. We have m colors. We have k bins. We want to select n balls and place them in the bins. We have enough balls of each color that we don't have to worry about running out of any particular color.

In that case, the problem boils down to how many ways we have have n balls of m*k kinds. (A kind being determined by color and bin.) There is a standard trick to calculate this. First let's number the kinds. Put down all of the balls of the first kind. Then a divider. Then all the balls of the second kind. Then a divider. And so on until we have all n balls and k*m - 1 dividers down. This procedure is completely reversible, if we take n + k*m - 1 things in a row, select n of them to be balls and the rest to be dividers, we can then color the balls and put them into bins to get to n balls of m colors in k bins.

Therefore the answer is choose(n + k*m - 1, n).

(Note, this is the reasoning that I came up with after I knew the answer. My actual path to the answer was much longer and more circuitous.)

Answer 2

I believe that you can treat this problem as m independent n-multicombinations.

So the answer is m * multichoose(n, k), where multichoose(a, b) = C(a + b -1, b).

---

Edit: This assumes you are asking about n balls of each color and placing all nm balls.