正多角形の頂点の入れ替え方は何通り？

${\sim }_f$が同値関係であることは省略.
まず$f=\tilde{f}\circ i$を満たす$\tilde{f}$が一意に存在することを示します.$x\in X$に対して$i(x)=[x]$と書きます.このとき$\tilde{f}$としてありうるのは
$$\tilde{f}:X/{\sim }_f\ni [x]⟼f(x)\in Y$$
のみです.これが well-defined であることを見ればよいです.
$[x]=[y]$とすると定義から$f(x)=f(y)$なので上の$\tilde{f}$は well-defined です.
$\tilde{f}$は作り方から明らかに$f=\tilde{f}\circ i$を満たし,さらに$f$は全射なので$\tilde{f}$も全射です.
次に単射性を示します.$\tilde{f}([x])=\tilde{f}([y])$とすると$f(x)=f(y)$なので${\sim }_f$の定義から$x{\sim }_{f}y$,つまり$[x]=[y]$です.

包除原理を使います.
$n$と互いに素$\iff$$\{p_1$の倍数でない$\}\cap \cdots \cap \{p_r$の倍数でない$\}$
に注意します.$A_{p_i}=\{k\in \{1,...,n\}\mid k\text{は}{p}_i\text{の倍数}\}$とすると
$$\begin{array}{rl}\phi (n)& =|A_{p_1}^c\cap \cdots \cap A_{p_r}^c|\\ & =n-|A_{p_1}\cup \cdots \cup A_{p_r}|\\ & =n+\sum _{\begin{array}{c}1\le i_1<\cdots <i_k\le r\\ 1\le k\le r\end{array}}(-1{)}^k|A_{p_{i_1}}\cap \cdots \cap A_{p_{i_k}}|\\ & =n+\sum _{\begin{array}{c}1\le i_1<\cdots <i_k\le r\\ 1\le k\le r\end{array}}\frac{(-1{)}^{k}n}{p_{i_1}\cdots p_{i_k}}\\ & =n\prod _{i=1}^r(1-\frac{1}{p_i})\end{array}$$
2行目の等号はド・モルガンの法則から,4行目の等号は$p_1,...,p_r$が相異なる素数であることから従います.

$n,m$がそれぞれ$n=p_1^{e_1}\cdots p_r^{e_r},m=q_1^{f_1}\cdots q_s^{f_s}$と素因数分解されているとします.$n$と$m$は互いに素なので$p_1,...,p_r,q_1,...,q_s$は互いに異なる素数であり$nm$は$nm=p_1^{e_1}\cdots p_r^{e_r}{q}_1^{f_1}\cdots q_s^{f_s}$と素因数分解されます.よってphikousikiより
$$\begin{array}{rl}\phi (n)\phi (m)& =\left(n\prod _{i=1}^r(1-\frac{1}{p_i})\right)\left(m\prod _{j=1}^s(1-\frac{1}{q_j})\right)\\ & =nm\prod _{i=1}^r(1-\frac{1}{p_i})\prod _{j=1}^s(1-\frac{1}{q_i})\\ & =\phi (nm)\end{array}$$

