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

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} 番の座席に座るのを「同じ座席に座った」と解釈する.