 | aのカードがbの箱に入っていることをを[a]→[b]と表します。
例、2のカードが5の箱に入り5のカードは7の箱に入っていて7のカードは8に入る･･･
[2]→[5]→[7]→[8]→･･･
case1.[k]→[n+2]→[k]･･･のとき
kにあたるカードの選び方がn+1通りあり、k,n+2以外のカードが条件を
満たすように入れる入れ方はAn通り。よって(n+1)An通り。
case2.[k]→[n+2]→[m]→･･･(k≠m)のとき
n+2のカードを除くn+1枚のカードの入れ方はAn+1通りあり、n+2のカードを
どこに入れるかはn+1通りある。なぜかというと、
[1]→[4]→････[6]→[1] [2]→[n-2]→･･･[10] ･････
n+2のカードをどこの矢印のところに入れるかは、n+1通りありますよね。
よって(n+1)An+1通り
以上より、An+2=(n+1)An+(n+1)An+1=(n+1)(An+An+1)
ごめんなさい、、、わかりにくいですね。
これは有名問題で、｢モンモール｣または｢撹乱順列｣と呼ばれているので、
検索などもしてみてくださいね。
|
