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

$\sim_f$が同値関係であることは省略.
まず$f=\tilde{f}\circ i$を満たす$\tilde{f}$が一意に存在することを示します.$x\in X$に対して$i(x)=[x]$と書きます.このとき$\tilde{f}$としてありうるのは
$$ \tilde{f}:X/{\sim_f}\ni[x]\longmapsto 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$と互いに素$\Leftrightarrow$$\{p_1$の倍数でない$\}\cap\cdots\cap\{ p_r$の倍数でない$\}$
に注意します.$A_{p_i}=\{k\in\{1,...,n\}\mid k\text{は$p_i$の倍数} \}$とすると
\begin{align*} \varphi(n) &= |A_{p_1}^{c}\cap\cdots\cap A_{p_r}^{c}|\\ &=n-|A_{p_1}\cup\cdots\cup A_{p_r}|\\ &=n+\sum_{\substack{1\leq i_1 <\cdots< i_k\leq r\\1\leq k\leq r}}(-1)^{k}|A_{p_{i_1}}\cap\cdots\cap A_{p_{i_k}}|\\ &=n+\sum_{\substack{1\leq i_1 <\cdots< i_k\leq r\\1\leq k\leq r}}\frac{(-1)^k n}{p_{i_1}\cdots p_{i_k}}\\ &= n\prod_{i=1}^{r}{\left(1-\frac{1}{p_i}\right)} \end{align*}
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{align*} \varphi(n)\varphi(m) &=\left(n\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right)\right)\left(m\prod_{j=1}^{s}\left(1-\frac{1}{q_j}\right)\right)\\ &=nm\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right)\prod_{j=1}^{s}\left(1-\frac{1}{q_i}\right)\\ &=\varphi(nm) \end{align*}

まず$n$が素数冪の場合,つまり素数$p$と非負整数$m$があって$n=p^{m}$と書ける場合について証明します.このとき
\begin{align*} \sum_{d|n}\varphi(d)&=\sum_{k=0}^{m}\varphi(p^{k}) =1+\sum_{k=1}^{m}{(p^k-p^{k-1})}\\ &=1+p^m-p^0=p^m=n \end{align*}
よりphinowaは成り立ちます.
次に$s_{\varphi}(n)\coloneqq\sum_{d|n}\varphi(d)$とおいて$s_{\varphi}$が乗法的であることを示します.これが示されれば,素数冪の場合の結果からphinowaがわかります.$n,m$を互いに素な自然数とします.phihazyouhoutekiより
\begin{align*} s_{\varphi}(n)s_{\varphi}(m) &=\left(\sum_{d|n}\varphi(d)\right)\left(\sum_{l|m}\varphi(l)\right) =\sum_{d|n}\sum_{l|m}\varphi(dl) \end{align*}
です.$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'$と$m$の正の約数$l'$があって$dl=d'l'$と書けたと仮定します.$d$と$l'$,$d'$と$l$は互いに素なので$d'$は$d$の倍数であり,逆に$d$は$d'$の倍数であるので$d=d'$がわかり,これから直ちに$l=l'$も従います.
従って$n$と$m$が互いに素なら
\begin{align*} s_{\varphi}(n)s_{\varphi}(m) =\sum_{d|n}\sum_{l|m}\varphi(dl) = \sum_{t|nm}\varphi(t) =s_{\varphi}(nm) \end{align*}
となり$s_{\varphi}$は乗法的関数です.以上よりphinowaが示されました.

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

