ちょっとした計算:[x^i y^j]1/(1-x)^2(1-x-y)^2

ARC203Cにかなり苦戦したが、そこで次のような計算が出てきたので紹介する。（本来の考察の順番としては後半のステップが最初にあるんだけど、そこからすぐうまくいくのが気づかなかった）

問題

\[[x^i y^j] \frac{1}{(1-x-y)^2 (1-x)^2}\]

を求めよ。

解法

\[\frac{1}{(1-x-y)^2 (1-x)^2} = \left( \frac{1}{1-x-y} - \frac{1}{1-x} \right) ^2 y^{-2}\]

なので

\[[x^i y^j] \frac{1}{(1-x-y)^2 (1-x)^2} = [x^i y^{j+2}] \left( \frac{1}{1-x-y} - \frac{1}{1-x} \right) ^2\]

ここで括弧の中は \(\sum_{i \ge 0} (x+y)^i - x^i\) となっている。 これを組合せ論的に解釈しよう。次の操作を考える。

非負整数$n$を選び、長さ$n$の$01$列を作る。ただし少なくとも1つの$1$が列に含まれなければならない

$x$が$0$に、$y$が$1$に対応する。 操作を2回行い、できた列を連結する。列に$0$が$i$個、$1$が$j$個含まれるような一連の操作の数が、もとめるものである。これは次のように数えられる。$i$個の$0$と$j+3$個の$1$を一列に並べる。その後$ 1 \le k \le j+1 $を満たす$k$を選び、$k$番目に出現する$1$の前と後で列を分割する（$k$番目の$1$は捨てる）。前の列が$1$回目の操作に対応し、後の列が$2$回目の操作に対応する。このような場合の数は$(j+1)\binom{i+j+3}{i}$である。