Distinguishability disparity, elementary counting

51 Views Asked by At

Let $m,n$ be given positive integers, $m \geq n$. I am interested in the ratio of the number of solutions to $x_1+\dots+x_n=m$ in positive integers to the number of solutions to $x_1+\dots+x_n=m$ in nonnegative integers. A stars-and-bars argument that can be found elsewhere on MSE tells us that the former is

$${m-1 \choose n-1}$$

while the latter is

$${n+m-1 \choose n-1}.$$

Thus the fraction that I aimed to compute at the beginning is $\frac{{m-1 \choose n-1}}{{n+m-1 \choose n-1}}=\frac{(m-1)!m!}{(m-n)!(n+m-1)!}$. So that's fine.

Now let's suppose the $m$ objects are now distinguishable (the $n$ boxes were already distinguishable in the previous formulation). I actually am not so interested to actually compute the ratio in this case. For my purpose it suffices to notice that the fraction of the configurations in which any one fixed box is occupied is now $1-\left ( \frac{n-1}{n} \right )^m$, and so the probability that all the boxes are occupied is at least $1-n \left ( \frac{n-1}{n} \right )^m$. As $m \to \infty$ this converges to $1$ exponentially fast.

But in the indistinguishable formulation, the ratio converges to $1$ far slower: it is asymptotically something like $1-n^2/m$.

Where is the discrepancy? In particular, why isn't the number of ways to do both things in the distinguishable case just $m!$ times the number of ways to do it in the indistinguishable case, so that the ratios would agree? And why is the effect so drastic in the $m \to \infty$ limit?

1

There are 1 best solutions below

4
On

The reason why the distinguishable case isn't just $m!$ times the number from the indistinguishable case is due to double counting. Let's just consider the case where $n = 2$ and $m = 3$. Consider the indistinguishable case of $x_1 = 2$ and $x_2 = 1$. This corresponds to having $2$ balls in the first bin and $1$ ball in the second bin.

How many distinguishable cases correspond to this indistinguishable case? It's just a matter of labeling the ball in the second bin, and thus there are $3$ choices for labeling, not $6 = 3!$.