What is the number of equivalence classes of $\{0,\ldots,n\}^m/\mathrm S_m$?

Question

What is the number of equivalence classes of $\{0,\ldots,n\}^m/\mathrm S_m$?

where $\mathrm S_m$ is the symmetric group and the equivalence relation is (obviously?) defined as

$$\alpha\sim\beta\iff \alpha\in\beta\cdot\mathrm S_m$$

Im trying to calculate it but it seems hard. Suppose that $n+1\ge m$.

Then if Im not wrong for some subset $A\subset\{0,\ldots,n\}$ such that $|A|=m$ then if $\alpha\in\{0,\ldots,m\}^m$ then

$$|A^m/\mathrm S_m|=\sum_{|\alpha|=m}\binom{m}{\alpha}=m^m$$

where $|\alpha|:=\sum \alpha_j$, in other words the above is the sum of all multinomial coefficients for $m$ positions and $m$ possibly different elements.

If $n+1>m$ then exist $\binom{n+1}{m}$ subsets of cardinality $m$, then the final answer should be

$$|\{0,\ldots,n\}^m/\mathrm S_m|=\binom{n+1}{m}\sum_{|\alpha|=m} \binom m \alpha =\binom{n+1}{m}m^m$$

But if $n+1<m$ then the multinomial sum will be not complete and we can calculate it in a more complicated way and where is not a closed form.

Im very unsure of my calculations. Can someone confirm or correct it? Thank you in advance.

---

Thank to both answers, both are correct, at least to this point:

$$|\{0,\ldots,n\}^m/\mathrm S_m|=\sum_{k=1}^{n+1}\binom{n+1}{k}\binom{m-1}{k-1}=\binom{m+n}{m}$$

• The Vandermonde's identity is key to show the equality.

Answer 1

Elements of $\{0,\ldots,n\}^m$ consist of $m$-tuples and I am assuming $S_m$ acts by place permutation. Since we are only interested in the orbits under the action of $S_m$, we can choose a nice representative: $$(\underbrace{0,\ldots,0}_{m_0},\underbrace{1,\ldots,1}_{m_1},\ldots,\underbrace{n,\ldots,n}_{m_n}).$$ Note that size of the orbit of this element is $$\displaystyle{m\choose m_0,\ldots,m_n}=\frac{m!}{m_0!m_1!\cdots m_n!}$$ and the number of such orbits is equal to the number of compositions of $m$ into at most $n+1$ parts, with parts labelled by an increasing sequence of integers between $0$ and $n$. Alternatively, one can count the number of orbits as the number of partitions of $m$ with at most $n+1$ parts, with parts labelled by distinct integers (in any order) between $0$ and $n$. The number of partitions of $m$ with exactly $k$ parts is the coefficient of $x^m$ in the power series expansion of $$\frac{x^k}{(1-x)(1-x^2)\cdots(1-x^{k})}.$$ It follows that the number of labelled partitions of $m$ with exactly $k$ parts is the coefficient of $x^m$ in power series expansion of $$\frac{{n+1\choose k}x^k}{(1-x)(1-x^2)\cdots(1-x^{k})}$$ and, therefore, the number of orbits is the coefficient of $x^m$ in the power series expansion of $$\sum_{k=0}^{n+1}\frac{{n+1\choose k}x^k}{(1-x)(1-x^2)\cdots(1-x^{k})}.$$

Answer 2

To keep it simple we count the number of equivalence classes of $\{1,2,\ldots,n\}^m$ under the action of the symmetric group $S_m$ acting on the slots. By stars-and-bars we should end up with

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

Now by the Polya Enumeration Theorem with $Z(S_m)$ being the cycle index of $S_m$ we should get

$$Z(S_m)(A_1+A_2+\cdots+A_n)_{A_1=A_2=\cdots=A_n=1}.$$

This is

$$\frac{1}{m!} \sum_{p=1}^m \left[m\atop p\right] n^p.$$

Evaluating this with the OGF of the Stirling numbers of the first kind which is

$$\sum_{k=1}^m \left[m\atop k\right] z^k = \prod_{q=0}^{m-1} (z+q)$$

we find

$$\frac{1}{m!} \sum_{p=1}^m n^p [z^p] \left(m! \times {z+m-1\choose m}\right) = {n+m-1\choose m}.$$

Remark. Since the issue with this question appears to be getting the interpretation right and ascertaining what exactly is being asked, I am posting some relevant Maple code. Consult the code to discover what interpretation I am using. I have deliberately refrained from simplification and optimization in order to represent the original problem as stated.

S :=
proc(n,m)
option remember;
local ind, orbits, dg, items;

    orbits := table();

    for ind from n^m to 2*n^m-1 do
        dg := convert(ind, base, n);

        items := [seq(dg[q], q=1..m)];
        orbits[convert(items, `multiset`)] := 1;
    od;

    nops([indices(orbits)]);
end;

T := (n,m)-> binomial(m+n-1,m);