2014/03/13

攪乱順列の公式

分野: 場合の数  レベル: 最難関大学

$1, 2,\cdots, n$ を並び替えてできる順列のうち,全ての $i=1, 2, \cdots, n$ に対して $i$ 番目が $i$ でないものの個数 $a_n$ は,以下の式で表される:
$a_n=n!\displaystyle\sum_{k=2}^n\dfrac{(-1)^k}{k!}$

攪乱順列とは

攪乱順列(かくらんじゅんれつ)とは,その名の通り数字の並びを完全にかくらんする(もとと同じ場所になる要素がない)順列のことを表します。完全順列とも言いますが,攪乱順列の方が意味として分かりやすいと思います。(漢字は難しいですが、)

攪乱順列の数 $a_n$ はモンモール数とも呼ばれます。
モンモール数を求める問題はモンモールの問題とも呼ばれ,$n=3, 4$ くらいの場合には入試問題でも多く出題されており,まれに一般の $n$ に対する問題も出題されます。

攪乱順列の具体例

・ $n=2$ のときは攪乱順列は$(2,1)$ の1通り
公式からも,$a_2=2!\left(\dfrac{1}{2}\right)=1$ と分かります。

・ $n=3$ のときは$(2, 3, 1), (3, 1, 2)$ の2通り
公式からも,$a_3=3!\left(\dfrac{1}{2}-\dfrac{1}{6}\right)=2$ と分かります。

・ $n=4$ の場合を求めよ(東工大)
→気合で数えて9通り。
公式からも,$a_4=4!\left(\dfrac{1}{2}-\dfrac{1}{6}+\dfrac{1}{24}\right)=9$ と分かります。

・ $n$ が十分大きいとき(有名問題)
公式から,$\dfrac{a_n}{n!}=\displaystyle\sum_{k=2}^n\dfrac{(-1)^k}{k!}=\sum_{k=0}^n\dfrac{(-1)^k}{k!}=e^{-1}=0.367\cdots$
つまり,適当に選んだ順列が攪乱順列になっている確率は約37%
(ただし,式変形の途中で指数関数のマクローリン展開を用いました。)

・くじ引きで席替えしたのに席が変わらない残念な人がいる確率は大体63%
($n$ を増やしたら100%に近づきそうな気がしますが,いくら大人数でやっても63%くらいというのは意外な結果です。

・大人数でプレゼント交換をするときに自分のプレゼントに当たる悲しい人がいる確率は大体63%

漸化式を用いた公式の導出

一般の $n$ に対して攪乱順列の数を求めたいのですが,気合で全部書き並べるわけにはいかないので,漸化式を用います。
1の移動先を $i$ として,攪乱順列を以下の2通りに場合分けします。

パターン1:$i$ の移動先が1となる場合の数
$i$ の選び方が $n-1$ 通りで,それぞれに対して1と $i$ 以外の $n-2$ 個の攪乱順列の数だけあるので,全部で$(n-1)a_{n-2}$ 通り。

パターン2:$i$ の移動先が1以外となる場合の数
$i$ の選び方が $n-1$ 通りで,それぞれに対して1以外の $n-1$ 個の攪乱順列の数だけあるので,全部で$(n-1)a_{n-1}$ 通り。

よって,$a_n=(n-1)(a_{n-1}+a_{n-2})$
あとは,$a_2=1, a_3=2$ のもとでこの三項間漸化式を解けばよいだけですが,解き方の詳細は割愛します。
→階乗を用いる漸化式の解法の例題3)

頑張って解くと,$a_n=n!\displaystyle\sum_{k=2}^n\dfrac{(-1)^{k}}{k!}$ が分かります。

包除原理を用いた公式の導出

方針:直接求めるのは難しいので余事象を考えます。「撹乱されない」=「1が移動しない」または「2が移動しない」または $\cdots$ 「nが移動しない」
「または」がいっぱい出てきて扱いにくいので包除原理を用いて「かつ」に変換します。

証明

$i$ が移動しない順列の集合を $A_i$ とおくと,
$a_n=n!-|A_1\cup A_2\cup\cdots\cup A_n|$

$i$ が移動しない順列の数は,$|A_i|=(n-1)!$
$i$ も $j$ も移動されない順列の数は,$|A_i\cap A_j|=(n-2)!$
以下同様にして,特定の $k$ 個の要素が移動されない順列の数は,$(n-k)!$ となる。すなわち「かつ」の確率は計算できるので,包除原理より,
$a_n=n!-|A_1\cup A_2\cup\cdots\cup A_n|\\
=n!-\displaystyle\sum_{k=1}^n(-1)^{k-1}{}_nC_k(n-k)!\\
=n!-n!\displaystyle\sum_{k=1}^n\dfrac{(-1)^{k-1}}{k!}\\
=n!\displaystyle\sum_{k=2}^n\dfrac{(-1)^k}{k!}$

攪乱順列,モンモールって響きが特徴的だからなんとなく印象に残ります。

Tag: とにかく美しい数学公式まとめ
Tag: マクローリン展開の応用例まとめ

分野: 場合の数  レベル: 最難関大学