OMC215(H) - 母関数を使う方法

$\{1,2,\cdots,n\}$ の置換 $\sigma$ に対してその固定点の個数を $F(\sigma)$ とすると $$a_n=\sum_{\sigma}2^{F(\sigma)}6^{n-F(\sigma)}$$ が成り立つ（$n$個の正三角形がどのように入れ替わるかを指定したあと，それぞれの頂点がどのように入れ替わるかを指定することを考えればわかる）．$|F(\sigma)|=0$ となる置換の総数（モンモール数）を $M_n$ とすると，$|F(\sigma)|=k$ となる置換の総数は $\binom{n}{k}M_{n-k}$ なので $$a_n=\sum_{k=0}^n\binom{n}{k}M_{n-k}2^k6^{n-k}$$ となる．よって$a_n$の指数型母関数は $$\sum_{n=0}^\infty\dfrac{a_n}{n!}x^n=\biggl(\sum_{i=0}^\infty\dfrac{2^i}{i!}x^i\biggr)\biggl(\sum_{j=0}^\infty\dfrac{M_j6^j}{j!}x^j\biggr)=e^{2x}\cdot \dfrac{e^{-6x}}{1-6x} = \dfrac{e^{-4x}}{1-6x}$$ である．両辺に $1-6x$ を掛けると $$\sum_{n=0}^\infty\dfrac{a_{n+1}-(6n+6)a_n}{(n+1)!}x^{n+1}=e^{-4x}$$ となるため $a_{n+1}-(6n+6)a_n$ が等比数列であることがわかる．あとは公式解説と同様である．