ピクロスの削り方の総数

昨日の話の続きです。

例えば、次のような列の削り方の総数は何通りあるでしょうか？



１３２□□□□□□□□□□□

これから考えるのは、これを一般化した問題です。

それでは、一般化します。
ヒントにある数字の個数を k とおくと、それぞれの削るマスの列の間には最低 1 個の空白が必要なので、各数字を $a_i$ ( $1 \leq i \leq k$ ) で表したとき、列のマス数が n なら
$k-1+\sum_{i=1}^k a_i \leq n$
が成り立っています。
このとき、可能な削り方の総数は何通りか。

[ 解答1 ]
空白のマスの総数は
$n-\sum_{i=1}^k a_i$
で、これを m とおきます。
そして、まずは空白のマスを全て一列に並べます。
それから、それぞれの空白のマスの間、もしくは両端に、削るマスの列を k 個、挿入すると考えます。



｜□｜□｜…｜□｜□｜ （□は m 個、｜は m+1 個）

この m+1 個の｜の中から k 個を選ぶ総数が、もとめる総数に等しく、
${}_{m+1}C_k$
が答え、ということになります。

めでたし。

実は、もっと泥臭いやり方もあります。

[ 解答2 ]
(1) k=1 のとき
$n-a_1+1 = n-s+1 = m+1$
であることが、簡単に確かめられます。
(2) k=2 のとき
場合分けしまぷ。
(2-1) 列の両端に空白のマスがあるとき
空白の列は、間に削る列を 2 個挟むので、3 個あります。



□…□■…■□…□■…■□…□

空白のマスは m 個あるので、これを順序を考慮して 3 個に分割する総数を求めればよいわけです。
これは、m 個の空白のマスの隙間 m-1 箇所から 2 箇所を選んで仕切りを入れればよいので
${}_{m-1}C_2$
となります。
(2-2) 列の片方の端だけに空白のマスがあるとき
空白の列は 2 個あるので、上と同様に考え、左と右を合わせて
${}_{m-1}C_{2-1} \times 2$
です。
(2-3) 列の両端に空白のマスがないとき



■…■□…□■…■

の 1 通りです。
これらの和をとると
${}_{m-1}C_2+{}_{m-1}C_{2-1} \times 2+1$
$=\frac{(m-1)(m-2)}{2}+2(m-1)+1$
$=\frac{m(m+1)}{2}$
となります。
(3) $k \geq 3$ のとき
また場合分けしまぷ。
(3-1) 列の両端に空白のマスがあるとき
(2) と同様に考えて
${}_{m-1}C_k$
だ。
(3-2) 列の片方の端だけに空白のマスがあるとき
(2) と同様に考えて
${}_{m-1}C_{k-1} \times 2$
ですよ。
(3-3) 列の両端に空白のマスがないとき
空白の列は k-1 個なので
${}_{m-1}C_{k-1}$
なのね。
以上により、
${}_{m-1}C_k + {}_{m-1}C_{k-1} + {}_{m-1}C_{k-1} + {}_{m-1}C_{k-2}$
$={}_mC_k + {}_mC_{k-1}$
$={}_{m+1}C_k$
となります。
また、これが (1) と (2) の場合についても成り立つことが分かります。
したがって、これが求めるものです。

めでたし。

実は、最初は解答2のやり方で答えを導いたのですが、その式を見て、解答1のやり方を思いつきました。
結果オーライ、ってことで。