イガブロギュ　♡数学のお話♡

完全順列と包除原理

順列・組合せ・確率 | 17:40

何年か前の早稲田大学かどこかの大学入試問題に、次のようなものがありました。

---

男 5 人、女 5 人が合コンをしました。

男 i は女 i 以外の人だったら誰でもいいと思っています。(i = 1 〜 5)

このとき、全員の欲求を満たす男女のくっつけ方は何通りありますか。

---

原文そのままではないですが、意味は同じです。

さて、問題集に載っていた模範解答を見てみると、しらみ潰しに数えているだけでした。

それでは面白くありません。

実はこの問題の条件を満たす順列は「完全順列」または「撹乱順列」または「モンモール数」と呼ばれていて、その総数を求める公式が存在します。

公式を知っていれば代入してすぐです。

しかし、あろうことか、普通の教科書には載ってないのです。あららー。

「完全順列の総数の公式」

1 〜 n () までの番号が書かれたボールを 1 〜 n までの番号が書かれた箱に入れるとき、いずれも番号が重ならないような順列（完全順列）の総数は

でっす。

どうやったらこんな公式が出来上がるのかしら。

ふっしぎー。

説明します。

---

完全順列の総数を で表します。

最後の n 番目の箱に入れるボールは 1 〜 n-1 の n-1 通りあって、それを i とすると

(i) i = n のとき i 番目の箱にボール n が入っているとき

i と n を入れ替えたのですから、残りの n-2 個の完全順列を考えればよく、 通り。

例えば n = 5 のとき

1, 2, 3, 4, 5 を

5, ○, ○, ○, 1 と並べ替えると

1 と 5 以外の 3 箇所だけで考えれば良い、ということです。

(ii) i = n じゃないとき i 番目の箱にボール n が入っていないとき

例えば n = 5 のとき

1, 2, 3, 4, 5 を並べ替えて

○, ○, ○, ○, 1 となったとします。

○ には 2, 3, 4, 5 が入ります。

ただし、1 番目に 5 がくると (i) と同じことになるので、それはダメです。

ところで、1 番目に入れられないのは 1 も同じことで、今は ○ に入る数は 1 以外なので、ここで 5 を改めて 1 と呼ぶことにしても差し支えありません。

そうすると、1 〜 4 での完全順列を考えれば良いということで、数が減りました。

よって、一般の n の場合は 通り。

(i), (ii) をあわせ、それぞれ i が n-1 パターンあることから、

という漸化式が成り立ちます。

うひゃー。

これは線形の漸化式じゃないので、普通にやったら解けません。

どうしましょ。

次のようにします。

右辺最初の n-1 が邪魔なので、n に 1 を足しましょ。

両辺から を引きます。そうすると上手くいくことを誰かが発見しました。

ここで とおくと

で、, より

なので

()

ゆえに

両辺を n! で割って

より

以上により

---

できました。よかった。

それにしても、何だかとっても技巧的ですネ！

技巧的じゃない考え方なんてあるのかしら？

あります。

というわけで、完全順列の総数の公式を求める方法第二弾、です。

まず、包除原理の復習から。

これは数学Aの「順列・組合せ」の単元でお馴染みの公式で、和集合の要素の個数は、それぞれの集合の要素の個数を足して、余分に数えちゃった共通部分の要素の個数を引けば求められるよ！っていう式です。

ベン図をかけば明らかですね。

こいつを一般化します。

面倒なので n(A) の代わりに |A| と書くことにすると、集合が 3 つの場合、

が成り立ちます。

実際、

です。

集合が 4 つの場合は、

　　

　　　　

　　　　　　

　　

　　　　

　　　　　　

となります。

集合がいくつになっても同様にできることは明らかですね。

さて。

ここで、完全順列の話に戻ります。

以下、証明。

---

i 番目の箱に i 番のボールが入っている順列からなる集合を とおくことにすると、求める完全順列の総数は

…(*)

となるので、包除原理が使えますね。よかったねっ。

ここで、

などとなっており、

n 個の集合から k 個を選ぶ組合せは 通り。

よって

　

　　

　　　

　　　　

したがって (*) とあわせて

ここで、k = 1 のとき なので

---

できましたっ！

ここまで読んでくださった皆さん、ありがとうございました。

他にも公式の導き方は色々あるかもしれません。

自分なりに考えてみると面白いかもしれませんねっ。