MathLabs

第4問

n>0n>0 を整数とする。天秤と、重さが 20,21,…,2n−12^0,2^1,\dots,2^{n-1} である nn 個のおもりが与えられている。nn 個のおもりを一つずつ天秤に載せていくとき、右の皿が左の皿より重くなることが決してないようにしたい。各段階で、まだ載せていないおもりを一つ選び、左の皿か右の皿のいずれかに載せる操作を、すべてのおもりを載せ終わるまで続ける。このような載せ方の総数を求めよ。
ステップ 5/5: 漸化式を展開して閉じた形にする
ざっくり言うと

ちょうど 2n-1 対 1 の対応は、数え上げの式では直接掛け算になり、下から順にすべての奇数の因子を掛け合わせると二重階乗が得られる。

f(n)=(2n−1)f(n−1)f(n)=(2n-1)f(n-1)
詳しい解説

n−1n-1 個の重りの有効な配置はどれも忘却写像のもとで正確に 2n−12n-1 個の原像を持つので、n≥2n\ge2 に対して f(n)=(2n−1)f(n−1)f(n)=(2n-1)f(n-1) が成り立ち、f(1)=1f(1)=1 と合わせて成立する。展開すると f(n)=(2n−1)(2n−3)⋯3⋅1⋅f(1)f(n)=(2n-1)(2n-3)\cdots3\cdot1\cdot f(1) となり、f(n)=1⋅3⋅5⋯(2n−1)=(2n−1)!!f(n)=1\cdot3\cdot5\cdots(2n-1)=(2n-1)!!:nn 個すべての重りを配置する有効な方法の数は最初の nn 個の奇数の積である。