1. 高校数学の美しい物語
  2. 攪乱順列(完全順列)の個数を求める公式

攪乱順列(完全順列)の個数を求める公式

更新日時 2021/03/07
攪乱順列(完全順列)の個数

11 から nn までの整数を並び替えてできる順列のうち,すべての ii について「ii 番目が ii でない」を満たすものの個数 ana_n

an=n!k=2n(1)kk!a_n=n!\displaystyle\sum_{k=2}^n\dfrac{(-1)^k}{k!}

攪乱順列(完全順列)の意味と具体例を紹介したあと,上記の公式を2通りの方法で証明します。

目次
  • 攪乱順列(完全順列)とは

  • 攪乱順列の具体例

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

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

攪乱順列(完全順列)とは

攪乱順列(かくらんじゅんれつ)とは,その名の通り数字の並びを完全にかくらんする(もとと同じ場所になる要素がない)順列のことを表します。

n=3n=3 の場合を考えてみる (1,2,3)(1,2,3) を「かくらんする」順列を考える。1番目が1でなく,2番目が2でなく,3番目が3でないのは (2,3,1)(2,3,1)(3,1,2)(3,1,2) の2つ。つまり a3=2a_3=2

  • 攪乱順列のことを完全順列とも言います。攪乱順列の方が漢字は難しいですが,意味は分かりやすいと思います。
  • nn 個の場合の攪乱順列の数 ana_nモンモール数とも呼ばれます。
  • モンモール数を求める問題はモンモールの問題とも呼ばれます。

攪乱順列の具体例

n=2の場合

n=2n=2 のときは攪乱順列は (2,1)(2,1) の1通りです。

また,公式 an=n!k=2n(1)kk!a_n=n!\displaystyle\sum_{k=2}^n\dfrac{(-1)^k}{k!}n=2n=2 とすることでも a2=2!(12)=1a_2=2!\left(\dfrac{1}{2}\right)=1 と分かります。

n=3n=3 の場合は,さきほど確認したように (2,3,1),(3,1,2)(2, 3, 1), (3, 1, 2) の2通りです。n=3,4n=3, 4 くらいは入試問題でも多く出題されており,まれに一般の nn に対する問題も出題されます。

n=4の場合(東工大)

頑張って数えると以下の9通りです。

(2,1,4,3),(2,3,4,1),(2,4,1,3),(2,1,4,3),(2,3,4,1),(2,4,1,3), (3,1,4,2),(3,4,1,2),(3,4,2,1),(3,1,4,2),(3,4,1,2),(3,4,2,1), (4,1,2,3),(4,3,1,2),(4,3,2,1)(4,1,2,3),(4,3,1,2),(4,3,2,1)

公式を知っていれば,a4=4!(1216+124)=9a_4=4!\left(\dfrac{1}{2}-\dfrac{1}{6}+\dfrac{1}{24}\right)=9 と分かります。

nが十分大きいとき(有名問題)

公式から,

ann!=k=2n(1)kk!=k=0n(1)kk!e1=0.367\dfrac{a_n}{n!}=\displaystyle\sum_{k=2}^n\dfrac{(-1)^k}{k!} =\sum_{k=0}^n\dfrac{(-1)^k}{k!}\fallingdotseq e^{-1}=0.367\cdots

つまり,適当に選んだ順列が攪乱順列になっている確率は約37%です(式変形の途中で指数関数のマクローリン展開を用いました)。

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

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

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

方針

一般の nn に対して攪乱順列の数を求めたいのですが,気合で全部書き並べるわけにはいかないので,漸化式を用います。

証明

1の移動先を「ii 番目」 として,攪乱順列を以下の2通りに場合分けする。

  • パターン1:ii の移動先が1番目となる場合の数(交換型)

ii の選び方が n1n-1 通りで,それぞれに対して1と ii 以外の n2n-2 個の攪乱順列の数だけあるので,全部で (n1)an2(n-1)a_{n-2} 通り。

  • パターン2:ii の移動先が1番目以外となる場合の数(非交換型)

ii の選び方が n1n-1 通りで,それぞれに対して1以外の n1n-1 個の攪乱順列の数だけあるので,全部で (n1)an1(n-1)a_{n-1} 通り。

よって,an=(n1)(an1+an2)a_n=(n-1)(a_{n-1}+a_{n-2})

あとは,a2=1,a3=2a_2=1, a_3=2 のもとでこの三項間漸化式を解けばよいだけです。解き方の詳細→階乗を用いる漸化式の解法の例題3より,

an=n!k=2n(1)kk!a_n=n!\displaystyle\sum_{k=2}^n\dfrac{(-1)^{k}}{k!} が分かります。

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

方針

直接求めるのは難しいので余事象を考えます。「撹乱されない」=「1が移動しない」または「2が移動しない」または \cdots 「nが移動しない」

「または」がいっぱい出てきて扱いにくいので包除原理を用いて「かつ」に変換します。

証明

ii が移動しない順列の集合を AiA_i とおくと,

an=n!A1A2Ana_n=n!-|A_1\cup A_2\cup\cdots\cup A_n|

ii が移動しない順列の数は,Ai=(n1)!|A_i|=(n-1)!

iijj も移動されない順列の数は,AiAj=(n2)!|A_i\cap A_j|=(n-2)!

以下同様にして,特定の kk 個の要素が移動されない順列の数は,(nk)!(n-k)! となる。すなわち「かつ」の確率は計算できるので,包除原理より,

an=n!A1A2An=n!k=1n(1)k1nCk(nk)!=n!n!k=1n(1)k1k!=n!k=2n(1)kk!a_n=n!-|A_1\cup A_2\cup\cdots\cup A_n|\\ =n!-\displaystyle\sum_{k=1}^n(-1)^{k-1}{}_n\mathrm{C}_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:マクローリン展開の応用例まとめ

人気記事
  1. 高校数学の美しい物語
  2. 攪乱順列(完全順列)の個数を求める公式