まず$n$が素数冪の場合,つまり素数$p$と非負整数$m$があって$n=p^m$と書ける場合について証明します.このとき
$$\begin{array}{rl}\sum _{d|n}\phi (d)& =\sum _{k=0}^m\phi (p^k)=1+\sum _{k=1}^m(p^k-p^{k-1})\\ & =1+p^m-p^0=p^m=n\end{array}$$
よりphinowaは成り立ちます.
次に$s_{\phi }(n):=\sum _{d|n}\phi (d)$とおいて$s_{\phi }$が乗法的であることを示します.これが示されれば,素数冪の場合の結果からphinowaがわかります.$n,m$を互いに素な自然数とします.phihazyouhoutekiより
$$\begin{array}{rl}{s}_{\phi }(n)s_{\phi }(m)& =(\sum _{d|n}\phi (d))(\sum _{l|m}\phi (l))=\sum _{d|n}\sum _{l|m}\phi (dl)\end{array}$$
です.$d,l$の取り方から$dl|nm$です.逆に$t$を$nm$の正の約数とすると$t$が$n$の正の約数と$m$の正の約数の積として一意的に書けることを示しましょう.
$d=gcd(t,n),l=\frac{t}{d}$とします.定め方から$t=dl$であり,$d$は$t$の正の約数なので$l$は自然数です.定め方から$d$は$n$の約数であり,$\frac{t}{l}=d$と$t$が$nm$の約数であることから$l$は$nm$の約数であり,さらに$d$は$n$と$t$の最大公約数であることから$n$と$l(=\frac{t}{d})$は互いに素なので$l$は$m$の約数になります.
$n$の正の約数$d^{\prime }$と$m$の正の約数$l^{\prime }$があって$dl=d^{\prime }{l}^{\prime }$と書けたと仮定します.$d$と$l^{\prime }$,$d^{\prime }$と$l$は互いに素なので$d^{\prime }$は$d$の倍数であり,逆に$d$は$d^{\prime }$の倍数であるので$d=d^{\prime }$がわかり,これから直ちに$l=l^{\prime }$も従います.
従って$n$と$m$が互いに素なら
$$\begin{array}{r}{s}_{\phi }(n)s_{\phi }(m)=\sum _{d|n}\sum _{l|m}\phi (dl)=\sum _{t|nm}\phi (t)=s_{\phi }(nm)\end{array}$$
となり$s_{\phi }$は乗法的関数です.以上よりphinowaが示されました.

ちなみに,メビウス関数$\mu$を知っていればphikousikiの右辺を展開すると
$$\begin{array}{rl}\phi (n)& =\sum _{d|n}\mu (d)\frac{n}{d}\end{array}$$
であることがわかるので,メビウスの反転公式からphinowaの式が成立することがわかります.

syousyazouを写像$o:G\ni g\mapsto gx\in O(x)$に適用すればよいです.
実際この写像は軌道の定義より全射で,$g,h\in G$について,
$$\begin{array}{r}gx=hx\iff x=g^{-1}hx\iff g^{-1}h\in \mathrm{Stab}(x)\iff h\in g\mathrm{Stab}(x)\end{array}$$
なのでsyousyazouの書き方で
$$\begin{array}{r}G/{\sim }_o=G/\mathrm{Stab}(x)\end{array}$$
であり$\tilde{o}$はstaborbitのものになります.

$v_{i+n}=v_i$を満たすように頂点の添え字を整数の範囲まで広げておきます.
$\sigma$が表す図形で頂点$v_i$から出た辺は頂点$v_{\sigma (i)}$に入ります.この図形を$-\frac{2\pi k}{n}$だけ回転させて重なる図形が$\tau$で表されるとすると頂点$v_{i-k}$から出た辺は$v_{\sigma (i)-k}$に入ることになります.
これが$\sigma ={\alpha }^k\tau {\alpha }^{-k}$で書けることはは各元の行先を見ればわかります.

