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

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

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

席替えの数理(その 2)

前回証明なしで使った反転公式
{\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)}
の証明.

{\begin{align}
\sum_{k=0}^n {n \choose k}(-1)^k g(k)
&= \sum_{k=0}^n {n \choose k}(-1)^k \sum_{j=0}^k {k \choose j}(-1)^j f(j) \\
&= \sum_{j=0}^n f(j)\sum_{k=j}^n {n \choose k}(-1)^{k+j}{k \choose j} \\
&= \sum_{j=0}^n f(j)\sum_{k=j}^n {n \choose j}(-1)^{k+j}{n-j \choose k-j} \\
&= \sum_{j=0}^n f(j) {n \choose j}\sum_{k=0}^{n-j} (-1)^k{n-j \choose k} \\
&= \sum_{j=0}^n f(j) {n \choose j}(-1)^{n-j}{n-j-1 \choose n-j} \\
&= f(n).
\end{align}}

さて,
{\displaystyle\frac{!n}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!}}
{n} が大きくなると急速に {1/e=0.367879\dots} に収束する. 従って, {n} が十分大きいとき, 席替えで全員が異なる座席に座る確率はだいたい 36.8% 程度である. 裏を返せば, 6 割強の確率で, 不幸(?)にして前と同じ座席に座る人が出ることになる.

次回は反転公式を使わない {!n} の求め方を. (続く)