完全順列(攪乱順列)とは？【漸化式から導く一般項の美しい性質】

2019年10月23日2022年2月21日

こんにちは、ウチダです。

いつもお読みいただきましてありがとうございます。

さて、皆さんは「完全順列」という言葉を耳にしたことはあるでしょうか。

仮に言葉だけは聞いたことがあったとしても…

[ふきだし set=”悩む男性”]完全順列っていう名前がわかりづらい！結局どういう意味なの？[/ふきだし]

[ふきだし set=”悩む女性”]完全順列には、公式があると聞きました。自分で色々調べてみましたが…さっぱりわかりません！タスケテクダサイ、、[/ふきだし]

こういった悩みを持つ方は非常に多いかと思います。

よって本記事では、「そもそも完全順列とは何か」から、完全順列の総数(モンモール数)の公式、また完全順列に成り立つ美しい性質まで

東北大学理学部数学科卒
教員採用試験に１発合格　→　高校教諭経験アリ
（専門は確率論でした。）

の僕がわかりやすく解説します。

完全順列(攪乱順列)とは【公式より一発で求まります】

これから解説していく「完全順列(攪乱順列)」についてのポイントを $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$ 番が冒頭にお話した美しい性質、いわゆるコラム的な内容になります。

[ふきだし set=”ウチダ”]今は「なんのこっちゃ………」という感じかもしれませんが、ここからちゃんと紐解いていきますので、ご安心ください。[/ふきだし]

さて、これらを理解するために、まず「完全順列とはいったい何者なのか」ここから始めていきましょう。

完全順列とは、一言で言うと「 $i$ 番目が $i$ でない順列」のことです。

たとえばこんな感じ。

「 $1,2,3,4$ 」という配置から数字を動かすと考えたとき、動かない数字が存在しないことから”完全”順列と名前が付けられています。

また、全部の数字がかき乱されていることから、別名「攪乱(かくらん)順列」とも呼ばれます。

ではまず、例で挙げてみた $n=4$ の完全順列の総数を求めていきましょうか。

完全順列(攪乱順列)の総数を求めよう

問題.　$1$、$2$、$3$、$4$ を並び替えたとき、どの数字も元の位置にいない場合の数を求めよ。

完全順列の総数のことを「モンモール数」と呼ぶこともあります。

これは別に覚えておかなくても大丈夫です。(笑)

さて、完全順列(攪乱順列)の問題を上手に解くコツ。

それは…

ⅰ）…$1$ と $k$ の場所が入れ替わる場合
ⅱ）…$1$ の移動先が $k$ で、$k$ の移動先が $1$ 以外の場合

以上 $2$ パターンに場合分けして考えることです。

[ふきだし set=”ウチダ”]これは、知る人ぞ知るテクニック的な側面が強いです。もちろん $n=4$ ぐらいであれば「数え上げ」も有効な手段です。ただ…この解法が最適な理由は「一般化が容易」な点にあります。[/ふきだし]

さっそく解答を見ていきましょう♪

【解答】

$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$ 番が導けました。

[ふきだし set=”ウチダ”]$n$ のときの値が、$n-1$ や $n-2$ のときの値によって決まる式のことを「漸化式(ぜんかしき)」と言い、詳しくは数学Ｂ「数列」にて学びます。さっきからちょくちょく出てきている「一般項(いっぱんこう)」も、数列の用語になります。[/ふきだし]

さて、この漸化式さえ知っておけば、どんな完全順列の総数でも求めることができます。

たとえば $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$ の公式を導いていきます。

[ふきだし set=”ウチダ”]ここからは数学Ｂ「数列」の話になります。結果を覚えるだけでもいいので、まだ習ってないよーという方は雰囲気だけでも掴んでいただきたく思います。[/ふきだし]

【漸化式から公式を導く】

先ほど、完全順列の総数(モンモール数)における漸化式

$$a_n=(n-1)(a_{n-1}+a_{n-2})$$

を導いた。

移項して、この式を整理すると、

\begin{align}a_n-n(a_{n-1})=(-1)\{a_{n-1}-(n-1)a_{n-2}\}　……①\end{align}

※以降、途切れている長い数式は横にスクロールできます。(スマホでご覧の方対象。)

ここで、①の式の意味を考えると、「 $n$ → $n-1$ のように $1$ 減らすとき、式全体に $(-1)$ 倍する必要がある」となる。

したがって、①の式より、$1$ 減らす操作を繰り返すと

\begin{align}a_n-n(a_{n-1})&=(-1)\{a_{n-1}-(n-1)a_{n-2}\}\\&=(-1)^2\{a_{n-2}-(n-2)a_{n-3}\}\\&=(-1)^3\{a_{n-3}-(n-3)a_{n-4}\}\\&=…\\&=(-1)^{n-2}(a_2-2a_1)=(-1)^n(1-2×0)=(-1)^n\end{align}

