Why does $\frac {f(n,m-1)} {f(n,m)} = \frac {g(n,m-1)} {g(n,m)} $ here? (Balls and Bins)

60 Views Asked by At

Define $f(n,m)$ as returning the amount of ways to throw $n$ distinguishable balls into $m$ bins, and $g(n,m)$ as returning the amount of ways to throw $n$ indistinguishable balls into $m$ bins. I am wondering whether anyone could conceptually justify why $\frac {f(n,m-1)} {f(n,m)} = \frac {g(n,m-1)} {g(n,m)} $ for any integers $n,m >1$, without just counting the numerators and denominators and using algebraic manipulation to show equivalence. So far, I have tried to think of these functions recursively: seeing combinatorially how $f(n,m)= f(n-1,m)+ f(n,m-1)$ and $g(n,m) = g(n-1,m-1) + g(n,m-1)$- but I haven't gotten anywhere conceptual with this (There may be an inductive proof with this, but this isn't the type of justification I want here unless it is extremely simple and intuitive).

This problem is of my own construction- the motivation for asking about it was to understand the underlying phenomena in the problem here better.

1

There are 1 best solutions below

0
On BEST ANSWER

Just so we can close this question, the two ratios you ask about are not equal.

It is easy to prove that $g(n,m)=m^n$, because each of the $n$ balls must be placed into one of the $m$ bins. This means that $$ \frac{g(n,m-1)}{g(n,m)}=\left(\frac{m-1}{m}\right)^n $$ However, using stars and bars, we can show $f(n,m)=\binom{m+n-1}{n}$. Therefore, $$ \frac{f(n,m-1)}{f(n,m)}=\frac{\binom{m+n-2}{n}}{\binom{m+n-1}{n}}=\frac{m-1}{m+n-1} $$ Clearly, these two expressions are not equal, for example when $m=2$ and $n=1$.