Two bijections from a finite set to itself commute with each other when they are both powers of one bijection. They also commute with each other when their cycles do not intersect each other.
But some other pairs commute: $(ab)(cd), (ac)(bd), (ad)(bc)$ commute with each other.
Can anything of interest be said about when they commute other than that they commute when they commute?
Let $\sigma\in\mathfrak{S}_n$, denote $C_1,\ldots,C_r$ its orbits, if $\tau\in\mathfrak{S}_n$ is such that $\sigma\circ\tau=\tau\circ\sigma$, then $\tau$ induces a permutation of the $C_i$'s that have the same number of elements. On the other hand, if $\varphi\in\mathfrak{S}_r$ is such that $C_i$ and $C_{\varphi(i)}$ have the same number of elements for all $i$ and if $x_i\in C_i$, there exists a unique permutation $\tau\in\mathfrak{S}_n$ that commutes with $\sigma$ and sending $x_i$ to $x_{\varphi(i)}$ for all $i$.
Let's give an example : suppose $$\sigma=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 5 & 8& 3 & 6&1&7&4&2 \end{pmatrix}\in\mathfrak{S}_8, $$ its orbits are $C_1=\{3\},C_2=\{1,5\},C_3=\{2,8\}$ and $C_4=\{4,6,7\}$. An element $\tau\in\mathfrak{S}_8$ commuting with $\sigma$ must satisfy $\tau(C_1)=C_1$ (i.e $\tau(3)=3$), $\tau(C_4)=C_4$ and $\{\tau(C_2),\tau(C_3)\}=\{C_2,C_3\}$. You thus have $3$ possibilites for the permutation of $C_4$ (take any element of $C_4$, the action of $\tau$ on $C_4$ is uniquely determined by its image) and $2^2=4$ for the permutation of $C_2$ and $C_3$, which you have to multiply by $2$ in case $C_1$ and $C_2$ are both stable by $\tau$ or not. This gives you $24$ possible permutations.
