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

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.

Mathematics Asked by ironX on November 14, 2021

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$$

Answered by Trent Park on November 14, 2021

## Related Questions

### Expected norm of first $d$ coordinates of the $n$-dimensional sphere

2  Asked on January 29, 2021 by godsbane

### Does anyone know how to find H in this question?

0  Asked on January 29, 2021 by dwij-bhandari

### Laplace eigenvalues on unit disc intermediate step

1  Asked on January 29, 2021 by azamat-bagatov

### How to check if a digraph is strongly connected with its adjacency matrix?

2  Asked on January 29, 2021 by javier-cf

### Confusion on analytic continuation.

1  Asked on January 29, 2021

### Is a surface curve made of planar points necessarily a line?

1  Asked on January 29, 2021 by mk7

### How to solve $sqrt{x!y!}=xy$ for $(x,y)inmathbb{Z}_{geq0}timesmathbb{Z}_{geq0}$?

3  Asked on January 29, 2021 by ramez-hindi

### Intuition for fractions of the localization of a non integral domain

1  Asked on January 29, 2021 by siddharth-bhat

### Proving origin to be removable singularity(Proof verification)

2  Asked on January 29, 2021

### Relationship between constants so that the center of curvature of the helix is contained in the cylinder

1  Asked on January 28, 2021

### An identity between integral

1  Asked on January 28, 2021 by inoc

### How to find the least in $E^{circ}=frac{5S^g}{162}+frac{C^circ}{50}+frac{2pi^2}{360}textrm{rad}$?

1  Asked on January 28, 2021 by chris-steinbeck-bell

### In what sense do we say two functions are equal?

0  Asked on January 28, 2021 by ziqi-fan

### $P (| X |> 1) = P (| X | <1)$

1  Asked on January 28, 2021

### Sequentially open sets but not open

1  Asked on January 28, 2021 by t-i

### Simplify $logleft(1+frac{x_i^2}{nu}right)$ with a $log(1+x)$ rule?

2  Asked on January 28, 2021

### Finding an Extremal for a function.

1  Asked on January 28, 2021 by zeroflank

### Isomorphism between group of homeomorphisms where $X nsim Y$

2  Asked on January 28, 2021

### Basis of the field $E$=$mathbb{Q}(sqrt{6}i-sqrt{5})$.

3  Asked on January 27, 2021 by questmath