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

問題

n人でプレゼントを交換する。誰も自分のプレゼントが当たらないようにする方法は何通りあるか?
言い換えると
1からnまでの数字を並べ替える時,すべてのiについて「左からi番目の数字≠i」になる並べ方は何通りあるか?

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

広告

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

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

n=1のとき,どう頑張っても自分のプレゼントは自分に来てしまう。0通り。
n=2のとき,そもそもの並べ方が「12」or「21」しかない。前者は自分のプレゼントが自分に来てしまっているので後者のみが条件を満たす。1通り。
n=3のとき,「231」「312」の2通り。
n=4のとき,「2143」「2341」「2413」「3142」「3412」「3421」「4123」「4312」「4321」の9通り。
【参考】n=5は樹形図を書いてください。44通りになります。「2」から始まるものだけ書きました。11通りです。「3」「4」「5」も11通りで合計44通りとなります。
完全順列

ステップ2: 漸化式を求める(ここの考えが難しいです)

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

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

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

数字で対応させると分かりにくいなら言葉で対応させるとわかりやすいと思います。
たとえば5人の人「一郎,二郎,三郎,四郎,五郎」君がそれぞれプレゼント「A,B,C,D,E」を持ってたとします。
一郎君がBを受け取ったとして,二郎君がAではないプレゼントをもらったとき
Bは一郎君がとってるので二郎君にBが来ることはありません。
残りの部分は「二郎,三郎,四郎,五郎」とプレゼント「A,C,D,E」の対応です。
条件は
仮定条件から二郎≠Aと
三郎≠C , 四郎≠D, 五郎≠Eになります。これは4人でプレゼント交換して自分のプレゼントが来ない場合の数と全く同じであることがわかりますね。

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

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

広告

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

an+2=(n+1)an+1+(n+1)an
両辺から(n+2)an+1を引く
an+2 – (n+2)an+1 =-{ an+1 -(n+1)an }
よってbn=an+1-(n+1)anとおくとb1=a2-2a1=1 – 2・0=1
bn+1=-bnよりbn=(-1)n+1
よってan+1-(n+1)an=(-1)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!} \)とおくとc1=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のときはa1=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!} \]
と書けます。

 

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

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

exのマクローリン展開
\[\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} \]
となります。

【参考】
全部でn問の空所補充問題があり,選択肢はn択であるとする。
(ア)同じ選択肢は繰り返し使えない場合
(イ)同じ選択肢を何回でも使ってよい場合
のそれぞれでランダムに解答したとき,1問も正解しない確率のn→∞の極限は
上の結果より(ア)では\(\displaystyle \frac{1}{e} \)
(イ)は\(\displaystyle \lim_{n\to \infty} (1-\frac{1}{n})^n=\frac{1}{e} \)
なので実は同じになります。

 

解説を読んで数学がわかった「つもり」になりましたか?数学は読んでいるうちはわかったつもりになりますが演習をこなさないと実力になりません。そのためには問題集で問題を解く練習も必要です。オススメの参考書を厳選しました

<高校数学> <大学数学> さらにオススメの塾、特にオンラインの塾についてまとめてみました。自分一人だけでは自信のない人はこちらも参考にすると成績が上がります。