プレゼント交換の数学！完全順列（攪乱順列）の計算公式と不思議な確率

佐藤先生とミライくんの完全順列トーク 💬

佐藤先生

ミライくん、こんにちは。今日も楽しく数学の勉強を始めようか。

ミライくん

こんにちは、佐藤先生。よろしくお願いします。あの、今日はちょっと気になるパズルというか、問題を見つけて気になっているんです。

佐藤先生

お、どんな問題だい。

ミライくん

学校でクラス替えがあったときに、みんなでプレゼントを持ち寄って交換会をすることになったんです。自分の持ってきたプレゼントが自分に当たっちゃうとつまらないから、全員が他の人のプレゼントを受け取るようにしたいね、っていう話になって。これって全部で何通りの配り方があるんだろうって思ったんです。

佐藤先生

それは素晴らしい問題だね。日常の身近な出来事の中に、実は数学のとても美しいテーマが隠れているんだよ。全員が自分のもの以外のプレゼントを受け取るような並べ方のことを、数学では完全順列、または攪乱順列と呼ぶんだ。

ミライくん

カンゼンジュンレツ。なんだか強そうな名前ですね。難しそうです。

佐藤先生

名前は難しそうに見えるけれど、中身はとてもシンプルだよ。要するに、誰も自分の本来の場所に戻らないように、みんなが他人の席に座るようなものだね。これを考えるために、まずは少ない人数から順番に実験してみようか。数学で行き詰まったら、まずは具体的な小さい数字で試すのが鉄則だからね。

ミライくん

小さい数字からですね。じゃあ、１人のときから考えてみます。

佐藤先生

そうだね。もしクラスにミライくん１人しかいなくて、プレゼント交換をしようとしたらどうなるかな。

ミライくん

ええと、僕が持ってきたプレゼントは１個だけで、それを自分で受け取るしかないので、全員が他人のプレゼントを受け取るっていうのは無理ですよね。

佐藤先生

その通り。だから１人のときは、条件を満たす配り方はゼロ通りだ。じゃあ、人数を２人に増やしてみよう。ミライくんと、友達のＡくんの２人でプレゼント交換をするとしたらどうだい。

ミライくん

僕のプレゼントを僕が「自分」、Ａくんのプレゼントを「Ａ」としますね。僕が「Ａ」を受け取って、Ａくんが「自分」を受け取れば、２人とも他人のプレゼントになります。これって、この１通りしかないですよね。

佐藤先生

大正解。２人のときは、お互いのプレゼントをそのまま交換するしか方法がないから、１通りだね。ここまでは簡単だ。では、３人に増やしてみよう。ミライくん、Ａくん、Ｂくんの３人だ。それぞれのプレゼントを、自分の名前と同じ文字で表すことにしよう。ミライくんは自分の、ＡくんはＡの、ＢくんはＢのプレゼントを持っている。これを誰も自分のものを受け取らないように配るには、どうすればいいかな。

ミライくん

３人になると、ちょっとこんがらがってきそうです。ええと、樹形図を書いてみてもいいですか。

佐藤先生

もちろん。樹形図は、抜けやダブりなく数え上げるための最強の道具だよ。書いてごらん。

ミライくん

まず、ミライくんが誰のプレゼントを受け取るかで分けてみます。ミライくんは自分のプレゼントは受け取れないから、Ａくんのプレゼントか、Ｂくんのプレゼントのどちらかですよね。

佐藤先生

そうだね。まずはミライくんがＡくんのプレゼントを受け取った場合から考えてみよう。

ミライくん

ミライくんがＡを受け取ったとします。残っているプレゼントは、自分のものと、Ｂくんのものです。次にＡくんがどちらを受け取るかですが、もしＡくんが自分のプレゼントを受け取っちゃうとダメですよね。でも、Ａのプレゼントはもう僕が持っているから、残っているのは「ミライくんのプレゼント」と「Ｂ」です。もしＡくんがＢを受けると、残ったＢくんは僕のプレゼントを受け取ることになります。これなら、ミライくんがＡ、ＡくんがＢ、Ｂくんがミライ、となって、全員が他人のものになりますね。

佐藤先生

よく気づいたね。他にはないかな。

ミライくん

もし、ミライくんがＡを受け取った後、Ａくんが僕のプレゼントを受け取ったらどうでしょう。残っているのはＢのプレゼントですが、そうなると最後に残ったＢくんが自分のＢを受け取ることになっちゃいます。これはルール違反ですね。だから、ミライくんがＡを受け取ったときは、この１通りだけです。

佐藤先生

その通り。じゃあ、ミライくんがＢくんのプレゼントを受け取った場合はどうなるだろう。

ミライくん

同じように考えてみます。ミライくんがＢを受け取ったとき、残っているのは僕のプレゼントと、Ａのプレゼントです。Ａくんは自分のＡを受け取れないから、僕のプレゼントを受け取るしかありません。そうすると、最後のＢくんはＡのプレゼントを受け取ることになります。ミライくんがＢ、Ａくんがミライ、ＢくんがＡ、という組み合わせです。これも全員が他人のものになっています。

佐藤先生

素晴らしい。ということは、３人のときは全部で何通りになったかな。

ミライくん

ミライくんがＡを受け取ったときが１通りで、Ｂを受け取ったときが１通りだから、合わせて２通りですね。

佐藤先生

正解だ。１人のときは０通り、２人のときは１通り、３人のときは２通り、と綺麗に増えてきたね。じゃあ、この調子で４人のときを考えてみよう。ここからが完全順列の本当の面白さと深さが見えてくるところだよ。４人になると、ミライくん、Ａくん、Ｂくん、Ｃくんになるね。

ミライくん

４人かあ。樹形図を書くのが少し大変になりそうだけど、頑張ってみます。まず、ミライくんが誰のプレゼントを受け取るかですね。僕が自分のを受け取るのはナシだから、Ａくん、Ｂくん、Ｃくんの３つのパターンに分かれます。

佐藤先生

ここで少し立ち止まって考えてみよう。ミライくんがＡくんのを受け取るときと、Ｂくんのを受け取るとき、Ｃくんのを受け取るときで、その後の組み合わせの数に違いはあると思うかい。

ミライくん

ええと、ＡくんもＢくんもＣくんも、僕から見たら同じ「友達の１人」だから、誰のプレゼントを選んでも、その後に起きるパターンの数は同じになりそうな気がします。

佐藤先生

その感覚、とても素晴らしいよ。対称性という言葉を使うんだけど、誰を選んでも状況の複雑さは同じだから、後で３倍すればいいね。じゃあ、まずはミライくんがＡくんのプレゼントを受け取った場合をじっくり数え上げてみよう。

ミライくん

はい。ミライくんがＡを受け取りました。残っているプレゼントは、僕のもの、Ｂ、Ｃの３つです。次にＡくんがどれを受け取るかで枝分かれさせますね。Ａくんが受け取れるのは、僕のものか、Ｂか、Ｃのどれかです。

佐藤先生

そうだね。じゃあ、Ａくんがミライくんのプレゼントを受け取った場合を考えてみよう。

ミライくん

ミライくんがＡ、Ａくんがミライ、を受け取りました。この時点で、ミライくんとＡくんはお互いのプレゼントを交換し合って、２人だけで完結しています。残っているプレゼントはＢとＣで、残っている人はＢくんとＣくんですね。

佐藤先生

おや、これってどこかで見た状況じゃないかい。

ミライくん

あ、残ったＢくんとＣくんの２人で、お互いに自分のものじゃないプレゼントを配るってことだから、さっきやった「２人のときのプレゼント交換」と同じだ。２人のときは１通りしかなかったから、ＢくんがＣを受け取って、ＣくんがＢを受け取るという、この１通りしかありません。

佐藤先生

素晴らしい。過去の計算をそのままパーツとして使えるんだ。じゃあ、ミライくんがＡを受け取った後、Ａくんが僕のもの以外、例えばＢくんのプレゼントを受け取った場合はどうなるかな。

ミライくん

ミライくんがＡ、ＡくんがＢ、を受け取りました。残っているプレゼントは、僕のものと、Ｃの２つです。残っている人はＢくんとＣくんですね。ええと、Ｂくんは僕のものか整Ｃを受け取れますが、もしＢくんが僕のものを受け取ったら、Ｃくんが自分のＣを受け取ることになってダメです。だから、ＢくんがＣを受け取って、Ｃくんが僕のものを受け取るしかありません。これで１通りですね。

