TransWikia.com

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

Mathematics Asked by ironX on November 14, 2021

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.

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

Answered by Trent Park on November 14, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP