Solutions of $ g p g = q $, with $p$, $g$, $q$ being permutations Given two permutations of the same size, $ p $ and $ q $, what can be said about solutions to the equation $ g p g = q $ (with $ g $ being another permutation)?
In particular, under what condition is there a solution? How many solutions are there? Is there a compact way to describe all solutions?
If $ p $ is the identity permutation the question is equivalent to finding the square root of the permutation $ q $, for which there's a solution here, but I can't think of any way to generalize it for other cases.
EDIT: If $ p = x^2 $ then we can multiply by $x$ from the left and right to get $ (xgx)^2 = xqx $, so we can turn each square root of $ xqx $ to a unique solution of the equation. But what if $ p $ isn't a square?
 A: I assume you want to solve $gpg=q$ for $g$ with $p,q$ given. Right-multiply $gpg=q$ by $p$ to get $(gp)^2=qp$. Rewrite as $x^2=r$ (with $x=gp$, $r=qp$), solving for $x$ we then have $g=xp^{-1}$.
What are the square roots $x$ of a permutation $r$? Consider what squaring does to the cycle-structure of $x$: every odd-length cycle stays a cycle of the same length, and every even-length cycle splits into two cycles of half length. Thus, for $r$ to have a square root, all its even-length cycles must be able to be paired off with same-length cycles. That is, a necessary condition is that for every even number $2k$, the permutation $r$ must have an even number of cycles of length $2k$.
In fact, this condition is sufficient: given any choice of how to pair up all cycles of equal even length, and any other number of pairs of cycles of equal odd length, we can interlace them together to get double-length cycles that comprise a square root of $r$.

Suppose $r=qp$ has cycle type $1^{c_1}2^{c_2}\cdots n^{c_n}$, where $c_{2k}$ is even for each even length $2k$. If $r$ has a square root $x$, then there is a unique way to write $x=x_1x_2\cdots x_n$ where the $x_j$ are all disjoint and $x_j^2$ is the $j^{c_j}$-"component" of $r$. So characterizing solutions to $x^2=r$ is reduced to characterizing the solutions when $r$ is a product of cycles of equal length.
Suppose $r$ has cycle type $m^c$ and $m$ is odd. There are $\binom{c}{2s}$ ways of picking $2s$ $m$-cycles to pair up. Then there are $(2s)!/(2^ss!)$ ways of actually pairing them up. There are $m$ ways to "align" and then interlace a pair of $m$-cycles. Thus, in this case the number of square roots $r$ has is
$$ \sum_{s\ge0}\binom{c}{2s} \frac{(2s)!}{2^ss!} m^s $$
On the other hand if $m$ is even, $c$ must be to (for $r$ to have a square root), and the number of square roots is just $\frac{c!}{2^{c/2}(c/2)!}m^{c/2}$.
Putting it all together, if $r$ has cycle type $1^{c_1}2^{c_2}\cdots n^{c_n}$, the number of square roots it has is
$$ \prod_{k\textrm{ even}}\frac{c_k!k^{c_k/2}}{2^{c_k/2}(c_k/2)!} \times \prod_{k\textrm{ odd}}\sum_{s\ge0}\binom{c_k}{2s}\frac{(2s)!k^s}{2^ss!}. $$
