質問

このような問題がテストで出てきたのですが、どうしてこのような答え
になるか分かりません、どうか教えて下さい

1,2,3,..........nの順列のＡ１、Ａ２、..............Ａｎのうち
Ａｉ＜=ｉ+１（ｉ=１，２，３，４...........ｎ）
を満たすものの個数を求めよ

答え２のｎ-１乗

お返事２００２／１／２０
from=武田

未解決問題に移したところ、３名の方（ｄ３さん、CharlieBrownさん、
Masatoshi Satoさん）よりアドバイスをいただきました。
いつもいつも感謝に絶えません！！

お便り２００２／１／２２
from=ｄ３

質問＜７６７＞の解答です．

A[1]の方から決めていくことにします．
A[1]≦2から，A[1]＝1,2です．２通り．
A[2]≦3から，A[2]＝1,2,3ですが，先ほど１つ使っていますから，２通り．
A[3]，A[4]，・・・A[n－1]についても，同様に２通りです．
A[n]は１通りです．したがって2＾(n－1)通りになります．

正確には数学的帰納法を使うのでしょうか？
Sekiya先生のｓｉｔｅにも同じような問題があったような？

それでは，お身体を大切になさってください．

お便り２００２／１／２２
from=CharlieBrown

A1から順番に考えていけばわかります。まずA1を選ぶ選び方は、
条件 A1≦2 より、1または2の2通りです。次にA2を選ぶ選び方を
考えると、条件 A2≦3 より、1から3までの3通りですが、1と2の
どちらか1つは既にA1で使われているので、残り2つから選ぶこと
になり、やはり2通りです。A3以降も同様で、常に残り2つからど
ちらかを選ぶので2通りになります。これはn-1番目まで続きます。
最後のn番目の数Anは残った数が自動的に入るので1通りです。
従って、求める場合の数は、2×2×…×2×1＝2^(n-1) 通りです。
実は同様の問題が既に質問213にあります。
この質問ではn＝10の場合を考えていて、
2^9＝512通りの解答が得られています。

お便り２００２／１／２２
from=Masatoshi Sato

とりあえず未解決問題に入っていたので解答を作ってみました。
もうできていたらおせっかいですみません。
 
このような考え方はどうでしょう？
A1から順に選んでいくときのそれぞれの通り数を考える．
 
A1=1もしくは2なので，このうちからどちらかを選んだとする。
A1の入れ方は2通り
A2には、3もしくは、1,2のうちA1に入れなかった方のものが入る。
つまりA2の選び方も2通り
A3には、4もしくは、1,2,3のうち今まで選ばれなかったものが入る。
つまりA3の選び方も2通り
同様に
Aｎ-1には、nもしくは、1,2,......,n-1のうち今まで選ばれなかった
ものが入る。(これは一つだけである)　
つまりAn-1の選び方も2通り
Anには最後の残った一つが入る。つまり1通り

よって、２のn-1乗となる。