| 完全順列 整数 1, 2, 3, …, n を並べかえた時に、i番目が i でない順列 |
単純にn個の数を並べかえると全部で n!通り（＝nPn）になりますが、今回の場合、例えば「1, …」や、「●, 2, …」のようなケースを除かないといけません。
もう少しイメージしやすくすると、「プレゼント交換で、自分のプレゼントをもらう人がいない配り方」とか「席替えをして、全員の席が変わるパターン」は何通りあるか、というような問題です。
以下の例は、３人の間でプレゼントを配ることを考えてみたものです。Aさんが「①」、Bさんが「②」、Cさんが「③」を持ってきたとして、誰も自分のプレゼントを受取らないようにします。
| 配り方 | Aさん | Bさん | Cさん | |
| （１） | ① | ② | ③ | ダメ |
| （２） | ① | ③ | ② | ダメ |
| （３） | ② | ① | ③ | ダメ |
| （４） | ② | ③ | ① | OK |
| （５） | ③ | ① | ② | OK |
| （６） | ③ | ② | ① | ダメ |
すると、今回は（４）と（５）の配り方であればOKということで、答えは２通りということになります。
数え方については、樹形図での書き出しを基本にしてもらったら結構ですが、
５人の時は数が多くなりますので、Aさんが ② である場合を数え上げて、③ のとき、④ のとき、⑤ のときは同様で、「×４」で求めてください。
ただ、６人以上の場合は数え上げ自体も難しくなってきますので、以下に記載の方法で計算を進めてください。
求め方
n個の数字を並べかえるときの【完全順列】を an通りとして、これを求めていきましょう。
※※※「なぜこう考えるのか」というよりは、「こういう解き方が発見されている」という捉え方をしてもらった方がいいと思います。※※※
さて、結果から先に言うと、
・２人で交換：１通り（２人で交換するだけ）
・３人で交換：２通り
・４人で交換：９通り
・５人で交換：44通り
というような感じになっていきますが、実は、例えば５人の時の「44」は、３人の時の「２」と４人の時の「９」から求めることができるのです。
考え方としては、以下の（１）と（２）のように場合分けして、合計してください。他の場合分けもできそうな感じがしますが、実際にスッと計算するためにはこのような形にしてください。
なお、この（１）と（２）は、同時に起こらず、かつ、これ以外のケースは生まれないような場合分けにちゃんとなっています。
（１）Aさんが他の誰かと直接２人で交換しているとき
例えば、AさんはBさんから、BさんはAさんからもらう、というようなケースです。
| Aさん | Bさん | Cさん | … | nさん |
| ② | ① | 残りの人でプレゼント交換 | ||
このとき、「A・B」の間では「自分のプレゼントはもらわない」という条件を満たしています。
あとは、残りの「ｎ－２人」の間で「自分のプレゼントはもらわない」ようにすればいいのですが、これって結局２人少ない場合の【完全順列】そのものになっています。
そして、相手がBさん以外の場合でも同じことが言えます。
| Aさん | Bさん | Cさん | … | nさん |
| ③ | ① | |||
ですので、（１）の場合については、
「『Aさんと交換相手』以外のプレゼント交換：an－2 通り」×「Aさんと直接交換する相手：n－1 人」ということで、(n－1)・an－2 通りということになります。
（２）Aさんがもらった人とは別の人に渡しているとき
次に、（１）以外のケース、つまり、Aさんと別の人が直接交換していないケースについてです。
例えば、AさんはBさんからもらっているとき、AさんはBさん以外の人に渡さないといけません（Bさんに渡す場合は（１）で考慮済み）
| Aさん | Bさん | Cさん | … | nさん |
| ② | ①以外 | |||
このとき、「AさんはBさん以外の人と交換しないといけません」という部分について、
「『①、③ ～』があって、Bさんは①をもらってはダメ、Cさんは③をもらってはダメ、Dさんは④をもらってはダメ、…」が何通りあるのか、というのは、
「『②、③ ～』があって、Bさんは②をもらってはダメ、Cさんは③をもらってはダメ、Dさんは④をもらってはダメ、…」が何通りあるのか、ということに置き換えることができます。
これはちょうど「ｎ－１人」の間で「自分のプレゼントはもらわない」ことに相当しますが、結局、１人少ない場合の【完全順列】そのものになっています。
そして、Aさんがプレゼントをもらえる相手は、Bさんに限らず、全部で「ｎ－１人」いて、しかも全ての場合で同じことが言えます。
よって、（２）の場合については、
「Aさん以外のプレゼントのもらい方：an－1 通り」×「Aさんがもらう相手：n－1 人」ということで、(n－1)・an－1 通りということになります。
というわけで、（１）（２）から、最終的に
an＝(n－1)・（an－1＋an－2）
という関係を導くことができます。
ここから先は数列の漸化式を用いた計算が必要ですが、結果的には、
\[ a_{n}=n! \sum_{k=2}^n \frac{ \big( – 1\big) ^{k} }{k!} \]
というものになりますが、最後のここまでは大学入試でも要求されないと思います。
（出題されたこともありますが、捨て問扱いで大丈夫です）
補足
場合分けの（１）で、Aさんだけに狙いを定めて考える理由は、（こうすれば上手く漸化式をたてられるという事情もありますが、）もし単純に「誰か２人が直接交換する場合」とすると、ものすごく重複が出てきてしまうためです。例えば、「A・B」で交換する場合には、例えば「E・M」が交換する場合も含まれますし、逆に「E・M」で交換する場合には、「A・B」が交換する場合も含まれます。
ですので、直接交換する２人を選ぶための nC2 のような計算をしても、特に意味がないのです。
