問題
＋（プラス）と－（マイナス）を個でたらめに並べるとき，同符号が続く部分の長さの最大値が となる確率をで表す．（例：で＋＋－－－＋－＋＋＋）のときは，．）
(1) を求めよ．
(2) は，偶数であることを示せ．
(3) のとき，を求めよ．
方針
同じ符号が連続する最大の長さを、符号列の連続ブロックで数える。(1)は の例外を確認し、 では1つだけ違う符号が端または内部にある4通りを数える。(2)は全符号反転で2個ずつ組にする。(3)は のため、長さ のブロックが高々1つ、ただし 偶数かつ では2つあり得る、という分け方で数える。
解答
(1)
まず のときは、最大の長さが となる列は の2通りであるから である。
以下 とする。最大の長さが となるには、長さ の同符号のブロックが1つあり、残り1個だけが反対の符号でなければならない。反対の符号が左端にある場合と右端にある場合、さらに全体の符号を反転した場合があるので、該当する列は4通りである。したがって である。
(2)
任意の符号列について、すべての と を入れ替える。この操作をしても、同符号が続く部分の長さは変わらない。また、入れ替えた後の列がもとの列と一致することはない。したがって、最大の長さが である列全体は2個ずつ組に分けられる。よって、その個数である は偶数である。
(3)
まず のときは、すべて またはすべて の2通りなので である。
次に とする。このとき長さ のブロックは2つ同時には存在できない。長さ のブロックの符号を先に決めると2通りである。ブロックの左に 個、右に 個の文字があるとすると である。ブロックのすぐ左またはすぐ右に文字がある場合、その文字はブロックと反対の符号でなければならない。残りの文字は全部で 個または 個となり、どのように並べても長さ を超えるブロックはできない。 とおく。ブロックが端にある場合は2か所あり、それぞれ 通りである。ブロックが端でない場合は か所あり、それぞれ 通りである。したがって個数は である。つまり である。
最後に、 が偶数で の場合を考える。このとき上と同じ数え方では、長さ のブロックが2つある列
をそれぞれ2回数えている。したがって、 として得られる から2を引き、 である。
以上より、 では
である。