ACL Beginner Contest F - Heights and Pairs

• 問題
• AC

$h_i$が互いに異なる場合は$(2N-1)!! = (2N)! / 2^N N!$通りという有名事実がある（後述）。以下、$p_i = (2i-1)!!$とする。

身長$h$の人が$a_h$人いるとする。$i$人の同じ身長を持つ人から$j$ペアを作る場合の数は$\binom{i}{2j}p_j$である。$F(x) = \prod_h \sum_j \binom{a_h}{2j}p_j x^{j}$とすると、$F(x)$の$x^k$の係数$[x^k]F(x)$は$2N$人から身長が同じであるような$k$ペアを作る場合の数に等しい。このとき、残った人、つまり$2(N-k)$人でペアを作る場合の数は$p_{N-k}$通りであり、あとは包除で$\sum_k(-1)^kp_{N-k}([x^k]F(x))$通りと求まる。

$(2N-1)!!$について

$2N$人に$1, 2, ..., 2N$という番号を振ってこの順に並べ、二人ずつ取り除いていくとする。この際、ペアのうちの一人目は必ずその時点で番号が最小の人を選ぶ、としておくと完全な数え上げができる。一人目には$2N-1$通りの人がマッチできて、二人目には$2N-3$通りの人がマッチできて、……となるので二重階乗の記号を使うと$(2N-1)!!$と表せる。

別の考え方もできる。$2N$人を自由な順番で一列に並べて、隣り合う二人をくっつけて$N$ペアを作ることにする。並べ方は$(2N)!$通りあるが、二人組の内の順番は考慮しないので$2^N$で割る必要がある。さらに、$N$ペアの順番も考慮しないので$N!$で割って$(2N)!/(2^N N!)$と求まる。これらは二重階乗の公式も与えている:

$$(2N-1)!! = \frac{(2N)!}{2^N N!}$$