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

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

席替えの数理(その 3)

数学・組み合わせ

$f(n)=!n$ のもう一つの求め方.

今, 座席に ${1\sim k}$ の番号を付け, 元々 ${j}$ 番の座席に座っていた生徒を ${a_j}$ とする.
${1}$ 番の座席に ${a_k\ (2\leq k\leq n)}$ が座るとして

${k}$ 番の座席に ${a_1}$ が座るとき, 残りの ${(n-2)}$ 人が前と違う座席に座る場合の数が ${f(n-2)}$ 通り,
${k}$ 番の座席に ${a_1}$ が座らないとき, ${(n-1)}$ 人が前と違う座席に座る場合の数が ${f(n-1)}$ 通り*1

となるので, これと ${k}$ の選び方 ${(n-1)}$ 通りから
${f(n)=(n-1)(f(n-2)+f(n-1))}$
を導ける. 変形すると
${f(n)-nf(n-1)=-(f(n-1)-(n-1)f(n-2))}$
となるので, ${f(0)=1, f(1)=0}$ から
${f(n)-nf(n-1)=(-1)^{n-1}(f(1)-f(0))=(-1)^n}$
が導かれる. さらに変形を続けて
${\displaystyle\frac{f(n)}{n!}-\frac{f(n-1)}{(n-1)!}=\frac{(-1)^n}{n!}}$
だから
${\displaystyle\frac{f(n)}{n!}-\frac{f(0)}{0!}=\sum_{k=1}^n\frac{(-1)^k}{k!}}$
となり, 再び ${f(0)=1}$ により
${\displaystyle\frac{f(n)}{n!}=1+\sum_{k=1}^n\frac{(-1)^k}{k!}=\sum_{k=0}^n\frac{(-1)^k}{k!}.}$

*1: ${a_1}$ が ${k}$ 番の座席に座るのを「同じ座席に座った」と解釈する.