この式の両辺を $n!$ で割ると、$$\frac{a_n}{n!}-\frac{a_{n-1}}{(n-1)!}=\frac{(-1)^n}{n!}　……②$$

②の式より、$k=2$ ～ $n$ までの和を取ってみると、

\begin{align}\sum_{k=2}^{n}\frac{(-1)^k}{k!}&=\sum_{k=2}^{n}(\frac{a_k}{k!}-\frac{a_{k-1}}{(k-1)!})\\&=\frac{a_2}{2!}-\frac{a_1}{1!}+\frac{a_3}{3!}-\frac{a_2}{2!}+…+\frac{a_n}{n!}-\frac{a_{n-1}}{(n-1)!}\\&=\frac{a_n}{n!}-\frac{a_1}{1!}\end{align}

したがって、$a_1=0$ より、$$a_n=n!\sum_{k=2}^{n}\frac{(-1)^k}{k!}$$

となり、公式が導けた。

(導出終了)

この公式さえ覚えておけば、たとえば $n=4$ を代入してみると

\begin{align}a_4&=4!\sum_{k=2}^{4}\frac{(-1)^k}{k!}\\&=4!(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!})\\&=12-4+1\\&=9\end{align}

と、確かに $a_4=9$ 通りであると求めることができました。

さっきは面倒くさくて諦めた $a_5$ や $a_6$、$a_7$ であっても、

\begin{align}a_5&=5!\sum_{k=2}^{5}\frac{(-1)^k}{k!}\\&=5!(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!})\\&=60-20+5-1\\&=44\end{align}

\begin{align}a_6&=6!\sum_{k=2}^{6}\frac{(-1)^k}{k!}\\&=6!(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!})\\&=360-120+30-6+1\\&=265\end{align}

\begin{align}a_7&=7!\sum_{k=2}^{7}\frac{(-1)^k}{k!}\\&=7!(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}-\frac{1}{7!})\\&=2520-840+210-42+7-1\\&=1854\end{align}

と、場合の数が多くなっても簡単に求めることができます。

ここまでくると数え上げでは対処できないため、公式の必要性がわかるかと思います。

[ふきだし set=”ウチダ”]この公式の導出方法は「隣接三項間の漸化式」における王道パターンです。隣接三項間の漸化式は発展内容ですが、難関大の入試では平気な顔して出てくるので、しっかりと学習しておきましょう。[/ふきだし]

完全順列(攪乱順列)の美しい性質について

さて、最後にポイント $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$ を代入し、

\begin{align}\frac{1}{e}&=\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-…\\&=\lim_{n \to \infty}\sum_{k=2}^{n}\frac{(-1)^k}{k!}\end{align}

となることを利用しなくてはいけません。

[ふきだし set=”ウチダ”]マクローリン展開は大学１年生で学ぶため、ここではスルー。気になる方はググってみて下さい。[/ふきだし]

以上を利用すれば、

\begin{align}\lim_{n \to \infty}\frac{a_n}{n!}&=\lim_{n \to \infty}\sum_{k=2}^{n}\frac{(-1)^k}{k!}\\&=\frac{1}{e}\end{align}

がすぐに従います。
※$n$ 枚のカードを一列に並べる場合の数は $n!$ で求まります。

美しい性質を感じられる具体例【プレゼント交換と席替え】

完全順列というのは、実は結構なじみ深いものなんですよね。

仲間内の誕生日会で、プレゼント交換をした。このとき、自分のプレゼントが当たる人がいない確率は？
$30$ 人のクラスで席替えをした。このとき、席が変わらない人がいない確率は？

プレゼント交換や席替えって、「動かない人(もの)が存在しない場合の数」を考えているので、ようは完全順列のお話ですよね。

さて、「さきほど $n$ を十分大きくとれば $\frac{1}{e}≒0.37$ に限りなく近づく」とお伝えしましたが、実はこの収束の速度はとても速いです。

なので、$n=10$ ぐらいでほぼ $\frac{1}{e}≒37$ % に収束し終わってしまうんですよ。

よって、プレゼント交換や席替えで、全く変わらないという残念な人がいない確率ってのは、大体 $37$ % になります。

逆に言えば、

少なくとも $1$ 人以上、自分のプレゼントが戻ってくる確率
少なくとも $1$ 人以上、席が変わらない確率

これらは $63$ % という、結構高確率で起こることがわかります。

[ふきだし set=”ウチダ”]なので、もし今後プレゼント交換の機会があり、自分のプレゼントが帰ってきてしまった場合は、「いや、この確率は $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!!