On the Wikipedia page for the Symbolic Method of Flajolet and Sedgewick


under the heading "Classes of combinatorial structures" it states: "The orbits with respect to two groups from the same conjugacy class are isomorphic."

Does anyone know of a proof of this? Perhaps something like:


  • $G$ is a group.

  • $X$ is a set.

  • $\psi: G \times X \rightarrow X$ is a $G$ action on $X$.

  • $H$ and $H^{\prime}$ are conjugate subgroups of $G$ — that is, $H^{\prime} = gHg^{-1}$ for some $g \in G$.

  • $H$ and $H^{\prime}$ act on $X$ by the restrictions of $\psi$ to $H$ and $H^{\prime}$, respectively.

  • $\text{orb}_{H}(x)$ and $\text{orb}_{H^{\prime}}(x)$ denote the orbits of $x \in X$ with respect to $H$ and $H^{\prime}$, respectively.

  • $\phi$ denotes the isomorphism between $H$ and $H^{\prime}$ defined by $\phi(h) = ghg^{-1}$.

Now, define the function $f: \text{orb}_H(x) \rightarrow \text{orb}_{H^{\prime}}(\psi(g, x))$ by \begin{equation*} f(\psi(h, x)) = \psi(\phi(h), \psi(g, x)). \end{equation*} Then, $f$ is a well-defined bijection and \begin{align*} f(\psi(h, z)) = \psi(\phi(h), f(z)). \end{align*} Many thanks.

  • 1
    $\begingroup$ What's the definition of "isomorphic orbits"? $\endgroup$ – user750041 Jun 5 '20 at 20:16
  • 2
    $\begingroup$ I assume in the sense of G sets. That is, that there exists a bijection between the orbits which is compatible with the group actions. $\endgroup$ – user796754 Jun 5 '20 at 20:28
  • 3
    $\begingroup$ Please do not vandalize your question, particularly after getting an answer. $\endgroup$ – Xander Henderson Jun 12 '20 at 17:45

After defining conjugacy as a group action, it follows from the definition that the orbits are now the conjugacy classes.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy