問題
を2以上の自然数，とを自然数とする．1からまでの番号がついた個の白玉，1からまでの番号がついた個の赤玉を用意する．これら白玉と赤玉を，1番から番まで番号づけられた個の箱それぞれに，小さい番号から順に白玉は個ずつ，赤玉は個ずつ配分しておく．たとえば，1番の箱には番号1からの白玉と番号1からの赤玉が入っている．これから個の玉を個の箱に以下のように再配分する．1番の箱から1個の玉を取り出して2番の箱に移し，次に2番の箱から1個の玉を取り出して3番の箱に移す．同様の操作を順次繰り返し最後に番の箱に1個の玉を移して終了する．このようにして実現され得る再配分の総数をとし，番の箱の白玉が個であるような再配分の総数をとする．
(1) ，を求めよ．
(2) を求めよ．
(3) を求めよ．
(4) を求めよ．
方針
各箱にもともとある玉の総数を とし、右へ移される玉の列を数える。最初は 通り、2回目以降は「直前の玉をそのまま送る」1通りと「その箱にもともとある玉を新しく送る」 通りで、合計 通りである。 はこの積で求まる。 は最後にn番の箱へ入る玉が白である場合であり、同じ構造から を得る。差分は一般式から、または最後の一段を伸ばす数え方で求める。
解答
各箱にもともと入っている玉の総数を とおく。玉には番号がついているので、同じ色でも別々の玉として区別する。
各操作で右隣へ移される玉を順に見れば、最終的な再配分はその列で決まる。1回目は箱1にもともとある 個から選ぶので 通りである。2回目以降は、直前に左から入ってきた玉をそのまま右へ送る1通り、またはその箱にもともとある 個から新しく選ぶ 通りで、合わせて 通りである。
(1)
のとき、2番の箱へ入る玉が白玉であるためには、箱1の白玉を選べばよい。箱1には白玉が 個あるので である。
のとき、3番の箱へ最後に入る玉が白玉である場合を数える。1回目に箱1の白玉を選び、それを2回目にそのまま送る場合が 通りある。また、1回目には任意の 個のどれを選んでもよく、2回目に箱2にもともとある白玉を新しく選ぶ場合が 通りある。したがって である。
(2)
個の箱では、操作は 回行われる。1回目が 通り、残りの 回がそれぞれ 通りなので である。すなわち である。
(3)
まず の構造を考える。最後にn番の箱へ入る玉が白玉なら、n番の箱の白玉はもともとの 個に1個増えて 個になる。逆に、n番の箱の白玉が 個になるには、最後に入る玉が白玉でなければならない。
最後に入る玉を白玉にするには、最初または途中のどこかで白玉を新しく選び、その後はそれを送ってもよいし、途中で別の選択をして最終的に白玉を選んでもよい。各段階での選択構造は、最後の色だけを指定した場合、最初に白玉を選ぶ 通りと、その後の 回の選択 通りで整理できる。したがって である。
よって であり、 となる。すなわち である。
(4)
(3)で述べた通り、最後に送られる玉が白玉である場合を直接数えると である。したがって である。