佐藤先生

よくできた。じゃあ、ＡくんがＣくんのプレゼントを受け取った場合はどうだい。

ミライくん

ミライくんがＡ、ＡくんがＣ、を受け取りました。残っているプレゼントは、僕のものと、Ｂの２つです。残っている人はＢくんとＣくん。Ｂくんは自分のＢを受け取れないから、僕のものを受け取るしかありません。そうすると、ＣくんがＢを受け取ることになります。これも１通りですね。

佐藤先生

ということは、ミライくんがＡくんのプレゼントを受け取った場合の合計は何通りになったかな。

ミライくん

Ａくんが僕のものを受け取ったときが１通り、Ｂを受け取ったときが１通り、Ｃを受け取ったときが１通り故に、全部で３通りです。

佐藤先生

その通り。そしてさっきミライくんが言ってくれたように、ミライくんがＢくんのプレゼントを受け取るときも、Ｃくんのプレゼントを受け取るときも、それぞれ同じように３通りずつあるはずだよね。

ミライくん

ということは、３通りが３パターンあるから、３かける３で、４人のときは全部で９通りになるんですね。

佐藤先生

大正解。４人の完全順列は９通りだ。ミライくん、ここまでの数字を一度並べて整理してみよう。１人のときは０通り。２人のときは１通り。３人のときは２通り。４人のときは９通り。この数字の並びを見て、何かきまりやルールが見えてこないかい。

ミライくん

うーん、０、１、２、９ですか。２から９へ急にジャンプしているし、掛け算や足し算の簡単なルールはなさそうに見えます。

佐藤先生

一見するとバラバラに見えるよね。でも、ここには数学のとても美しいリレーのような関係が隠れているんだ。これを漸化式と呼ぶんだけど、前の数字を使って次の数字を作るルールを一緒に探してみよう。例えば、４人のときの「９」という数字は、その前の「１」と「２」を使って作ることができるんだ。

ミライくん

ええと、１と２を使って９ですか。２に４をかけて１を足す、とかですか。

佐藤先生

惜しいね。実はこういうルールんだ。前の２つの数字である「１」と「２」を足してみてごらん。

ミライくん

1足す2は3です。

佐藤先生

その３に、今の人数より１少ない数、つまり４人だから「３」をかけてみてごらん。

ミライくん

３かける３は９になります。あ、本当だ。

佐藤先生

じゃあ、このルールが３人のときにも成り立つか試してみよう。３人の前の２つの数字は「０」と「１」だね。これを足すとどうなる。

ミライくん

０足す１は１です。

佐藤先生

その１に、３人より１少ない数、つまり「２」をかけると。

ミライくん

１かける２は２になります。あ、３人のときの答えの２通りになりました。すごい、繋がっています。

佐藤先生

ね、不思議だろう。このルールを言葉で説明すると、次のようになるんだ。ある人数の完全順列の数は、その前の人数と、前々回の人数の完全順列の数を足し算して、そこに、今の人数から１を引いた数を掛け算すれば求められる。これが、完全順列の数をドミノ倒しのように次々と計算していくための魔法の公式なんだ。

ミライくん

どうしてそんなルールが成り立つんですか。偶然にしては出来すぎている気がします。

佐藤先生

とてもいい質問だね。なぜこのルールが成り立つのか、さっき４人のときを数え上げたときのミライくんの考え方の中に、すべてのヒントが隠されているんだよ。もう一度、４人のプレゼント交換を振り返ってみよう。ミライくんが最初にＡくんのプレゼントを受け取ったとき、その後のパターンは２つのチームに分かれていたんだ。覚えているかい。

ミライくん

ええと、Ａくんが僕のプレゼントを受け取って、僕とＡくんでペアを作って完結しちゃったパターンと、Ａくんが僕のもの以外のプレゼントを受け取ったパターンですね。

佐藤先生

その通り。まさにそこがポイントなんだ。まず、ミライくんとＡくんがお互いのプレゼントを交換して、２人で綺麗に完結してしまった場合、残されたのはＢくんとＣくんの２人だったよね。これは「４人から２人を除いた、残りの２人での完全順列」を考えているのと同じなんだ。だから、２人のときの完全順列の数である「１通り」がそのまま出てきた。