syousyazouを写像$o:G\ni g\mapsto gx\in O(x)$に適用すればよいです.
実際この写像は軌道の定義より全射で,$g,h\in G$について,
\begin{align*} gx=hx \Leftrightarrow x=g^{-1}hx \Leftrightarrow g^{-1}h\in\Stab(x) \Leftrightarrow h\in g \Stab(x) \end{align*}
なのでsyousyazouの書き方で
\begin{align*} G/{\sim_{o}}=G/\Stab(x) \end{align*}
であり$\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$を用いて$\langle d\rangle$と書けるもので尽くされます.よって
\begin{align*} \mathfrak{S}_n = \bigsqcup_{d|n}\Stab^{-1}(\langle d \rangle) \end{align*}
であり,staborbitより$\sigma\in\Stab^{-1}(\langle d \rangle)$なら
\begin{align*} |O(\sigma)| &= \frac{|\mathbb{Z}/n\mathbb{Z}|}{|\Stab(\sigma)|} = \frac{|\mathbb{Z}/n\mathbb{Z}|}{|\langle d \rangle|} = \cfrac{n}{\left(\cfrac{n}{d}\right)} = d \end{align*}
なので
\begin{align*} E_n=|(\mathbb{Z}/n\mathbb{Z})\backslash\mathfrak{S}_n|=\sum_{d|n}{\frac{1}{d}|\Stab^{-1}(\langle d \rangle)|} \end{align*}
また定義より任意の$\mathbb{Z}/n\mathbb{Z}$の部分群$\langle d \rangle$に対して次が成り立ちます.
\begin{align*} \sigma\in\mathfrak{S}_n^{\langle d \rangle} \Longleftrightarrow\text{ $\langle d \rangle$が$\Stab(\sigma)$の部分群} \end{align*}
従って
\begin{align*} \mathfrak{S}_n^{\langle d \rangle} &= \bigsqcup_{l|d}\Stab^{-1}(\langle l \rangle)\\ \therefore |\mathfrak{S}_n^{\langle d \rangle}| &= \sum_{l|d}|\Stab^{-1}(\langle l \rangle)| \end{align*}
これらから次のように計算できます.
\begin{align*} E_n &= \sum_{d|n}{\frac{1}{d}|\Stab^{-1}(\langle d \rangle)|} =\frac{1}{n}\sum_{d|n}{\frac{n}{d}|\Stab^{-1}(\langle d \rangle)|}\\ &=\frac{1}{n}\sum_{d|n}{|\Stab^{-1}(\langle d \rangle)|}\sum_{l|\frac{n}{d}}\varphi(l) =\frac{1}{n}\sum_{dl|n}{|\Stab^{-1}(\langle d \rangle)|}\varphi(l)\\ &=\frac{1}{n}\sum_{l|n}{\varphi(l)}\sum_{d|\frac{n}{l}}|\Stab^{-1}(\langle d \rangle)| =\frac{1}{n}\sum_{l|n}{\varphi(l)|\mathfrak{S}_n^{\langle \frac{n}{l} \rangle}|}\\ &= \frac{1}{n}\sum_{d|n}\varphi\!\left(\frac{n}{d}\right)|\mathfrak{S}_n^{\langle d \rangle}| \end{align*}
１行目から２行目への変形はphinowaによります.

