こんにちは、ウチダです。
いつもお読みいただきましてありがとうございます。
さて、皆さんは「完全順列」という言葉を耳にしたことはあるでしょうか。
仮に言葉だけは聞いたことがあったとしても…
数学太郎
数学花子こういった悩みを持つ方は非常に多いかと思います。
よって本記事では、「そもそも完全順列とは何か」から、完全順列の総数(モンモール数)の公式、また完全順列に成り立つ美しい性質まで
- 東北大学理学部数学科卒
- 教員採用試験に１発合格 → 高校教諭経験アリ
- （専門は確率論でした。）
の僕がわかりやすく解説します。
完全順列(攪乱順列)とは【公式より一発で求まります】
これから解説していく「完全順列(攪乱順列)」についてのポイントを $3$ つ、最初にまとめておきます。
- 完全順列の総数の一般項 $a_n$ は、$$a_n=(n-1)(a_{n-1}+a_{n-2})$$と表すことができる。
- $1$ より、$$a_n=n!\sum_{k=2}^{n}\frac{(-1)^k}{k!}$$と求めることができる。
- 無造作に $n$ 枚のカードを一列に並べたとき、それが完全順列になる確率は、$n$ を大きくしていくと$$\frac{1}{e}=0.367879…$$に近づく。
$1$ 番が絶対に押さえてほしいポイントで、$2$ 番が知っていると便利な公式です。
そして、$3$ 番が冒頭にお話した美しい性質、いわゆるコラム的な内容になります。
ウチダさて、これらを理解するために、まず「完全順列とはいったい何者なのか」ここから始めていきましょう。
完全順列とは、一言で言うと「 $i$ 番目が $i$ でない順列」のことです。
たとえばこんな感じ。
「 $1,2,3,4$ 」という配置から数字を動かすと考えたとき、動かない数字が存在しないことから”完全”順列と名前が付けられています。
また、全部の数字がかき乱されていることから、別名「攪乱(かくらん)順列」とも呼ばれます。
ではまず、例で挙げてみた $n=4$ の完全順列の総数を求めていきましょうか。
完全順列(攪乱順列)の総数を求めよう
完全順列の総数のことを「モンモール数」と呼ぶこともあります。
これは別に覚えておかなくても大丈夫です。(笑)
さて、完全順列(攪乱順列)の問題を上手に解くコツ。
それは…
- ⅰ）…$1$ と $k$ の場所が入れ替わる場合
- ⅱ）…$1$ の移動先が $k$ で、$k$ の移動先が $1$ 以外の場合
以上 $2$ パターンに場合分けして考えることです。
ウチダさっそく解答を見ていきましょう♪
【解答】
$k=2$ として考えると、
- ⅰ）…$n=2$ の完全順列の総数（つまり $a_2$ ）
- ⅱ）…$n=3$ の完全順列の総数（つまり $a_3$ ）
を求めて足せばよいことがわかる。
よって、$a_2=1$ 、$a_3=2$ なので、$1+2=3$ 通りであることがわかる。
<補足>$a_2$、$a_3$ は数え上げればすぐに求まります。
したがって、$k=3$、$k=4$ の場合も同様に考えられるので、$n=4$ の完全順列の総数は $3×3=9$ 通りである。
(解答終了)
一見すると、「数え上げた方が速いんじゃない…？」と思うぐらい複雑な解法ですよね。
しかし、解答の前にもお伝えした通り、このやり方は一般化が非常に容易なんです！！
この問題は $n=4$ でしたが、今の議論って $n$ がどんな値でも成り立ちませんか？
よって、たとえば $1,2,3,4,5,6$ の完全順列の総数であれば、$k=2$ ～ $6$ の $5$ パターンに対して、
- ⅰ）…$n=4$ の完全順列の総数（つまり $a_4$ ）
- ⅱ）…$n=5$ の完全順列の総数（つまり $a_5$ ）
となるので、$$a_6=5(a_4+a_5)$$が成り立つことがわかります。
以上の話を一般化すると…
$$a_n=(n-1)(a_{n-1}+a_{n-2})$$
となり、冒頭で紹介したポイント $1$ 番が導けました。
ウチダさて、この漸化式さえ知っておけば、どんな完全順列の総数でも求めることができます。
たとえば $n=7$ のときであれば…
$$a_7=6(a_6+a_5)$$
ですから、$a_6$、$a_5$ についても同様に
$$a_6=5(a_5+a_4)$$
$$a_5=4(a_4+a_3)$$
であり、また $a_5$、$a_4$ についても同様に…
って、めんどくさい～～～～！！
ということで、求めることは理論上可能ですが、かなり面倒くさいため、次はもう少し簡単な公式を作っていきましょう。
完全順列(攪乱順列)の総数の公式を漸化式から導く
現時点で、ポイント $1$ は示せました。
よってここからは、ポイント $2$ の公式を導いていきます。
ウチダ【漸化式から公式を導く】
先ほど、完全順列の総数(モンモール数)における漸化式
$$a_n=(n-1)(a_{n-1}+a_{n-2})$$
を導いた。
移項して、この式を整理すると、
※以降、途切れている長い数式は横にスクロールできます。(スマホでご覧の方対象。)
ここで、①の式の意味を考えると、「 $n$ → $n-1$ のように $1$ 減らすとき、式全体に $(-1)$ 倍する必要がある」となる。
したがって、①の式より、$1$ 減らす操作を繰り返すと
この式の両辺を $n!$ で割ると、$$\frac{a_n}{n!}-\frac{a_{n-1}}{(n-1)!}=\frac{(-1)^n}{n!} ……②$$
②の式より、$k=2$ ～ $n$ までの和を取ってみると、
したがって、$a_1=0$ より、$$a_n=n!\sum_{k=2}^{n}\frac{(-1)^k}{k!}$$
となり、公式が導けた。
(導出終了)
この公式さえ覚えておけば、たとえば $n=4$ を代入してみると
と、確かに $a_4=9$ 通りであると求めることができました。
さっきは面倒くさくて諦めた $a_5$ や $a_6$、$a_7$ であっても、
と、場合の数が多くなっても簡単に求めることができます。
ここまでくると数え上げでは対処できないため、公式の必要性がわかるかと思います。
ウチダ完全順列(攪乱順列)の美しい性質について
さて、最後にポイント $3$ を解説していきます。
無造作に $n$ 枚のカードを一列に並べたとき、それが完全順列になる確率は、$n$ を大きくしていくと$$\frac{1}{e}=0.367879…$$に限りなく近づく。
$e$ という数は「ネイピア数」と呼ばれていて、数学Ⅲで初登場します。
とりあえず、“数学的にものすごい重要な数”とだけ認識しておけばOKです。
その数の逆数に近づくのですから、数学的に美しいですよね～。
さて、このポイント $3$ を理解するには、$e^x$ のマクローリン展開が
$$e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+…$$
であることから、この式に $x=-1$ を代入し、
となることを利用しなくてはいけません。
ウチダ以上を利用すれば、
がすぐに従います。
※$n$ 枚のカードを一列に並べる場合の数は $n!$ で求まります。
美しい性質を感じられる具体例【プレゼント交換と席替え】
完全順列というのは、実は結構なじみ深いものなんですよね。
- 仲間内の誕生日会で、プレゼント交換をした。このとき、自分のプレゼントが当たる人がいない確率は？
- $30$ 人のクラスで席替えをした。このとき、席が変わらない人がいない確率は？
プレゼント交換や席替えって、「動かない人(もの)が存在しない場合の数」を考えているので、ようは完全順列のお話ですよね。
さて、「さきほど $n$ を十分大きくとれば $\frac{1}{e}≒0.37$ に限りなく近づく」とお伝えしましたが、実はこの収束の速度はとても速いです。
なので、$n=10$ ぐらいでほぼ $\frac{1}{e}≒37$ % に収束し終わってしまうんですよ。
よって、プレゼント交換や席替えで、全く変わらないという残念な人がいない確率ってのは、大体 $37$ % になります。
逆に言えば、
- 少なくとも $1$ 人以上、自分のプレゼントが戻ってくる確率
- 少なくとも $1$ 人以上、席が変わらない確率
これらは $63$ % という、結構高確率で起こることがわかります。
ウチダ完全順列(攪乱順列)に関するまとめ
本記事のポイント $3$ つは押さえられたでしょうか？
- 完全順列の総数の一般項 $a_n$ は、$$a_n=(n-1)(a_{n-1}+a_{n-2})$$と表すことができる。
- $1$ より、$$a_n=n!\sum_{k=2}^{n}\frac{(-1)^k}{k!}$$と求めることができる。
- 無造作に $n$ 枚のカードを一列に並べたとき、それが完全順列になる確率は、$n$ を大きくしていくと$$\frac{1}{e}=0.367879…$$に限りなく近づく。
「すべてを理解するのは少し難しかった…」という方は、とりあえず知っておくだけでもいいので、ぜひ自らの教養として知識を蓄えていただきたく思います。
「場合の数」全 12 記事をまとめました。こちらから次の記事をCHECK!!
終わりです～。
コメントを残す