完全順列と包除原理 - イガブロギュ

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

男 5 人、女 5 人が合コンをしました。
男 i は女 i 以外の人だったら誰でもいいと思っています。(i = 1 〜 5)
このとき、全員の欲求を満たす男女のくっつけ方は何通りありますか。

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

さて、問題集に載っていた模範解答を見てみると、しらみ潰しに数えているだけでした。
それでは面白くありません。

実はこの問題の条件を満たす順列は「完全順列」または「撹乱順列」または「モンモール数」と呼ばれていて、その総数を求める公式が存在します。
公式を知っていれば代入してすぐです。
しかし、あろうことか、普通の教科書には載ってないのです。あららー。

「完全順列の総数の公式」
1 〜 n ( $n \geq 2$ ) までの番号が書かれたボールを 1 〜 n までの番号が書かれた箱に入れるとき、いずれも番号が重ならないような順列（完全順列）の総数は
$n! \sum_{k=2}^n \frac{(-1)^k}{k!}$
でっす。

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

説明します。

完全順列の総数を $a_n$ で表します。
最後の n 番目の箱に入れるボールは 1 〜 n-1 の n-1 通りあって、それを i とすると

(i) ~~i = n のとき~~ i 番目の箱にボール n が入っているとき
i と n を入れ替えたのですから、残りの n-2 個の完全順列を考えればよく、 $a_{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 の場合は $a_{n-1}$ 通り。

(i), (ii) をあわせ、それぞれ i が n-1 パターンあることから、
$a_n = (n-1)(a_{n-1} + a_{n-2})$
という漸化式が成り立ちます。

うひゃー。

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

右辺最初の n-1 が邪魔なので、n に 1 を足しましょ。
$a_{n+1} = n(a_n + a_{n-1})$
両辺から $(n+1)a_n$ を引きます。そうすると上手くいくことを誰かが発見しました。
$a_{n+1} - (n+1)a_n = -(a_n - na_{n-1})$
ここで $b_n = a_n - na_{n-1}$ とおくと
$b_{n+1} = -b_n$ で、 $a_1 = 0$ , $a_2 = 1$ より
$b_2 = a_2 - 2 a_1 = 1$ なので
$b_n = (-1)^n$ ( $n \geq 2$ )
ゆえに
$a_n - na_{n-1} = (-1)^n$
両辺を n! で割って
$\frac{a_n}{n!} - \frac{a_{n-1}}{(n-1)!} = \frac{(-1)^n}{n!}$
$\frac{a_n}{n!} = \frac{a_{n-1}}{(n-1)!} + \frac{(-1)^n}{n!}$
$\frac{a_1}{1!} = 0$ より
$\frac{a_n}{n!} = \sum_{k=2}^n \frac{(-1)^k}{k!}$
以上により
$a_n = n! \sum_{k=2}^n \frac{(-1)^k}{k!}$

できました。よかった。

それにしても、何だかとっても技巧的ですネ！
技巧的じゃない考え方なんてあるのかしら？

あります。

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

まず、包除原理の復習から。
$n(A \cup B) = n(A) + n(B) - n(A \cap B)$
これは数学Aの「順列・組合せ」の単元でお馴染みの公式で、和集合の要素の個数は、それぞれの集合の要素の個数を足して、余分に数えちゃった共通部分の要素の個数を引けば求められるよ！っていう式です。
ベン図をかけば明らかですね。
こいつを一般化します。

面倒なので n(A) の代わりに |A| と書くことにすると、集合が 3 つの場合、
$|A \cup B \cup C| = |A|+|B|+|C|-|A \cap B|-|B \cap C|-|C \cap A|+|A \cap B \cap C|$
が成り立ちます。
実際、
$|A \cup B \cup C|$
$= |(A \cup B) \cup C|$
$= |A \cup B|+|C|-|(A \cup B) \cap C|$
$= |A \cup B|+|C|-|(A \cap C) \cup (B \cap C)|$
$= |A \cup B|+|C|-(|A \cap C|+|B \cap C|-|A \cap B \cap C|)$
$= |A|+|B|+|C|-|A \cap B|-|B \cap C|-|C \cap A|+|A \cap B \cap C|$
です。

集合が 4 つの場合は、
$|A \cup B \cup C \cup D|$
$=|(A \cup B \cup C) \cup D|$
$=|A \cup B \cup C|+|D|-|(A \cup B \cup C) \cap D|$
$=|A \cup B \cup C|+|D|-|(A \cap D) \cup (B \cap D) \cup (C \cap D)|$
$=|A \cup B \cup C|+|D|-($
　　 $|A \cap D|+|B \cap D|+|C \cup D|$
　　　　 $-|A \cap B \cap D|-|B \cap C \cap D|-|A \cap C \cap D|$
　　　　　　 $+|A \cap B \cap C \cap D|)$
$=|A|+|B|+|C|+|D|$
　　 $-|A \cap B|-|A \cap C|-|A \cap D|-|B \cap C|-|B \cap D|-|C \cap D|$
　　　　 $+|A \cap B \cap C|+|A \cap B \cap D|+|A \cap C \cap D|+|B \cap C \cap D|$
　　　　　　 $-|A \cap B \cap C \cap D|$
となります。

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

さて。
ここで、完全順列の話に戻ります。
以下、証明。

i 番目の箱に i 番のボールが入っている順列からなる集合を $A_i$ とおくことにすると、求める完全順列の総数は
$a_n = n! - |A_1 \cup A_2 \cup \cdots \cup A_n|$ …(*)
となるので、包除原理が使えますね。よかったねっ。

ここで、
$|A_i| = (n-1)!$
$|A_i \cap A_j| = (n-2)!$
$|A_i \cap A_j \cap A_k| = (n-3)!$
などとなっており、
n 個の集合から k 個を選ぶ組合せは ${}_n \mathrm{C}_k$ 通り。

よって
$|A_1 \cup A_2 \cup \cdots \cup A_n|$
$= (|A_1| + |A_2| + \cdots + |A_n|)$
　 $- (|A_1 \cap A_2| + |A_1 \cap A_3| + \cdots)$
　　 $+ (|A_1 \cap A_2 \cap A_3| + \cdots)$
　　　 $- \cdots$
　　　　 $(-1)^{n-1} (|A_1 \cap A_2 \cap \cdots \cap A_n|)$
$= \sum_{k=1}^n (-1)^{k-1}(n-k)!{}_n \mathrm{C}_k$
$= \sum_{k=1}^n (-1)^{k-1}\frac{n!}{k!}$
$= n!\sum_{k=1}^n \frac{(-1)^{k-1}}{k!}$

したがって (*) とあわせて
$a_n = n! - n!\sum_{k=1}^n \frac{(-1)^{k-1}}{k!}$
ここで、k = 1 のとき $n! \frac{(-1)^{k-1}}{k!} = n!$ なので
$a_n= n!\sum_{k=2}^n \frac{(-1)^k}{k!}$

できましたっ！

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

他にも公式の導き方は色々あるかもしれません。
自分なりに考えてみると面白いかもしれませんねっ。