巡回群$\mathbb{Z}/n\mathbb{Z}$の部分群は$n$の正の約数$d$を用いて$⟨d⟩$と書けるもので尽くされます.よって
$$\begin{array}{r}{\mathfrak{S}}_n=\underset{d|n}{⨆}{\mathrm{Stab}}^{-1}(⟨d⟩)\end{array}$$
であり,staborbitより$\sigma \in {\mathrm{Stab}}^{-1}(⟨d⟩)$なら
$$\begin{array}{rl}|O(\sigma )|& =\frac{|\mathbb{Z}/n\mathbb{Z}|}{|\mathrm{Stab}(\sigma )|}=\frac{|\mathbb{Z}/n\mathbb{Z}|}{|⟨d⟩|}=\frac{n}{\left(\frac{n}{d}\right)}=d\end{array}$$
なので
$$\begin{array}{r}{E}_n=|(\mathbb{Z}/n\mathbb{Z})\mathrm{\setminus }{\mathfrak{S}}_n|=\sum _{d|n}\frac{1}{d}|{\mathrm{Stab}}^{-1}(⟨d⟩)|\end{array}$$
また定義より任意の$\mathbb{Z}/n\mathbb{Z}$の部分群$⟨d⟩$に対して次が成り立ちます.
$$\begin{array}{r}\sigma \in {\mathfrak{S}}_n^{⟨d⟩}⟺⟨d⟩\text{が}\mathrm{Stab}(\sigma )\text{の部分群}\end{array}$$
従って
$$\begin{array}{rl}{\mathfrak{S}}_n^{⟨d⟩}& =\underset{l|d}{⨆}{\mathrm{Stab}}^{-1}(⟨l⟩)\\ \therefore |{\mathfrak{S}}_n^{⟨d⟩}|& =\sum _{l|d}|{\mathrm{Stab}}^{-1}(⟨l⟩)|\end{array}$$
これらから次のように計算できます.
$$\begin{array}{rl}{E}_n& =\sum _{d|n}\frac{1}{d}|{\mathrm{Stab}}^{-1}(⟨d⟩)|=\frac{1}{n}\sum _{d|n}\frac{n}{d}|{\mathrm{Stab}}^{-1}(⟨d⟩)|\\ & =\frac{1}{n}\sum _{d|n}|{\mathrm{Stab}}^{-1}(⟨d⟩)|\sum _{l|\frac{n}{d}}\phi (l)=\frac{1}{n}\sum _{dl|n}|{\mathrm{Stab}}^{-1}(⟨d⟩)|\phi (l)\\ & =\frac{1}{n}\sum _{l|n}\phi (l)\sum _{d|\frac{n}{l}}|{\mathrm{Stab}}^{-1}(⟨d⟩)|=\frac{1}{n}\sum _{l|n}\phi (l)|{\mathfrak{S}}_n^{⟨\frac{n}{l}⟩}|\\ & =\frac{1}{n}\sum _{d|n}\phi \left(\frac{n}{d}\right)|{\mathfrak{S}}_n^{⟨d⟩}|\end{array}$$
１行目から２行目への変形はphinowaによります.

