はい、今回は、、完全順列というものについて、なるべくわかりやすく！解説することが目的です。
完全順列って？(･ิω･ิ)
数学的に説明すると、「完全順列とは、1〜nの数字を1列に並べた順列のうち、どのk番目の数もkでないもの」
であります。たとえば、左から順番に1,2,3 とならんだ順列があるとします。
この順列に対する完全順列は、
2,3,1
3,1,2
の2つです。
完全順列でないものは
1,2,3 （1番目に1、2番目に2、3番目に3が入っている）
1,3,2（1番目に1が入っている）
2,1,3（3番目に3が入っている）
3,2,1 （2番目に2が入っている）
では次です。
n個の数の順列 1,2,3,······,nの完全順列の個数を W(n)とします。
例えるならば、、
n人の子供がいて、プレゼント交換をするとします🎁。n人全員が、自分のプレゼントを受け取らないように交換したいとき、何通りあるか！？
これが W(n) にあたります( ･ิω･ิ)
まず、結論から↓
W(1)=0
W(2)=1
W(n)=(n-1){W(n-1)+W(n-2)} (n≧3)
となります。
それでは、ここから詳しく解説していきます！
W(1)=0
一人でプレゼント交換はできないので、0通り。
W(2)=1
Aさん（🎁aを持っている）、Bさん（🎁bを持っている）の2人でプレゼント交換をすると、1通り。
A B
✖
a b
ここまでは、すぐにわかりますね(๑•̀ㅁ•́๑)✧
では、
W(3) を考えてみます。
式に当てはめてみると、
W(3)=(3-1){W(3-1)+W(3-2)}=2(1+0)=2
となり、2通りとなります。
確認してみましょう！
確かに！やってみると、この2つしかありませんでした。
では！次に、、
W(4) を考えてみます。
式に当てはめてみると、
W(4)=(4-1){W(4-1)+W(4-2)}=3(2+1)=9
となり、9通りとなります。
確認してみます！
わ、わかりにくい、、(＠_＠;)一人増えただけで、、
でも確かに！9通りになりました！！
というわけで！！
ここから、式の解説も兼ねて、もう少し詳しく見ていこうと思います( ･ิω･ิ)
まず、下の写真を見てください。
Aさんが、bをもらったとき、cをもらったとき、dをもらったとき、と場合分けをします。
この時点で
3通りありますね(๑•̀ㅁ•́๑)
じつは、この3というのが、
W(4)=(4-1){W(4-1)+W(4-2)}=3(2+1)=9
この式の水色部分なんです。
そして、
この部分に着目しましょう！
Aさんはいなくなり、Bさんのプレゼントがありませんが、それをいったん無視すると、3人のプレゼント交換と同じ形です！そう、この形がまずつくれます。↓
この時点で、2通りであり、じつはこれが
W(4)=(4-1){W(4-1)+W(4-2)}=3(2+1)=9
水色部分です！
そして、これが肝心なところなのですが、、
いったん無視しちゃったところ、、
Aさんはいなくなり、Bさんのプレゼントがない、という事実( ･ิω･ิ)
↑このつなぎ方が出来るのです。すると、、
2人でプレゼント交換をしていることになるわけです。これが、
W(4)=(4-1){W(4-1)+W(4-2)}=3(2+1)=9
水色部分になります。
つまりこの式の
{W(4-1)+W(4-2)} の部分は、3人でプレゼント交換をした場合と、さらに、2人でプレゼント交換をした場合を合計したものであり、
それに、Aのもらい方が、3通りあるので、3をかけるわけです！！
この式をつかえば、何人の場合でも求めることができます。では試しにもう一つだけ。
5人の場合は、
W(5)=(5-1){W(5-1)+W(5-2)}=4(9+2)=44
です。
Aさんがもらえるのはb,c,d,eの4通り。
こんな感じですね(^o^)で、一部に着目↓
これは、4人のプレゼント交換の形です。
さらに、
3人のプレゼント交換の形が出現！！(๑´ڡ`๑)
と、こんな感じで、どこまでも続きます、、、