読者です 読者をやめる 読者になる 読者になる

Red cat の数学よもやま話・新装開店

はてなダイアリー「Red cat の数学よもやま話」から徐々にこちらに移行していきます。

席替えの数理(その 1)

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