いろはちゃんコンテスト Day2 E - 連呼

• 問題
• AC

AAAが登場しない列を数えて$\binom{N+M-2}{N}$から引く方針が良さそう。

とりあえず、最初の文字と最後の文字の制限がないとして考えてみる。AAAが登場しない列とは、AとAAを$M$個のBの間に挿入してできる列である。Aを$d$個にわけるとして、Aが$x$個、AAが$y$個になったとすると、

$x + 2y = N$

$x+y = d$

より、$y = N-d, x = 2d-N$と整理できる。AとAAの並べ方は$\binom{d}{y }$通りあり、$M$個のBへの挿入の仕方は（両端を含めると）$\binom{M+1}{d}$通りある。したがって、総和は$\sum_d \binom{M+1}{d}\binom{d}{y}$となる。（有効な$d$についてだけ計算する。）

さて、最初の文字がAで最後の文字がBという制限を満たすものを数える。最初がABから始まるパターンとAAから始まるパターンにわけて数えることにする。

最初がABから始まる場合、最後がBなので、AB·B·...·Bの·で示した$M-1$箇所から選んでAかAAを挿入することになる。総和は$\sum_d \binom{M-1}{d} \binom{d}{y}$である。ただし、$x+2y = N-1, x+y =d$ だから$y = N-1-d$である。

最初がAAから始まる場合、AAB·B·...·Bの·で示した$M-1$箇所から選んでAかAAを挿入することになる。総和はやはり$\sum_d \binom{M-1}{d} \binom{d}{y}$である。ただし、$x+2y = N-2, x+y=d$ だから$y=N-2-d$である。