$\mathbb{Z}/n\mathbb{Z}$の$\mathfrak{S}_n$への作用が$\mathbb{Z}/n\mathbb{Z}$から$\Int\mathfrak{S}_n\subset\Aut\mathfrak{S}_n$への準同型によって与えられていることから,$n$の任意の正の約数$d$について$\mathfrak{S}_n^{\langle d \rangle}$は$\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^{\langle d \rangle}$を取ります.まず全射$\pi\circ\sigma$について
\begin{align*} \pi\circ\sigma(i)=\pi\circ\sigma(j) &\Longleftrightarrow \sigma(i)-\sigma(j)\in d\mathbb{Z}/n\mathbb{Z}\\ &\Longleftrightarrow i-j \in d\mathbb{Z}/n\mathbb{Z} \end{align*}
であることを示します.一つ目の$\Leftrightarrow$は定義より明らかです.$\sigma\in\mathfrak{S}_n^{\langle d \rangle}$より
\begin{align*} \sigma(i+d)&=\sigma(i)+d &(\forall i \in \mathbb{Z}/n\mathbb{Z}) \end{align*}
なので二つ目の$\Leftrightarrow$の$\Leftarrow$はすぐわかります.さらに$\sigma^{-1}\in\mathfrak{S}_n^{\langle d \rangle}$でもあることから$\Rightarrow$もわかります.
これとsyousyazouから以下の図式を可換にする全単射$\Phi(\sigma)\;($つまり$\pi\circ\sigma=\Phi(\sigma)\circ\pi$を満たす全単射$\Phi(\sigma) )$が一意に存在することがわかります.
\begin{xy}\xymatrix{ \mathbb{Z}/n\mathbb{Z} \ar[rr]^{\sigma} \ar[d]_{\pi} && \mathbb{Z}/n\mathbb{Z} \ar[d]^{\pi} \\ (\mathbb{Z}/n\mathbb{Z})/(d\mathbb{Z}/n\mathbb{Z}) \ar@{.>}[rr]^{\exists! \Phi(\sigma)} && (\mathbb{Z}/n\mathbb{Z})/(d\mathbb{Z}/n\mathbb{Z}) \ar@{}[llu]|{\large{\circlearrowright}} \\ }\end{xy}
この対応$\Phi:\mathfrak{S}_n^{\langle d \rangle}\to\mathfrak{S}_d$は定め方から群準同型です（以下の図式を参照）.
\begin{xy}\xymatrix{ \mathbb{Z}/n\mathbb{Z} \ar[r]^{\sigma} \ar[d]_{\pi} & \mathbb{Z}/n\mathbb{Z} \ar[d]^{\pi} \ar[r]^{\tau}　& \mathbb{Z}/n\mathbb{Z} \ar[d]^{\pi} \\ (\mathbb{Z}/n\mathbb{Z})/(d\mathbb{Z}/n\mathbb{Z}) \ar@{.>}[r]^{\exists! \Phi(\sigma)} \ar@{.>}@/_15pt/[rr]_{\exists! \Phi(\tau\sigma)} & (\mathbb{Z}/n\mathbb{Z})/(d\mathbb{Z}/n\mathbb{Z}) \ar@{.>}[r]^{\exists! \Phi(\tau)} \ar@{}[lu]|{\large{\circlearrowright}} & (\mathbb{Z}/n\mathbb{Z})/(d\mathbb{Z}/n\mathbb{Z}) \ar@{}[lu]|{\large{\circlearrowright}} \\ }\end{xy}
また$\Psi:\mathfrak{S}_d\to\mathfrak{S}_n^{\langle d \rangle}$を
\begin{align*} \Psi(\sigma)(i+kd) &= \sigma(i)+kd & \left(1\leq i\leq d, 0\leq k < \frac{n}{d}\right) \end{align*}
によって定めることができて,$\Phi\circ\Psi=\mathrm{id}_{\mathfrak{S}_d}$であるので$\Phi$は全射です.
\begin{align*} \ker\Phi &= \{\sigma\in\mathfrak{S}_n^{\langle d \rangle} \mid \sigma(i)-i\in d\mathbb{Z}/n\mathbb{Z}\;(\forall i \in\mathbb{Z}/n\mathbb{Z}) \} \end{align*}
であり,$\mathfrak{S}_n^{\langle d \rangle}$の元は$1,...,d$の$d$個の行先を定めれば決まることに注意すると,写像
\begin{align*} \ker\Phi\ni\sigma\longmapsto(\sigma(1)-1,...,\sigma(d)-d)\in(d\mathbb{Z}/n\mathbb{Z})^d \end{align*}
は単射です.逆に任意の$(k_1,...,k_d)\in(d\mathbb{Z}/n\mathbb{Z})^d$に対して$\sigma(1)=1+k_1,...,\sigma(d)=d+k_d$によって$\ker\Phi$の元が一つ定まるのでこの写像は全単射であることがわかります.従って
\begin{align*} |\ker\Phi|=\left(\frac{n}{d}\right)^{d} \end{align*}
がわかります.準同型定理より
\begin{align*} |\mathfrak{S}_n^{\langle d \rangle}|=|\ker\Phi||\Im\Phi|=\left(\frac{n}{d}\right)^d d! \end{align*}
です.これとwanokakikaeより
\begin{align*} E_n &= \frac{1}{n}\sum_{d|n}\varphi\!\left(\frac{n}{d}\right)|\mathfrak{S}_n^{\langle d \rangle}| = \frac{1}{n}\sum_{d|n}\varphi\!\left(\frac{n}{d}\right)\left(\frac{n}{d}\right)^d d!\\ &= \sum_{d|n}\varphi\!\left(\frac{n}{d}\right)\left(\frac{n}{d}\right)^{d-1}\!(d-1)! \end{align*}
以上よりkotaeが示されました.