FPS24 F - 色紙
青の色紙を$ x枚，黄色の色紙を$ y枚作るとした時，$ \frac{N!}{x!y!(N-x-y)!} だけ答えに寄与する．
赤，青，黄の指数型母関数はそれぞれ$ 1+x+\frac{1}{2}x^2+\frac{1}{3!}x^3+\cdots, $ 1+\frac{1}{2}x^2+\frac{1}{4!}x^4+\cdots,$ x+\frac{1}{3!}x^3+\frac{1}{5!}x^5+\cdots に対応する．
Taylor展開を考えるとそれぞれ$ e^x, \frac{e^x+e^{-x}}{2}, \frac{e^x-e^{-x}}{2} であり，その積は$ \frac{e^{3x}-e^{-x}}{4} である．この$ x^Nの項は$ \frac{3^N-(-1)^N}{4 \cdot (N!)} なので，求める答えは$ N!倍した$ \frac{3^N-(-1)^N}{4}である．
コメント
4項の線形漸化式ができるから行列累乗でも解けそう．
ラベル付きの物体をカウントすることが指数型母関数と対応するのね．