The number of types on a set is equal to $binom{n + m - 1}{m - 1}$?

Question

Let $M = {1,2,..., m }$ be a finite set. Consider an $n$-type distribution $t$ on $M$ such that for any $e in M$, $t(e) in left {0,frac{1}{n}, ..., frac{n-1}{n}, 1 right }$ and $sum limits_{e in M} t(e) = 1$.
The set of all possible $n$-types on $M$ is denoted by $mathcal P_n(M)$. Why is $$|mathcal{P}_n(M)| = binom{n+m-1}{m-1} ,, ? $$
My thoughts:
A vector $t in mathcal{P}_n(M)$ has $m$ components; each component can take $n+1$ possible values but not quite. Because for example if $t(1) = 1$ then the rest of components must be zero. So the first component can take $n+1$ possible values, but the number of possible values the second component can take depends on the first component's value and so on .... I am struggling to make counting argument here.

Trent Park · Answer

To elaborate even further on Matthew Tower's answer, imagine your m number of objects as stars: * and then imagine you have bars | to divide up your stars into n groups, for example:
* *|* *|*
So we have m=5 objects divided into n=3 groups.
This can equivalently be thought of as arranging 7 'objects' (i.e. I only need two 'dividers' to make 3 groups, hence the n+m-1), however, the stars are indistinguishable from on another and the bars are indistinguishable from one another so the number of unique arrangements can be determined by placing [and fixing] your m stars among the m+n-1 positions, leaving the choice of n-1 positions for the bars, hence:
$$ n+m-1choose n-1$$
Or, equivalently, fix the bars and choose m spots for the stars:
$$ n+m-1choose m $$

The number of types on a set is equal to $binom{n + m - 1}{m - 1}$?

One Answer

Add your own answers!

Ask a Question