完全順列の漸化式・一般項・極限

上野竜生です。今回は完全順列の漸化式・一般項・極限を扱います。漸化式の導出も，ひらめきにくいアイデアが必要となり，答えを読んで理解するのも大変です。基本はn=5ぐらいまでで導出できればいいですが，一般の漸化式までは入試で問われてもおかしくないので難関大受験生は見ておきましょう。

問題

正確に言うとこれの解を表すのはΣを使った式を使わないと難しいです。漸化式を作ってそれを解きます。全部でa_n通りあるとします。

ステップ１：　n=1,2,3,4ぐらいまでは書き出して求める（本当はn=2までで十分）

テストでは一般のnの漸化式を答えさせる難関大学もありますが，普通はn=5ぐらいまでについて具体的な数値を求めさせる問題も多いです。n=4までは書き出してみます。

n=1のとき，どう頑張っても自分のプレゼントは自分に来てしまう。0通り。
n=2のとき，そもそもの並べ方が「１２」or「２１」しかない。前者は自分のプレゼントが自分に来てしまっているので後者のみが条件を満たす。1通り。
n=3のとき，「２３１」「３１２」の2通り。
n=4のとき，「２１４３」「２３４１」「２４１３」「３１４２」「３４１２」「３４２１」「４１２３」「４３１２」「４３２１」の9通り。
【参考】n=5は樹形図を書いてください。44通りになります。「２」から始まるものだけ書きました。11通りです。「３」「４」「５」も11通りで合計44通りとなります。

ステップ２：　漸化式を求める（ここの考えが難しいです）

1番左の値をkとします。（2≦k≦n）
左からk番目の値が1かどうかで場合分けします。

左からk番目の値が1のとき
1とkが入れ替わっている。残りのn-2個の決め方はa_n-2通り。
kの決め方がn-1通りあるので(n-1)a_n-2通り。

左からk番目の値が1ではないとき
たとえばk=2とすると「2番目からn番目」と残った数字「1,3,4,・・・ｎ」には次の制約がある。
・2番目は1ではない。
・3番目は3ではない。
・・・
・n番目はnではない。
ここで1を②と思うと「2番目からn番目」と残った数字「②,3,4,・・・,n」には次の制約がある。
・2番目は②ではない
・3番目は3ではない
・・・
・n番目はnではない。
つまりこれはn-1個の完全順列の個数なのでa_n-1通り。
k=2以外でもk=3,4,5,・・・,nでも同様。
kの決め方がn-1通りあるので(n-1)a_n-1通り。

以上よりa_n=(n-1)(a_n-1 +a_n-2)

添え字をずらして見やすくすると
a_n+2= (n+1)(a_n+1 +a_n)

ステップ３　漸化式を解いて一般項を求める。

a_n+2=(n+1)a_n+1+(n+1)a_n
両辺から(n+2)a_n+1を引くと
a_n+2 - (n+2)a_n+1 =-{ a_n+1 -(n+1)a_n }
よってb_n=a_n+1-(n+1)a_nとおくとb₁=a₂-2a₁=1 - 2・0=1
b_n+1=-b_nよりb_n=(-1)ⁿ⁺¹
よってa_n+1-(n+1)a_n=(-1)ⁿ⁺¹
両辺を(n+1)!で割ると
\[\displaystyle \frac{a_{n+1}}{(n+1)!}=\frac{a_n}{n!}+\frac{(-1)^{n+1}}{(n+1)!} \]
ここで\(\displaystyle c_n= \frac{a_n}{n!} \)とおくとc₁=0
\[\displaystyle c_{n+1}=c_n+\frac{(-1)^{n+1}}{(n+1)!} \]
階差数列の形だからn≧2では
\[\displaystyle c_n=c_1+\sum_{k=1}^{n-1} \frac{(-1)^{k+1}}{(k+1)!}=\sum_{k=2}^n \frac{(-1)^k}{k!} \]
よって\(\displaystyle a_n=n! \sum_{k=2}^n \frac{(-1)^k}{k!} \)
n=1のときはa₁=0

ちなみにΣの中はk=2からnまで足していますがk=0のときとk=1のときを足すと0になるのでΣはk=0からの式にしてもOK!この場合n=1の場合分けは不要です。よってn=1も含めて
\[\displaystyle a_n=n! \sum_{k=0}^n \frac{(-1)^k}{k!} \]
と書けます。

ステップ４　極限　(大学の内容を含んでいます)

a_nの極限は∞になります。確率p_nの極限を求めてみましょう。
１からｎまでの並べ方はn!通りあるので完全順列になる確率をp_nとすると
\[\displaystyle p_n=\frac{a_n}{n!}=\sum_{k=0}^n \frac{(-1)^k}{k!} \]

e^xのマクローリン展開
\[\displaystyle e^x=\frac{x^0}{0!}+\frac{x^1}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots \]
にx=-1を代入すれば
\[\displaystyle \lim_{n\to \infty} p_n=e^{-1}=\frac{1}{e} \]
となります。