Count number of maps from $2$ object set to $S_n$ up to equivalence I need to find a way to count the number of maps from $\{0,1\}$ to $S_{n}$ the symmetric group on n symbols, where 2 maps $f,g$ are equivalent if $\exists \sigma \in S_{n}$, $\sigma f \sigma^{-1} = g$ (that is, $\sigma f(0) \sigma^{-1} = g(0)$ and $\sigma f(1) \sigma^{-1} = g(1)$. specifically im interested in the case $n=3$ but if there is some generalization for $n$ and maybe a set larger than $\{0,1\}$ I would love to hear it.
What I tried: I was thinking that it was enough to count the number of maps from $\{0,1\}$ to the set of conjugacy classes of $S_{n}$, but obviously the condition imposed is slightly stronger, since it isnt enough to ask that $g(0)$ is conjugate to $f(0)$ and same for $f(1),g(1)$. Perhaps there's a way to slightly modify this argument?
 A: Call $M_{n}$ the set of functions form $[2]=\{0,1\}$ to $S_n$ and consider the action by conjugation of $S_n$ there. You want to count the number of orbits. Burnside lemma tells us that
$$\text{# Orbits}=\frac{1}{|S_n|}\sum _{\sigma \in S_n}\left | M_n^{\sigma }\right |=\frac{1}{n!}\sum _{\sigma \in S_n}|\text{# functions fixed by $\sigma$}|.$$
$f$ is fixed by $\sigma$ iff $\sigma f \sigma ^{-1}=f$ so $f(0)\sigma ^{-1}f(0)^{-1}=\sigma ^{-1}$ that means that $f(0)$ fixes $\sigma ^{-1}$ under conjugation. Same for $f(1).$ so we have to get two permutations that fix $\sigma ^{-1}.$
To fix a permutation by conjugation we have to fix every cycle, and to fix a cycle of length $k$ we have $k$ choices. That means that if $\sigma ^{-1}$ has cycle type $\lambda _1,\cdots ,\lambda _s$ then we have $\prod _{i=1}^s\lambda _i$ ways to fix it, so if we want to choose two elements of this set we have to compute $$\left ( \prod _{i=1}^s\lambda _i\right ) ^2=\prod _{i=1}^s\lambda _i^2.$$ In that way we have that
$$\text{# Orbits}=\frac{1}{n!}\sum _{\lambda \vdash n}\sum _{\sigma \text{ has cycle type }\lambda} \prod _{i=1}^s{\lambda _i}^2=\frac{1}{n!}\sum _{\lambda \vdash n}\left ( \text{# permutations type $\lambda$}\right )\cdot \prod _{i=1}^s{\lambda _i}^2. $$
If you have a partition $\lambda =(\lambda_1,\cdots , \lambda _s)$ and you consider $a_i = \text{# times $i$ is a part of $\lambda$},$ then, because you can choose the elements in each cycle and then multiply by number of cycles, the sum above can be expressed as
$$\text{# Orbits}=\frac{1}{n!}\sum _{a_1+2\cdot a_2+\cdots +n\cdot a_n=n}\frac{n!}{\prod _{i=1}^ni^{a_i}}\cdot \prod _{i=1}^ni^{2\cdot a_i}=\sum _{a_1+2\cdot a_2+\cdots +n\cdot a_n=n}\prod _{i=1}^ni^{a_i},$$
from there is not hard to believe that if you have functions from $[m]$ to $S_n$ then the total number of functions is
$$\sum _{a_1+2\cdot a_2+\cdots +n\cdot a_n=n}\prod _{i=1}^ni^{(m-1)a_i}.$$
Which kind of makes sense for $m=1$ because you get the number of partitions of $n.$
This can be expressed as
$$[x^n]\prod _{k=1}^n\frac{1}{1-k^{m-1}\cdot x^k},$$
for $m=2$ you can find more info in OEIS. $m>2$ seems to not be there.
