攪乱(かくらん)順列（完全順列）
攪乱順列の一般項
$${n}$$$${(n}$$は$${2}$$以上の整数$${)}$$人が各自$${1}$$個のプレゼントを持ち寄って，プレゼント交換をする．ただし，どの人も，自分のプレゼントは受け取らないようにする．このような交換の仕方は全部で何通りか．
以下の例題を参考に求めたいと思う。
$${n}$$を$${2}$$以上の自然数とする．正の整数からなる有限数列$${\left\lbrace a_{1},a_{2},\dots,a_{n}\right\rbrace}$$は次の条件を満たす．
$${\begin{aligned}&\left(a\right)\ a_{k}\neq k\ \left(k=1,2,\dots,n\right)\\&\left(b\right)\ 1\leqq a_{k}\leqq n\ \left(k=1,2,\dots,n\right)\\&\left(c\right)\ 1\leqq k< l\leqq n\ のとき\ a_{k}\neq a_{l}\end{aligned}}$$
このような数列の全体を$${X_{n}}$$で表し，$${X_{n}}$$の要素の個数を$${x_{n}}$$で表す．
$${\left(1\right)}$$$${x_{n+2}}$$を$${x_{n+1},\ x_{n},\ n}$$を用いて表せ．
$${\left(2\right)}$$$${x_{n}}$$を求めよ．
上の条件$${\left(a\right),\ \left(b\right),\ \left(c\right)}$$を満たす正の整数からなる有限数列$${\left\lbrace a_{1},a_{2},\dots,a_{n}\right\rbrace}$$を$${n}$$次の攪乱順列（完全順列）という。また，$${n}$$次の攪乱順列の総数$${x_{n}}$$をモンモール数という。
$${\left(1\right)}$$
$${a_{n+2}}$$の選び方は$${1}$$から$${n+1}$$までの$${n+1}$$通りである．このとき，$${a_{n+2}=i}$$とする．
$${\left(\mathrm{i}\right)}$$$${a_{i}=n+2}$$のとき
$${a_{i}=n+2,\ a_{n+2}=i}$$以外の$${n}$$個の数の並べ方は，$${n}$$次の攪乱順列の総数$${x_{n}}$$に等しい．
$${\left(\mathrm{ii}\right)}$$$${a_{i}\neq n+2}$$のとき
$${a_{n+2}=i}$$以外の$${n+1}$$個の数の並べ方は，$${n+1}$$次の攪乱順列の総数$${x_{n+1}}$$に等しい．
$${\left(\mathrm{i}\right),\ \left(\mathrm{ii}\right)}$$より$${a_{n+2}=i}$$のとき$${\left(a\right),\ \left(b\right),\ \left(c\right)}$$を満たす$${\left\lbrace a_{1},a_{2},\dots,a_{n}\right\rbrace}$$は全部で$${x_{n+1}+x_{n}}$$個ある．よって
$${x_{n+2}=\left(n+1\right)\left(x_{n+1}+x_{n}\right)}$$
が成り立つ．
$${\left(2\right)}$$
まず$${x_{2}}$$を求める．$${n=2}$$のとき，攪乱順列は
$${\left(2,1\right)}$$
の$${1}$$通りである．よって
$${x_{2}=1}$$である．
次に$${x_{3}}$$を求める．$${n=3}$$のとき，攪乱順列は
$${\left(2,3,1\right),\left(3,1,2\right)}$$
の$${2}$$通りである．よって
$${x_{3}=2}$$である．
$${x_{n+2}=\left(n+1\right)\left(x_{n+1}+x_{n}\right)}$$を変形すると
$${x_{n+2}-\left(n+2\right)x_{n+1}=-\left\lbrace x_{n+1}-\left(n+1\right)x_{n}\right\rbrace}$$
とできるから，数列$${\left\lbrace x_{n+1}-\left(n+1\right)x_{n}\right\rbrace}$$は公比が$${-1}$$の等比数列である．よって$${n\geqq2}$$のとき
$${\begin{aligned}x_{n+1}-\left(n+1\right)x_{n}&=\left(x_{3}-3x_{2}\right)\left(-1\right)^{n-2}\\&=\left(-1\right)^{n-1}\end{aligned}}$$
すなわち
$${\begin{aligned}x_{n+1}&=\left(n+1\right)x_{n}+\left(-1\right)^{n-1}\end{aligned}}$$
となるから，両辺を$${\left(n+1\right)!}$$で割って
$${\begin{aligned}\frac{x_{n+1}}{\left(n+1\right)!}=\frac{x_{n}}{n!}+\frac{\left(-1\right)^{n-1}}{\left(n+1\right)!}\end{aligned}}$$
したがって，$${n\geqq3}$$のとき，
$${\begin{aligned}\frac{x_{n}}{n!}&=\frac{x_2}{2!}+\sum_{k=2}^{n-1}\frac{\left(-1\right)^{k-1}}{\left(k+1\right)!}\\&=\frac{1}{2}+\sum_{k=3}^{n}\frac{\left(-1\right)^{k-2}}{k!}=\frac{1}{2}+\sum_{k=3}^{n}\frac{\left(-1\right)^{k}}{k!}\end{aligned}}$$
さらに，$${\dfrac{\left(-1\right)^{0}}{0!}+\dfrac{\left(-1\right)^{1}}{1!}+\dfrac{\left(-1\right)^{2}}{2!}=\dfrac{1}{2}}$$であるから，
$${\begin{aligned}\frac{x_{n}}{n!}&=\frac{1}{2}+\sum_{k=0}^{n}\frac{\left(-1\right)^{k}}{k!}-\frac{1}{2}\\&=\sum_{k=0}^{n}\frac{\left(-1\right)^{k}}{k!}\end{aligned}}$$
となり，$${n=2}$$でも成り立つ．よって，
$${\begin{aligned}x_{n}=n!\sum_{k=0}^{n}\frac{\left(-1\right)^{k}}{k!}\end{aligned}}$$
と表すことができる．また，$${n\geqq2}$$の場合で考えるから
$${\begin{aligned}x_{n}=n!\sum_{k=2}^{n}\frac{\left(-1\right)^{k}}{k!}\end{aligned}}$$
と表すこともできる．
したがって，最初のプレゼント交換の問の答えも
$${\begin{aligned}n!\sum_{k=0}^{n}\frac{\left(-1\right)^{k}}{k!}\ \text{通り}\end{aligned}}$$
ということになる。
攪乱順列の確率
$${n}$$$${(n}$$は$${2}$$以上の整数$${)}$$人が各自$${1}$$個のプレゼントを持ち寄って，プレゼント交換をする．このとき，どの人も，自分のプレゼントは受け取らないような交換をする確率を求めよ．
という問題については，以下のように考えることができる．
プレゼントの交換の仕方は全部で$${n!}$$通りで，これらは同様に確からしい．
したがって，どの人も，自分のプレゼントは受け取らないような交換をする確率は
$${\begin{aligned}\frac{x_{n}}{n!}=\sum_{k=0}^{n}\frac{\left(-1\right)^{k}}{k!}\end{aligned}}$$
である．
ちなみに，指数関数のマクローリン展開
$${\begin{aligned}e^{x}=\sum_{k=0}^{\infty}\frac{x^{k}}{k!}\end{aligned}}$$
より
$${\begin{aligned}\lim_{n \to \infty}\frac{x_{n}}{n!}=e^{-1}=\frac{1}{e}\end{aligned}}$$
であることがわかる。これは
$${\begin{aligned}&36.78794411714423215955237\\&7016146086744581113103176\\&7834507836801697461495744\\&8998033571472743459196437\cdots\%\\&(100\ 桁目まで表記)\end{aligned}}$$
であることが分かっている。
以上で説明を終わる。