他己紹介の場合の数 - 数学の命題示しました

他己紹介とは， $n$ 人の参加者が一人づつ自分以外の誰かを紹介し，結果的に $n$ 人全員が自分以外の誰かから紹介されるようにすることです．

太郎，次郎，三郎，四郎の４人が参加者とすると，例えば
太郎は三郎を紹介．
次郎は太郎を紹介．
三郎は四郎を紹介．
四郎は次郎を紹介．
すると，これは一つの他己紹介になります．

参加者が $n$ 人いるとき，何通りの他己紹介が可能か気になりますよね？
調べましょう．

上の太郎の例からすぐ分かるように， $n$ 人の他己紹介は不動点を持たない $n$ 文字の置換にほかなりません．
この数え上げ問題は撹乱の問題と呼ばれ，WikipediaによるとMontmortや Nicholas Bernoulliにより１８世紀初頭に研究されたそうです．

場合の数に関する漸化式を立てて代数的に解く方法もあるようですが，ここでは次の包除原理と呼ばれる定理を用います．

定理（包除原理, [1]）
集合 $X$ を $X\triangleq\{1,\ldots,n\}$ とする．二つの写像 $f,g\colon 2^X\to \mathbb{C}$ に関する以下の二つの主張は同等である．

すべての $S\subseteq X$ に対し $g(S)=\sum_{T\subseteq S}f(T)$ .
すべての $S\subseteq X$ に対し $f(S)=\sum_{T\subseteq S}(-1)^{|S\setminus T|}g(T)$ .

命題([1])
自然数 $n$ に対し， $n$ 人で他己紹介を行う場合の数は
$\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}k!$ 通りである．
証明
集合 $X$ を $X\triangleq\{1,\ldots,n\}$ とする．
写像 $f\colon 2^X\to \mathbb{C}$ を， $S\subseteq X$ に対し
$f(S)\triangleq(S$ 上では不動点を持たず， $X\setminus S$ の点は不動点であるような $X$ の置換の数 $)$
と定義する．
このとき $S\subseteq X$ に対し $\sum_{T\subseteq S}f(T)$ は全ての $S$ の置換の数を表すので
$|S|!=\sum_{T\subseteq S}f(T)$ である．
包除原理より $S\subseteq X$ に対し
$f(S)=\sum_{T\subseteq S}(-1)^{|S\setminus T|}|T|!$ ．

今求めたいのは $S=X$ の場合なので代入すると，不動点を持たない $X$ の置換の数は
$f(X)=\sum_{T\subseteq X}(-1)^{|X\setminus T|}|T|!=\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}k!$ である．
（終）

得られた量はさらに次のように評価できることが知られています．

命題([2])
自然数 $n$ に対し， $n$ 人で他己紹介を行う場合の数は
$n!/e$ に一番近い整数である．但し $e$ はネイピア数 $=2.71828\ldots$ ．
証明
前の命題の記号をそのまま用いる．
$|n!/e - f(X)|=|n!\sum_{k=0}^\infty (-1)^{k}/k! - \sum_{k=0}^n\binom{n}{k}(-1)^{n-k}k!|$ .
$\binom{n}{k}=n!/k!(n-k)!$ を代入して計算すると
$|n!/e - f(X)|=\frac{1}{n+1}|1-\frac{1}{n+2}+\frac{1}{(n+2)(n+3)}-\frac{1}{(n+2)(n+3)(n+4)}+\cdots$ ad. inf. $|$ .
ここから
$\frac{1}{n+2}\leq |n!/e - f(X)| \leq \frac{1}{n+1}$ を得る．
値 $f(X)$ は整数なことから，所望の結果が言える．
（終）

これにより例えば，７人で他己紹介をする場合の数は1854通りです．

参考文献
[1] Richard P. Stanley. (2011) "Enumerative Combinatorics," Volume 1, second edition. v. 15. p. 227.
[2] Ronald L. Graham, Donald E. Knuth, Oren Patashnik. (1994) "Concrete Mathematics," second edition. p.195.