It is known that any two disjoint cycles in $S_n$ commutes. Therefore, any $\pi\in S_n$ which is disjoint with $\sigma$ is in the centralizer of $\sigma$: $C_{S_n}(\sigma)$. Also
$$
\sigma^i\pi\in C_{S_n}(\sigma), 0\leq i\leq|\sigma|. \tag{*}
$$
Here are my questions:
Are these all the elements in $C_{S_n}(\sigma)$? If the answer is no, is there an method to find all the elements in $C_{S_n}(\sigma)$ other than check the elements one by one?
A quick search returns several relevant questions:
- Order of the centralizer of a permutation
- Centralizer of a specific permutation
- Is there a systematic way of finding the conjugacy class and/or centralizer of an element?
The method ($*$) is what I learned so far from these questions and their answers. An immediate example in which ($*$) does not work that I can come up with is $\sigma=(12)(34)(56)$ in $S_6$. No disjoint $\pi$ can be found in this case and
$$\langle(12),(34),(56)\rangle\subset C_{S_6}(\sigma).$$
Best Answer
The key is to look at how conjugation affects permutations of a given cycle type:
$$g=(a_1~a_2~\cdots~a_{\lambda_1})(b_1~b_2~\cdots~b_{\lambda_2})\cdots(c_1~\cdots~c_{\lambda_r}); \\ \sigma g\sigma^{-1}=(\sigma(a_1)~\sigma(a_2)~\cdots~\sigma(a_{\lambda_1}))\,\cdots(\sigma(c_1)~\cdots~\sigma(c_{\lambda_r})).$$
The first line denotes the disjoint cycle representation of an arbitrary $g\in S_n$. Thus, conjugation may only permute cycles of the same length in the representation. Let's revamp our notation:
$$g=a_{1,1}a_{1,2}\cdots a_{1,e_1}\cdots a_{s,1}\cdots a_{s,e_s},$$
where $a_{k,1},\cdots,a_{k,e_k}$ denote the $e_k$ cycles of length $\lambda_k$ in the decomposition, and $g$'s cycle type is
$$\lambda=\big(\underbrace{\lambda_1,\cdots,\lambda_1}_{e_1},\cdots,\underbrace{\lambda_s,\cdots,\lambda_s}_{e_s}\big)\vdash n.$$
The $\lambda_i$s are distinct so that the $e_i$s describe their multiplicities in the integer partition $\lambda$ of $n$.
Fix written representations of the cycles i.e. $a_{t,\ell}=(a_{t,\ell}^{(1)}~a_{t,\ell}^{(2)}~\cdots~ a_{t,\ell}^{(\lambda_{\large t})})$ for $1\le t\le s$ and $1\le\ell\le e_t$; denote, for an arbitrary element $\tau\in S_{e_1}\times\cdots\times S_{e_s}=E$, the induced permutation $\phi(\tau)\in S_n$ that sends $a_{t,\ell}^{(f)}\mapsto a_{t,\tau_{\large t}(\ell)}^{(f)}$, again for each index $1\le t\le s$, $1\le \ell\le e_t$. Thus the inclusion $\phi(E)\subseteq C(g)$ holds. The only other ways to not affect $g$'s structure is to cycle through its disjoint cycles, but note these cyclings can all be done independently from each other. We therefore deduce
$$C(g)=\left\langle \underbrace{\phi(S_{e_1}\times\cdots\times S_{e_s})}_E,\underbrace{\prod_{t=1}^s\prod_{\ell=1}^{e_t}\langle a_{t,\ell}\rangle}_{P}\right\rangle.$$
Observe the cyclic groups generated in the products in $P$ are each trivially intersecting, so the internal product is in fact direct. The elements of $E$ don't slide past those of $P$ without a fight, however; they act on them so that we are creating an unrestricted internal wreath product.
Note then that every element of $C(g)$ can be written as $\alpha\beta$ with $\alpha\in E$ and $\beta\in P$.
We say unrestricted because the arguments here generalize to symmetric groups of arbitrary cardinality, with care taken to only allow infinite products of disjoint cycles and replace $\lambda_i$s and $e_i$s with cardinal numbers as need be. In conclusion,
$$C(g)\cong \prod_{t=1}^s (C_{\lambda_{\large t}}\wr S_{e_{\large t}}),\quad \#C(g)=\prod_{t=1}^s \lambda_t^{e_t}e_t!$$
edit: fixed notation explanation