ここから本文です

1から n までの整数を一列に並べる順列において、i 番目の数を ai (iは添字) とす...

pon********さん

2012/4/2621:15:29

1から n までの整数を一列に並べる順列において、i 番目の数を ai (iは添字) とする。

すべての i ( i = 1, 2, …,n - 1) に対し、ai+1 (i+1は添字) ≦ ai (iは添字) + 1 が成り立つような並べ方は何通りあるか。
詳細な解法のお分かりの方、お教えください。よろしくお願い致します。

閲覧数:
251
回答数:
1
お礼:
50枚

違反報告

ベストアンサーに選ばれた回答

nf1********さん

2012/4/2622:02:21

求める場合の数を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

質問した人からのコメント

2012/5/2 15:45:24

詳細な解法、有難う御座いました。とても参考になりました。

この質問につけられたタグ

みんなで作る知恵袋 悩みや疑問、なんでも気軽にきいちゃおう!

Q&Aをキーワードで検索:

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる