I am recently reading a research paper and I came across author's calculation that I am not able to figure out:
There is a flow(sequence) of packets and n total buckets. All the balls in a flow are uniformly assigned to m random buckets, where m << n.
What is a probability that 2 flows of packets will be assigned the same set of m buckets?
My solution: I consider this problem as picking m random samples from total of n. There are nCm ways to pick m buckets and only one of them will be similar so 1/nCm.
Paper's answer: m!/n^m
Suppose we have a flow of $n$ packets, and we have $m$ buckets.
The packets are identical, and buckets are identical. In this case, there are $\big(n+(m-1)\big)!$ different ways that we can distribute $n$ different packets to $m$ different buckets. (Suppose we have $\underbrace{**\dots*}_{n}$, and we have $\underbrace{||\dots|}_{m-1}$. The stars are balls, and the lines are buckets. Why we have $m-1$ lines? For this question, consider this example. For three balls and two buckets, we have $***|$ (all balls are in the first bucket), $**|*$ (two balls are in the first bucket and one ball are in the second buckets),... Thus, we need $m-1$ lines.) If we have two flows, then the probability of the two flows be same is $\frac{1}{\big(n+(m-1)\big)!}$.
The packets are not identical, and buckets are identical. In this case, there are $\frac{\big(n+(m-1)\big)!}{n!}$ different ways that we can distribute $n$ same packets to $m$ different buckets. If we have two flows, then the probability of the two flows be same is $\frac{n!}{\big(n+(m-1)\big)!}$.
The packets are identical, and buckets are not identical. In this case, there are $\frac{\big(n+(m-1)\big)!}{(m-1)!}$ different ways that we can distribute $n$ different packets to $m$ same buckets. If we have two flows, then the probability of the two flows be same is $\frac{(m-1)!}{\big(n+(m-1)\big)!}$.
The packets are not identical, and buckets are not identical. In this case, there are $\frac{\big(n+(m-1)\big)!}{n!(m-1)!}$ different ways that we can distribute $n$ same packets to $m$ same buckets. If we have two flows, then the probability of the two flows be same is $\frac{n!(m-1)!}{\big(n+(m-1)\big)!}$.