離散数学・組合せ論の問題

方針 上昇階乗について
$$x(x+1)\cdots (x+n-1)=\sum _{k=1}^n\left[\genfrac{}{}{0ex}{}{n}{k}\right]x^k$$
が成り立つ。ここで $\left[\genfrac{}{}{0ex}{}{n}{k}\right]$ は第 1 種スターリング数で、$n$ 文字の置換のうち巡回（不動点も長さ $1$ の巡回として数える）がちょうど $k$ 個のものの個数である。与えられた式は $n=5$ の場合なので、求める係数は $\left[\genfrac{}{}{0ex}{}{5}{2}\right]$ である。

漸化式で表を作る 漸化式
$$\left[\genfrac{}{}{0ex}{}{n}{k}\right]=\left[\genfrac{}{}{0ex}{}{n-1}{k-1}\right]+(n-1)\left[\genfrac{}{}{0ex}{}{n-1}{k}\right]$$
と、$\left[\genfrac{}{}{0ex}{}{n}{n}\right]=1$、$k=0$ や $k>n$ のときは $0$（ただし $n\ge 1$）であることを使って順に計算する。

• $n=1$: $\left[\genfrac{}{}{0ex}{}{1}{1}\right]=1$
• $n=2$: $\left[\genfrac{}{}{0ex}{}{2}{1}\right]=0+1\cdot 1=1$, $\left[\genfrac{}{}{0ex}{}{2}{2}\right]=1$
• $n=3$: $\left[\genfrac{}{}{0ex}{}{3}{1}\right]=0+2\cdot 1=2$, $\left[\genfrac{}{}{0ex}{}{3}{2}\right]=\left[\genfrac{}{}{0ex}{}{2}{1}\right]+2\left[\genfrac{}{}{0ex}{}{2}{2}\right]=1+2=3$
• $n=4$: $\left[\genfrac{}{}{0ex}{}{4}{1}\right]=0+3\cdot 2=6$, $\left[\genfrac{}{}{0ex}{}{4}{2}\right]=\left[\genfrac{}{}{0ex}{}{3}{1}\right]+3\left[\genfrac{}{}{0ex}{}{3}{2}\right]=2+9=11$
• $n=5$: $\left[\genfrac{}{}{0ex}{}{5}{2}\right]=\left[\genfrac{}{}{0ex}{}{4}{1}\right]+4\left[\genfrac{}{}{0ex}{}{4}{2}\right]=6+4\cdot 11=50$

検算 直接展開しても確かめられる。$x(x+1)(x+2)(x+3)(x+4)$ の $x^2$ の係数は、$(x+1)(x+2)(x+3)(x+4)$ の $x^1$ の係数に等しい。これは $4$ つの因数のうち $1$ つから $x$ を、残り $3$ つから定数を選んだ積の和なので
$$2\cdot 3\cdot 4+1\cdot 3\cdot 4+1\cdot 2\cdot 4+1\cdot 2\cdot 3=24+12+8+6=50$$
となり、一致する。

よって求める係数は $50$ である。

$x(x+1)(x+2)(x+3)(x+4)=x\cdot P(x)$、ただし $P(x)=(x+1)(x+2)(x+3)(x+4)$ とおく。$x^2$ の係数は $P(x)$ の $x$ の係数に等しい。

$P(x)$ の $x$ の係数は、4 つの因数のうち 3 つから定数項、1 つから $x$ を選ぶ和であり、$1,2,3,4$ から 3 つを選んだ積の和である。
$1\cdot 2\cdot 3+1\cdot 2\cdot 4+1\cdot 3\cdot 4+2\cdot 3\cdot 4=6+8+12+24=50$。

検算：$(x+1)(x+4)=x^2+5x+4$、$(x+2)(x+3)=x^2+5x+6$。$u=x^2+5x$ とおくと $P=(u+4)(u+6)=u^2+10u+24$。$u^2=x^4+10x^3+25x^2$ なので、$x$ の項は $10\cdot 5x=50x$ のみ。よって $P$ の $x$ の係数は 50 で一致する（第一種スターリング数の絶対値 $c(5,2)=50$ とも一致）。