A combinatoric problem: assign labeled ball to unlabeled boxes

by KevinKim   Last Updated April 16, 2018 12:20 PM

I have $n$ boxes with unlimited capacity. I have $m$ ball with label $1,2,...,m$. The assigning mechanism is the following: randomly draws a ball without replacement, then randomly assigns this ball to one of these $n$ boxes. Do this for all $m$ balls. I want to know

P{a ball with label $i$ being assigned to an empty box}, where $i=1,2,...,m$

I was thinking

P{a ball with label $i$ being assigned to an empty box} = $\sum_{k=1}^m$P{a ball with label $i$ being assigned to an empty box| the rank of ball with label $i$ is k}P{rank = k}

And we know P{rank = k} = 1/m, for all $k$. When $k=1$, P{a ball with label $i$ being assigned to an empty box| the rank of ball with label $i$ is k}=1, obviously. But what is the expression for P{a ball with label $i$ being assigned to an empty box| the rank of ball with label $i$ is k} for general k?

A second question is, when $n,m$ goes to infinity (at the same rate), then what will the limit of P{a ball with label $i$ being assigned to an empty box}?

Tags : combinatorics


Related Questions



Combinatorics problem on the size of A+B

Updated April 22, 2015 22:08 PM

Certain property of finite field $F_p$

Updated September 27, 2017 02:20 AM


Necklace polynomial recurrence relation

Updated March 05, 2017 05:20 AM