$\mathbb{Z}/n\mathbb{Z}$の${\mathfrak{S}}_n$への作用が$\mathbb{Z}/n\mathbb{Z}$から$\mathrm{Int}{\mathfrak{S}}_n\subset \mathrm{Aut}{\mathfrak{S}}_n$への準同型によって与えられていることから,$n$の任意の正の約数$d$について${\mathfrak{S}}_n^{⟨d⟩}$は${\mathfrak{S}}_n$の部分群になります.$d$を固定します.
$\pi :\mathbb{Z}/n\mathbb{Z}\to (\mathbb{Z}/n\mathbb{Z})/(d\mathbb{Z}/n\mathbb{Z})\cong \mathbb{Z}/d\mathbb{Z}$を自然な射影とします.
任意に$\sigma \in {\mathfrak{S}}_n^{⟨d⟩}$を取ります.まず全射$\pi \circ \sigma$について
$$\begin{array}{rl}\pi \circ \sigma (i)=\pi \circ \sigma (j)& ⟺\sigma (i)-\sigma (j)\in d\mathbb{Z}/n\mathbb{Z}\\ & ⟺i-j\in d\mathbb{Z}/n\mathbb{Z}\end{array}$$
であることを示します.一つ目の$\iff$は定義より明らかです.$\sigma \in {\mathfrak{S}}_n^{⟨d⟩}$より
$$\begin{array}{rlr}\sigma (i+d)& =\sigma (i)+d& (\mathrm{\forall }i\in \mathbb{Z}/n\mathbb{Z})\end{array}$$
なので二つ目の$\iff$の$\Leftarrow$はすぐわかります.さらに${\sigma }^{-1}\in {\mathfrak{S}}_n^{⟨d⟩}$でもあることから$\Rightarrow$もわかります.
これとsyousyazouから以下の図式を可換にする全単射$\mathrm{\Phi }(\sigma )($つまり$\pi \circ \sigma =\mathrm{\Phi }(\sigma )\circ \pi$を満たす全単射$\mathrm{\Phi }(\sigma ))$が一意に存在することがわかります.
$$\mathbb{Z}/n\mathbb{Z}\sigma \pi \mathbb{Z}/n\mathbb{Z}\pi (\mathbb{Z}/n\mathbb{Z})/(d\mathbb{Z}/n\mathbb{Z})\mathrm{\exists }!\mathrm{\Phi }(\sigma )(\mathbb{Z}/n\mathbb{Z})/(d\mathbb{Z}/n\mathbb{Z})\circlearrowright$$
この対応$\mathrm{\Phi }:{\mathfrak{S}}_n^{⟨d⟩}\to {\mathfrak{S}}_d$は定め方から群準同型です（以下の図式を参照）.
$$\mathbb{Z}/n\mathbb{Z}\sigma \pi \mathbb{Z}/n\mathbb{Z}\pi \tau \mathbb{Z}/n\mathbb{Z}\pi (\mathbb{Z}/n\mathbb{Z})/(d\mathbb{Z}/n\mathbb{Z})\mathrm{\exists }!\mathrm{\Phi }(\sigma )\mathrm{\exists }!\mathrm{\Phi }(\tau \sigma )(\mathbb{Z}/n\mathbb{Z})/(d\mathbb{Z}/n\mathbb{Z})\mathrm{\exists }!\mathrm{\Phi }(\tau )\circlearrowright (\mathbb{Z}/n\mathbb{Z})/(d\mathbb{Z}/n\mathbb{Z})\circlearrowright$$
また$\mathrm{\Psi }:{\mathfrak{S}}_d\to {\mathfrak{S}}_n^{⟨d⟩}$を
$$\begin{array}{rlr}\mathrm{\Psi }(\sigma )(i+kd)& =\sigma (i)+kd& (1\le i\le d,0\le k<\frac{n}{d})\end{array}$$
によって定めることができて,$\mathrm{\Phi }\circ \mathrm{\Psi }={\mathrm{id}}_{{\mathfrak{S}}_d}$であるので$\mathrm{\Phi }$は全射です.
$$\begin{array}{rl}\ker \mathrm{\Phi }& =\{\sigma \in {\mathfrak{S}}_n^{⟨d⟩}\mid \sigma (i)-i\in d\mathbb{Z}/n\mathbb{Z}(\mathrm{\forall }i\in \mathbb{Z}/n\mathbb{Z})\}\end{array}$$
であり,${\mathfrak{S}}_n^{⟨d⟩}$の元は$1,...,d$の$d$個の行先を定めれば決まることに注意すると,写像
$$\begin{array}{r}\ker \mathrm{\Phi }\ni \sigma ⟼(\sigma (1)-1,...,\sigma (d)-d)\in (d\mathbb{Z}/n\mathbb{Z}{)}^d\end{array}$$
は単射です.逆に任意の$(k_1,...,k_d)\in (d\mathbb{Z}/n\mathbb{Z}{)}^d$に対して$\sigma (1)=1+k_1,...,\sigma (d)=d+k_d$によって$\ker \mathrm{\Phi }$の元が一つ定まるのでこの写像は全単射であることがわかります.従って
$$\begin{array}{r}|\ker \mathrm{\Phi }|={\left(\frac{n}{d}\right)}^d\end{array}$$
がわかります.準同型定理より
$$\begin{array}{r}|{\mathfrak{S}}_n^{⟨d⟩}|=|\ker \mathrm{\Phi }||\mathrm{Im}\mathrm{\Phi }|={\left(\frac{n}{d}\right)}^{d}d!\end{array}$$
です.これとwanokakikaeより
$$\begin{array}{rl}{E}_n& =\frac{1}{n}\sum _{d|n}\phi \left(\frac{n}{d}\right)|{\mathfrak{S}}_n^{⟨d⟩}|=\frac{1}{n}\sum _{d|n}\phi \left(\frac{n}{d}\right){\left(\frac{n}{d}\right)}^{d}d!\\ & =\sum _{d|n}\phi \left(\frac{n}{d}\right){\left(\frac{n}{d}\right)}^{d-1}(d-1)!\end{array}$$
以上よりkotaeが示されました.