The number of orbits of $\langle\pi\rangle$ on $\Omega$ is $\frac{1}{m}\sum_{d\mid m}f(\pi^d)\varphi(m/d)$

Question

Let $\Omega$ be $\Omega= \{1, . . . , n\}$ and let $G$ be $G := \text{Sym}(\Omega)$.

Show:

(a) If $\pi_1, \pi_2 \in G$ generate the same cyclic subgroup of $G$, then $f(\pi_1) = f(\pi_2)$.

(b) Let $\pi ∈ G$ be of order $m$. The number of orbits of $\langle\pi\rangle$ on $\Omega$ is

$$\frac{1}{m}\sum_{d\,\mid\,m}f(\pi^d)\varphi\left(\frac{m}{d}\right)$$

Definition of orbit: Consider a group $G$ acting on a set $X$. The orbit of an element $x$ in $X$ is the set of elements in $X$ to which $x$ can be moved by the elements of $G$.

I'm currently learning for the discrete maths exam and I found this old exam question. Unfortunately I really have no idea where to start. Thanks in advance!

Answer 1

For $\pi\in\operatorname{Sym}(\Omega)$ of order $m$, consider the natural action of $\langle\pi\rangle$ on $\Omega$. Then (Burnside's lemma): $$\#\text{ of orbits}=\frac{1}{m}\sum_{k=1}^m\left|\operatorname{Fix}(\pi^k)\right| \tag 1$$ where $\operatorname{Fix}(\pi^k)=\{i\in\Omega\mid\pi^k(i)=i\}$. If $\gcd(k,m)=d$, then $\pi^k$ fixes the same number of elements of $\Omega$ as $\pi^d$. But there are $\varphi (\frac{m}{d})$ elements $k\in\{1,\dots,m\}$ such that $\gcd(k,m)=d$. Then: \begin{alignat}{1} \sum_{k=1}^m\left|\operatorname{Fix}(\pi^k)\right| &= \sum_{d|m}\varphi\Bigl(\frac{m}{d}\Bigr)\left|\operatorname{Fix}(\pi^d)\right| \\ \tag 2 \end{alignat} Now, plug $(2)$ into $(1)$ and you'll get the claim (b) (with the identification $f(\_)=\left|\operatorname {Fix}(\_)\right|$).

---

Edit. The number of orbits in the question is precisely the length of the cycle structure of $\pi$, $c_\pi=(\underbrace{1,\dots,1}_{k\text{ slots}},m_1,\dots,m_l)$, where:

• all $m_i$'s are greater than $1$;
• $\sum_{i=1}^lm_i=n-k$;
• $m=\operatorname{lcm}(m_1,\dots,m_l)$.

In particular, if $\pi$ is an $m$-cycle, then: $$n-m+1=\frac{1}{m}\sum_{d|m}\varphi\Bigl(\frac{m}{d}\Bigr)\left|\operatorname{Fix}(\pi^d)\right| \tag 3$$ which, for $\pi$ an $n$-cycle, further specializes into: $$\sum_{d|n}\frac{\varphi(n/d)}{n}\left|\operatorname{Fix}(\pi^d)\right|=1 \tag 4$$ Since $\sum_{d|n}\frac{\varphi(n/d)}{n}=1$ (see "Divisor sum" under "Computing Euler's totient function" section), $(4)$ looks like a weigthed average with possibly some statistic application.

(Added: $(4)$ is trivial, actually: in fact, for an $n$-cycle $\pi$, $\left|\operatorname {Fix}(\pi^d)\right|\ne 0\iff d=n$, and $\left|\operatorname {Fix}(\pi^n)\right|=\left|\operatorname {Fix}(Id)\right|=n$, whence $(4)$ trivially follows.)