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

前回証明なしで使った反転公式
$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}$ の求め方を. (続く)