MathLabs

第4题

设 n>0n>0 为整数。现有一架天平和 nn 个重量分别为 20,21,…,2n−12^0,2^1,\dots,2^{n-1} 的砝码。我们要依次把这 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 个奇数之积。