ミライくん

なるほど。お互いに入れ替わってペアを作っちゃえば、残りのメンバーだけで他人のものを受け取るゲームをすればいいから、前々回の人数、つまり２人少ない状態の完全順列になるわけですね。

佐藤先生

その通り。じゃあ、もう一つのパターン、Ａくんがミライくんのプレゼントを受け取らなかった場合はどうだろう。このとき、残っているプレゼントは僕のものとＣで、残っている人はＢくんとＣくんだったね。ここで、少し頭を柔らかくして考えてみてほしい。「ミライくんのプレゼント」という名前を、一時的に「Ａくんのプレゼント」と書き換えてみたらどうなるかな。

ミライくん

ええと、名前を書き換える。どういうことですか。

佐藤先生

Ａくんはミライくんのプレゼントを受け取ってはいけない、というルールだったよね。これを「Ａくんは、新しく名前を変えたプレゼントを受け取ってはいけない」と考えると、これはミライくんを除いたＡくん、Ｂくん、Ｃくんの３人の中で、誰も自分の名前のプレゼントを受け取ってはいけない、という「３人の完全順列」と全く同じ状況になっているんだよ。

ミライくん

うわあ、ちょっと難しいです。でも、言われてみれば、Ａくんが僕のプレゼントを拒否するっていうルールは、まるでＡくん自身が自分のプレゼントを拒否しているのと同じようなプレッシャーになっているってことですか。

佐藤先生

まさにその通りだよ。とても鋭いね。だから、お互いにペアを作らなかった場合は、自分以外の１人を除いた「１人少ない人数での完全順列」の数、つまり３人のときの数である「２通り」と同じになるんだ。

ミライくん

だから、ペアを作って完結したときの「前々回の数」と、ペアを作らずに巻き込んだときの「前回の数」を足し算すればいいんですね。

佐藤先生

そういうこと。そして、今回はミライくんが最初に選ぶ相手として、Ａくん、Ｂくん、Ｃくんの３人がいたよね。これは、自分以外の全員だから、人数が４人なら「４マイナス１」で３人いることになる。

ミライくん

だから、足し算した結果に、自分以外の人数である「３」を掛け算するんだ。全部のパーツが綺麗に繋がりました。

佐藤先生

これで、どうしてあの公式が成り立つのかが心から納得できただろう。数式を丸暗記するのではなく、こうして意味を考えると、数学は一気に楽しくなるんだ。このルールを使えば、５人のときも樹形図を書かずに一瞬で計算できるよ。ミライくん、５人のときの完全順列が何通りになるか、計算してみてくれるかい。

ミライくん

はい、やってみます。５人のときの前の数字は、３人のときの「２」と、４人のときの「９」ですよね。まず、この２つの数字を足します。２足す９は１１です。次に、今の人数は５人だから、自分以外の人数は５マイナス１で「４」です。だから、さっきの１１に４を掛け算すればいいんですね。１１かける４は４４。つまり、５人のときは４４通りですか。

佐藤先生

大正解。５人になると樹形図を書くのは絶対に無理なくらい大変だけど、このリレーのルールを使えば、あっという間に４４通りだと分かるんだ。どうだい、完全順列の仕組みが見えてきたかな。

ミライくん

はい。すごくスッキリしました。一見バラバラに見える数字の後ろに、こんなに綺麗なリレーのルールがあるなんて感動です。

佐藤先生

喜んでもらえて嬉しいよ。さて、この完全順列には、もう一つとても面白い特徴があるんだ。もし人数をもっとたくさん、例えば１０人とか２０人、あるいはクラス全員の４０人とかに増やしていったとき、全員が他人のプレゼントを受け取る確率って、どれくらいになると思うかい。

ミライくん

人数が増えれば増えるほど、自分のプレゼントが当たっちゃう確率が高くなりそうだから、全員が他人のものを受け取れる確率はどんどん小さくなって、最後はゼロに近づいていく気がします。

佐藤先生

普通の感覚だとそう思うよね。人数が増えるんだから、誰か１人くらい自分のものを引き当てちゃいそうだと感じる。でもね、ここに数学の信じられないような不思議な現象があるんだ。実は、人数をどれだけ増やしていっても、全員が他人のプレゼントを受け取る確率は、ある一定の割合からほとんど変わらなくなるんだよ。

