問題
を2以上の自然数，とを自然数とする。1からまでの番号がついた個の白玉，1からまでの番号がついた個の赤玉を用意する。これら白玉と赤玉を，1番から番まで番号づけられた個の箱それぞれに，小さい番号から順に白玉は個ずつ，赤玉は個ずつ配分しておく。たとえば，1番の箱には番号1からの白玉と番号1からの赤玉が入っている。これら個の玉を個の箱に以下のように再配分する。1番の箱から1個の玉を取り出して2番の箱に移し，次に2番の箱から1個の玉を取り出して3番の箱に移す。同様の操作を順次繰り返し最後に番の箱に1個の玉を移して終了する。このようにして実現され得る再配分の総数をとし，番の箱の白玉が個であるような再配分の総数をとする。
(1) を求めよ．
(2) とを求めよ．
(3) とを求めよ．
方針
各箱にもともと入っている玉の総数を とおく。再配分は、各境界で右へ移された玉の列によって一意に決まる。最初の移動は箱1にもともとある 個から選ぶ。2回目以降は、直前に左から入ってきた玉をそのまま右へ送るか、その箱にもともとあった 個から新しく選ぶかの 通りである。 は最後に箱nへ入る玉が白である場合を数えればよい。
解答
白玉と赤玉を合わせて、各箱にもともと入っている玉の個数を とおく。玉には番号がついているので、同じ色でも別の玉として区別する。
一連の操作で、各境界を右へ越える玉を順に見る。1回目は箱1にもともと入っている 個の玉から1個を選ぶ。2回目以降は、その箱に左から移ってきた玉をそのまま右へ送るか、その箱にもともと入っていた 個の玉から1個を新しく選ぶかである。したがって、2回目以降の各操作には 通りの選択がある。
(1)
のとき、操作は箱1から箱2へ1個移すだけである。選べる玉は箱1にもともと入っている 個なので である。
(2)
のとき、1回目の移動は 通りである。2回目、つまり箱2から箱3への移動では、直前に箱1から来た玉を送る場合が1通り、箱2にもともとあった玉を送る場合が 通りある。よって である。
次に を求める。箱3の白玉が 個になるのは、最後に箱3へ入る玉が白玉であるときである。最後の移動で白玉が送られる場合は、次の2種類である。
1つ目は、1回目に箱1の白玉を選び、それを2回目にそのまま箱3へ送る場合である。これは 通りである。2つ目は、1回目にどの玉を選んでもよく、2回目に箱2にもともとあった白玉を新しく選ぶ場合である。これは 通りである。
したがって である。
(3)
のとき、1回目は 通り、2回目と3回目はそれぞれ 通りである。よって である。
また は、最後に箱4へ入る玉が白玉である場合の数である。最後に白玉を送る選択は、最初から白玉を選んでそれを運び続けてもよいし、途中の箱でもともとあった白玉を新しく選んでもよい。一般に、最後の移動で白玉を送るには、最後に白玉を選ぶ段階を1つ決め、その前の選択は自由に続けられる。
具体的には、1回目に箱1の白玉を選んでそれを2回続けて送る場合が 通り、2回目に箱2の白玉を新しく選んでそれを最後に送る場合が 通り、3回目に箱3の白玉を新しく選ぶ場合が 通りという見方でも数えられる。合計は である。したがって である。