質問: 1から n までの整数を一列に並べる順列において、i 番目の数を ai (iは添字) とする。
回答: 求める場合の数をA(n)通りとする。 A(1)=1 , A(2)=2 は容易にわかる。 A(n)=2^(n-1)を数学的帰納法で証明する。 n以下で成り立つとしてn+1のときを考える。 n+1が先頭にくる並べ方ではそれ以後のn個の整数 (1からnまで)を条件を満たすように並べればよいから A(n)通りある。 n+1が2番目にくる並べ方では1番目にはnしかこれない。 残りのn-1個の整数(1からn-1まで)を条件を満たすように 並べればよいからA(n-1)通りある。 n+1が3番目にくる並べ方では2番目にはn、1番目にはn-1 しかこれない。残りのn-2個の整数(1からn-2まで)を条件を 満たすように並べればよいからA(n-2)通りある。 以下同様 ∴A(n+1)=A(n)+A(n-1)+・・・・+A(1)+1 =2^(n-1)+2^(n-2)+・・・・2+1+1=2^n