Distributing $m\cdot n$ identical items into $n$ distinct boxes, with $m$ distinct positions in box

67 Views Asked by At

There are $n$ boxes and $m\cdot n$ identical items. Each box has $m$ positions where an item can be placed. The order matters here. It is a difference if an item is placed in position 1, 2, or 3 or if two items are placed in positions 1 and 2, or 1 and 3, or 2 and 3.

How many combinations exist for up to $m\cdot n$ items placed in the $n$ boxes so that the number of boxes with more than $0$ items is exactly $t$?

I can simulate (count) this, but I do not have the combinatoric math capabilities to come up with the analytical equation.

I simulated for $n=7$ boxes with $m=3$ distinct positions in the box:

There are $49$ possible combinations for $t=1$ (items are distributed in a single box). $21 (7\cdot 3)$ when placing a single item, $21$ when placing $2$ items and $7$ when placing $3$ items.

For $t=2$, there are overall $1029$ ways to distribute items: $189$ for placing $2$ items, $378$ for $3$, $315$ for $4, 126$ for $5$ and $21$ for $6$.

And so on.

Is there a way to express this problem analytically for arbitrary $m, n,$ and $t$?

1

There are 1 best solutions below

15
On BEST ANSWER

Assuming the boxes are distinguishable:

There are $\binom nt$ ways to choose the $t$ non-empty boxes. Then, for each of those, there are $(2^m-1)$ ways to pick a non-empty subset of the positions. It follows that the desired function is $$f(n,m,t)=\binom nt\times \left(2^m-1\right)^t$$

We remark that $f(7,3,1)=49$ and $f(7,3,2)=1029$ as desired.