FPS24 L - 順列 2
長さ2以下のサイクルが含まれないようなサイクルの集合を求める．
$ N頂点からなるサイクルグラフは$ (N-1)!通り存在する．サイクルのEGFは$ \sum_{j=1}^\infty \frac{x^j}{j}=-\ln (1-x)と書け，今回の場合は頂点数2以下のものを除くので$ \sum_{j=3}^\infty \frac{x^j}{j}=-\ln (1-x)-x-\frac{x^2}{2}である．
ラベル付きの物体のEGFをラベル付きの物体の集合のEGFに変換するには$ \exp(A(x))とするだけで良いので，求めるEGFは$ \exp(-\ln (1-x)-x-\frac{x^2}{2})=\frac{1}{1-x}\exp(-x-\frac{x^2}{2})である．
コメント
自分で似たようなの作問しといてよかった〜