ミライくん

ええっ、そんなことあるんですか。人数が増えても確率が減らないんですか。

佐藤先生

そうなんだ。具体的に言うと、だいたい３６．８パーセントという確率にどんどん近づいていって、そこから動かなくなるんだ。４人だろうが、１０人だろうが、１００人だろうが、全員が完全に他人のプレゼントを受け取れる確率は、いつでも約３割から４割くらいに落ち着くんだよ。

ミライくん

３６．８パーセント。なんだか不思議な数字ですね。どうしてそんな中途半端な数字で止まるんですか。

佐藤先生

これは高校生や大学生になってから習う「自然対数の底」という、数学の世界でとても重要な「ｅ」という特別な定数が関係しているんだ。パーセントで言うと不思議な数字に見えるけれど、分数で表すと、大体３分の１より少し大きいくらいの確率にずっと固定されるんだよ。人数が増えると、全体の並び方の数も爆発的に増えるけれど、それと同時に条件を満たす完全順列の数も同じようなスピードで爆発的に増えるから、割り算したときの確率は一定に保たれるんだね。

ミライくん

数学って、一見すると予想もつかないようなところで、不思議な数字が守られているんですね。プレゼント交換の幹事をするときに、この話を知っていると、どれくらいの確率でやり直しになっちゃうかが予想できて便利そうです。

佐藤先生

まさにその通り。約６割の確率で誰かが自分のプレゼントを引き当ててしまうから、一発で成功させるのは少しラッキーが必要だということだね。学校の席替えや、テストのプリントをクラスメイト同士で採点するために回すときなんかにも、この完全順列の考え方がそのまま使えるよ。

ミライくん

身の回りにたくさん完全順列が隠れているんですね。今日教えてもらったことを、忘れないように頭の中でしっかり整理しておきます。

佐藤先生

素晴らしい姿勢だね。では、今日学んだ内容を、いつでも誰にでも説明できるように、最も大切なポイントを綺麗にまとめておこう。これを見ていつでも思い出せるようにしてね。

完全順列の決定的な結論

完全順列とは、すべての要素が本来あるべき位置とは異なる位置に配置されるような並べ方のことです。身近な例では、全員が自分の持ってきたもの以外のプレゼントを受け取るようなプレゼント交換の配り方がこれに該当します。この完全順列の仕組みと計算方法には、以下の３つの明確な原則とルールがあります。

１．少人数の場合の具体的な数

人数が少ない場合の完全順列の数は、樹形図などを丁寧に書くことで以下のように数え上げることができます。この最初の数を知っておくことが、すべての計算の土台になります。

• １人のとき：自分のものを受け取るしかないので、条件を満たす配り方は０通り。
• ２人のとき：お互いのものを入れ替えるしかないので、１通り。
• ３人のとき：循環するように配るしかなく、２通り。
• ４人のとき：樹形図で丁寧に数え上げると、９通り。

２．次の人数を導き出すリレーの公式

人数が多くなったとき、毎回樹形図を書くのは不可能です。完全順列の数には、前の２つの結果を使って次の結果を導き出すことができる美しいリレーのルールが存在します。

• 求めたい人数の完全順列の数は、１人少ないときの数と、２人少ないときの数を足し算します。
• その足し算した結果に、自由以外の人数、つまり今の人数から１を引いた数を掛け算します。
• 例えば、５人のときの数を求めたい場合は、３人のときの数である２と、４人のときの数である９を足して１１とし、そこに５から１を引いた４を掛け算することで、４４通りと簡単に計算できます。

３．人数が増えても変わらない驚異の確率

普通の感覚では、人数が増えれば増えるほど、全員が他人のプレゼントを受け取れる確率は低くなっていくように感じられます。しかし、数学的には非常に不思議な性質があり、全体の人数をどれだけ大きくしていっても、全員が他人のものを受け取れる確率は約３６．８パーセントという一定の値に限りなく近づいていきます。

どれほど大人数でプレゼント交換や席替えを行っても、およそ３回に１回以上の確率で全員が綺麗に他人の位置に収まるという事実は、完全順列が持つ最も魅力的で不思議な特徴の一つです。