席替えの数理(その 1) - Red cat の数学よもやま話・新装開店

${n}$ 人のクラスで席替えを行う. このとき, ちょうど ${k}$ 人が前と同じ座席になるような場合の数を ${h(n, k)}$ としよう.
すぐにわかることとして, 奇跡的にも全員が同じ座席になるような場合の数は 1 通りしかない. すなわち ${h(n, n)} = 1$ である. また, ちょうど ${n - 1}$ 人だけが同じ座席になるということはありえない(残る一人はどこに座るのか ?)から, ${h(n,n - 1) = 0}$ もわかる.
ちょっと考えると
$h(n, k)={n \choose k}h(n - k, 0)$
であることがわかる. つまり, 同じ座席に座る ${k}$ 人の選び方の場合の数と, それぞれに残りの ${(n - k)}$ 人が前と違う座席に座る場合の数の積になる.
さらにわかることは
$n! = \sum_{k = 0}^n h(n, k)$
である.

我々の当面の興味の対象は
${!n = h(n,0)}$
である.*1
${\begin{align} n! &= \sum_{k = 0}^n h(n, k) \\ &= \sum_{k = 0}^n {n \choose k}(!(n - k)) \\ &= \sum_{k = 0}^n {n \choose k}(!k) \\ \end{align}}$
に反転公式
$g(n) = \sum_{k = 0}^n {n \choose k}(- 1)^k f(k) \iff f(n) = \sum_{k = 0}^n {n \choose k}(- 1)^k g(k)$
を ${f(n) = (- 1)^n(!n), g(n) = n!}$ として適用すると
${\begin{align} !n &= (- 1)^n \sum_{k = 0}^n {n \choose k}(- 1)^k k! \\ &= \sum_{k = 0}^n \frac{n!}{(n - k)!}(- 1)^{n + k} \\ &= n!\sum_{k = 0}^n \frac{(- 1)^k}{k!} \end{align}}$
を得ることができる. 反転公式の証明は次回に. (続く)

*1:「コンピュータの数学」では n¡ と表記されていた.