Ordered pairs of permutations in symmetric group

Question

How many ordered pairs $\left(\alpha_1,\alpha_2\right)$ of permutations in symmetric group $S_n$ that commute: $$\alpha _1 \circ \alpha _2 = \alpha _2 \circ \alpha _1\,,$$ where $\alpha _1, \alpha _2 \in S_n$?

Answer 1

Let $G$ be a finite group. For each $g\in G$, define $\varphi_g$ to be the conjugation by $g$ (i.e., $\varphi_g$ sends $h\in G$ to $ghg^{-1}$). Let $\tilde{G}$ be the set of conjugacy classes of $G$. For $g\in G$, let $\Gamma_g$ be the conjugacy class of $G$ containing $g$. We claim that the set $$T(G):=\left\{(g,h)\in G\times G\,\big|\,gh=hg\right\}$$ has $|G|\cdot|\tilde{G}|$ elements.

For $\psi:G\to G$, write $\text{Fix}(\psi)$ for the set of fixed points of $\psi$ (i.e., $\text{Fix}(\psi)=\left\{g\in G\,\big|\,\psi(g)=g\right\}$). By the Orbit-Stabilizer Theorem, $$\Big|\text{Fix}\left(\varphi_g\right)\Big|\,\left|\Gamma_g\right|=|G|\,,$$ since $h\in \text{Fix}\left(\varphi_g\right)$ if and only if $g\in\text{Fix}\left(\varphi_h\right)$. Observe that $$\big|T(G)\big|=\sum_{g\in G}\,\big|\text{Fix}\left(\varphi_g\right)\big|=\sum_{C\in \tilde{G}}\,\sum_{g\in C}\,\Big|\text{Fix}\left(\varphi_g\right)\Big|\,.$$ Now, $g\mapsto \Big|\text{Fix}\left(\varphi_g\right)\Big|$ for every $g\in G$ is clearly a class function, so we shall write $F_C$ for $\Big|\text{Fix}\left(\varphi_g\right)\Big|$ for every $C\in \tilde{G}$, where $g\in C$ is arbitrary. Hence, $$\big|T(G)\big|=\sum_{C\in \tilde{G}}\,\sum_{g\in C}\,F_C=\sum_{C\in \tilde{G}}\,|C|\cdot F_C\,.$$ As $|C|\cdot F_C=\left|\Gamma_g\right|\cdot \Big|\text{Fix}\left(\varphi_g\right)\Big|=|G|$, where $g\in C$ is arbitrary, we obtain $$\big|T(G)\big|=\sum_{C\in\tilde{G}}\,|G|=|G|\cdot|\tilde{G}|\,,$$ as desired. If $\tilde{T}(G):=\big\{\{g,h\}\,\big|\,(g,h)\in T(G)\big\}$, then $\big|\tilde{T}(G)\big|=\frac{|G|}{2}\big(|\tilde{G}|+1\big)$.

Now, if $G=S_n$, then $\left|\tilde{G}\right|=p(n)$, where $p$ is the partition function (i.e., $p(n)$ is the number of ways to write $n$ as a sum of positive integers in nondecreasing order). Consequently, $$\big|T\left(S_n\right)\big|=p(n)\cdot n!\,.$$

---

As a remark to Elliot G's comment, the number of pairs $(\alpha,\beta)\in S_n\times S_n$ such that $\alpha$ and $\beta$ have disjoint cycle factorizations is given by $\sum_{k=0}^n\,\binom{n}{k}\,k!\,D_{n-k}$, where $D_r$ is the $r$-th derangement (or subfactorial) number. Using $D_r=r!\,\sum_{j=0}^r\,\frac{(-1)^j}{j!}$, you can show that $$\sum_{k=0}^n\,\binom{n}{k}\,k!\,D_{n-k}=D_{n+1}+D_{n}\,.$$ The number of unordered pairs $\{\alpha,\beta\}\subseteq S_n$ with disjoint cycle factorizations is thus $\frac{D_{n+1}+D_n+1}{2}$.

Answer 2

Let $T_r(n)$ denote the number of commuting $r$-tuples in $S_n$. The following formula for the exponential generating function of $T_r(n)$ is derived in [http://arxiv.org/abs/1304.2830]:

$$\sum\limits_{n=0}^{\infty} T_r(n)\frac{u^n}{n!} = \prod\limits_{j=1}^{\infty} (1-u^j)^{-\lambda_{r-1}(j)}$$ where $$\lambda_r(n)= \sum\limits_{d_1d_2\cdots d_r=n}d_2 d_3^2 \cdots d_r^{r-1}.$$

In particular, to evaluate $T_2(n)$, observe that $\lambda_1(n)=1$, so $$\sum\limits_{n=0}^{\infty} T_2(n)\frac{u^n}{n!} = \prod\limits_{j=1}^{\infty} (1-u^j)^{-1} = \sum_{n=0}^\infty p(n) u^n$$ where $p(n)$ is the number of partitions of $n$, and we conclude that $T_2(n)=n!\, p(n)$.