問題はこちら（画像をクリックするとPDFファイルで開きます。）
完全順列、攪乱順列、モンモール数などと呼ばれる話題の問題で、1994年度慶応大、2004年度東工大など類題も多く見られます。
本問のように \(5\) 人といったような具体的な場合であれば、樹形図をかき、腕力で押し切ることも可能でしょう。
（ただ、工夫しないとそれなりの大木になるでしょう。）
ただ、ここでは一般的な \(n\) のときでも話が通じる態度である漸化式を立てる方針で考えてみます。
完全順列に対する漸化式の立て方は独特なものがあります。
（以下ネタバレ注意）
+ クリック（タップ）して続きを読む \(1\) 番から \(n\) 番までの番号がついた球と箱が１つずつあるとします。 これらの球を左から並べて箱に一つずつ入れていくことを考えます。 このとき、箱の番号と球の番号が一致しないような並べ方を完全順列と言います。 もう少し順列っぽい言い方をすると \(1\) から \(n\) の数字を \(1\) 列に並べた順列のうち、\(k=1 \ , \ 2 \ , \cdots \ , \ n\) に対して どの \(k\) 番目の数も \(k\) ではないもの という言い方になるでしょうか。 本問もアルファベットよりも数字の方が記述がしやすいので、人に \(1\) , \(2\) , \(\cdots\) とゼッケンをつけ、プレゼントを入れる箱にも \(1\) , \(2\) , \(\cdots\) と番号をつけておきます。 \( \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\) という入れ方を考えるわけです。 このような箱への入れ方を \(a_{n}\) 通りとします。 完全順列における漸化式の立て方は独特です。 今回のプレゼント交換を例に表現すると ポイント
\(1\) 番の人と、\(k\) 番の人のプレゼント交換が成立するか否か という観点で場合分けをします。 \(k\) の選び方は \(n+1\) 通りです。 このとき、残りの \(n\) 人に関するプレゼント交換の仕方は \(a_{n}\) 通りあります。 \(k\) の選び方は先ほど同様 \(n+1\) 通りです。 このとき \( \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\) \( \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\) と、\(n+1\) 個のプレゼントに対して \(n+1\) 個の「 NG 箱」があるということで \(a_{n+1}\) 通りの入れ方 となります。 \(\displaystyle \frac{a_{n}}{n!}\) は \(n\) 人でプレゼント交換をしたときに、自分の持ってきたプレゼントに当たってしまう「可哀そうな人」が一人もいない確率です。 \(\displaystyle \lim_{n \to \infty}\displaystyle \frac{a_{n}}{n!}\) を計算すると \(\displaystyle \lim_{n \to \infty}\displaystyle \frac{a_{n}}{n!}=\displaystyle \frac{1}{e}\) と約 \(36.7\) ％ほどです。 \(n\) が十分大きければ、可哀そうな人が一人ぐらいいそうなものなので、極限が \(0\) とならないのは不思議です。 このあたりの計算については【総括】後の【補足】で触れてあります。完全順列とは
\(a_{n+2}\) について
\(1\) 番の人と、\(k\) 番の人のプレゼント交換が成立するとき
\(1\) 番の人と、\(k\) 番の人のプレゼント交換が成立しないとき
\(n\) が十分大きいとき