折り返しの問題（途中から分からない）

質問

問題を解いていたのですが(2)が難しすぎて分かりません。
問題は、

-----------------------------------------------------------
5以上の自然数nに対して、1からnまでのn個の自然数を1列に並べて、
順列 a1,a2,a3,・・・,an
を作る。ai（2≦i≦n-1）が

a(i-1)＜ai＞a(i+1)　または　a(i-1)＞ai＜a(i+1)
　　　　　　※a(i+1)は"+1"が"i"に対してかかるという意味です

を満たす時、aiは「折り返しにある」というものとする。
ただし、a1,anは折り返しに無いものとする。

(1)折り返しにある数がnのみの1個であるような順列a1,a2,・・・,anは何通りあるか。
(2)折り返しにある数がnと他に1個の合計2個であるような順列a1,a2,・・・,anは何通りあるか。
-----------------------------------------------------------

これで(1)は以下の様に記述しました。

(1)
nは両端を除いてn-2の中から1箇所に位置するので
(n-2)C(1)　（Cは選択する場合の数を調べる記号）

nより左はi-1個並べられ、選んだ数は右から大きい順に1通りに並べるので、
(n-1)C(i-1)

nより右は上の余りで、選んだ数は左から大きい順に1通りに並べるので、
1

よってiを含めた通りの数は
(n-2)C(1)*(n-1)C(i-1)*1
=(n-1)C(i-1)*(n-2)

i は2からn-1まで変化するので、(n-1)C(i-1)からiをはずすと、

Σ[i=2→n-1](n-1)C(i-1)
=(n-1)C(1)+(n-1)C(2)+(n-1)C(3)+・・・・+(n-1)C(n-2)

ここで、2項定理の
2^(n-1)=（1+1）^(n-1)=Σ[k=0→n-1](n-1)C(k)　を利用して、

Σ[i=2→n-1](n-1)C(i-1)
=2^(n-1)-(n-1)C(0)-(n-1)C(n-1)
=2^(n-1)-2　

よって求める値は　（n-1）｛2^(n-1)-2｝　（答え）

(2)
nは両端を除いてn-2の中から1箇所に位置するので、
(n-2)C(1)=(n-2)

これ以降の2つの折り返しの求め方が解けません。
どのように場合分けをするのか、分かる方宜しくお願いします。

回答No.2

rtz · ベストアンサー

下の続きです。

(2)
nを左端からk番目に配置し、この以外の折り返しはnより右にあるとする。
このとき2≦k≦n-2である。

nより左の数字は小さい順に並ぶ。
即ちある組み合わせで選ばれた数字群につき並べ方は1通り。
よってn-1個の数字からk-1個の数字を選ぶ方法(n-1)C(k-1)通りが
そのままnより左の数字の並べ方の場合の数。

さて、nより右にはn-k個の数字があるわけだが、
折り返しを1つ作るのは(1)で求めてある。
ただし、nの右隣がn-k個の最小数となってもいいので、
2^(n-k-1)－1通り。

よって、
Σ[k＝2～n-2](n-1)C(k-1)・{2^(n-k-1)－1}
＝(1/2)Σ[k＝2～n-2](n-1)C(n-k)・{2^(n-k)－2}
＝(1/2)Σ[k＝2～n-2](n-1)C(k)・{2^(k)－2}
(n-k→kとした。Σの範囲は変わらない。)
＝(1/2){(2＋1)^(n-1)－1－2(n-1)－2^(n-1)}－{(1＋1)^(n-1)－2－(n-1)}
＝(1/2)・3^(n-1)－(3/2)・2^(n-1)＋(3/2)

さらに折り返しが左にある場合も含めれば
3^(n-1)－3・2^(n-1)＋3通り

お礼

今計算終わりました。
＞2^(n-k-1)－1通り
これはk+1以降から右肩上がりの時の通りを加えているわけですね。

計算は
＝(1/2)Σ[k＝2～n-2](n-1)C(k)・{2^(k)－2}
＝(1/2){(2＋1)^(n-1)－1－2(n-1)－2^(n-1)}－{(1＋1)^(n-1)－2－(n-1)}
この関係が分かりません・・・。

補足

回答ありがとうございます。
今計算しているのですが、

＞ただし、nの右隣がn-k個の最小数となってもいいので、
＞2^(n-k-1)－1通り。

これは　2^(n-k-1)－2通り　ですよね？

回答No.6

rtz

＞計算は
＞＝(1/2)Σ[k＝2～n-2](n-1)C(k)・{2^(k)－2}
＞＝(1/2){(2＋1)^(n-1)－1－2(n-1)－2^(n-1)}－{(1＋1)^(n-1)－2－(n-1)}
＞この関係が分かりません・・・。

二項定理です。
(x＋y)^n＝Σ[k＝0～n](n)C(k)・x^k・y^(n-k)
ですので、
3^(n-1)＝(2＋1)^(n-1)
＝Σ[k＝0～n-1](n-1)C(k)・2^k・1^(n-k-1)
＝Σ[k＝0～n-1](n-1)C(k)・2^k
です。
Σの範囲が2～n-2なので、0、1、n-1を計算して引きました。

後ろ側は
2^(n-1)＝(1＋1)^(n-1)を使っています。

お礼

回答ありがとうございます。
計算できました！
最後の計算が難しかったですね・・・。
(2+1)^n＝　も覚えておきます。
ありがとうございました！

回答No.5

age_momo

(1)は解けているようですが、(2)につなぐ意味で書いてみます。

nに対して他の1～(n-1)をnの左右に振り分ける。分けたら並べ方は1通り。

2^(n-1)

ただし、nが末端に来る2通りを引いて

2^(n-1)-2

(2)nが山になっているのでもう一つの折り返しは谷
1が谷になるには

・・・1・・・・n・・・・・

残りの2～(n-1)を左右中の3種類に分けるので

3^(n-2)

ただし、左、右に一つも来ない

2*2^(n-2)

を引いて引きすぎた1を足すと(全て中の場合が重複している)

3^(n-2)-2*2^(n-2)+1

1とnの並び替えで2を掛けて

2*3^(n-2)-2^n+2

kで谷になっているのは

・・・k・・・・n・・・(k-2)・・・2,1

(k+1)～(n-1)を左右中に振り分けるので

3＾(n-k-1)

今度はnが右端になることはないのでkが左端に来る

2^(n-k-1)

を引いて、並び替えの2を掛けると

2*3＾(n-k-1)-2^(n-k)

よって答えは

2*3^(n-2)-2^n+2+Σ[k=2,n-2]{2*3＾(n-k-1)-2^(n-k)}
=2*3^(n-2)-2^n+2+{3*3^(n-3)-3-4*2^(n-3)+4}
=3^(n-1)-3*2^(n-1)+3

お礼

回答ありがとうございます。
こっちの方が簡単な解法ですね。

回答No.4

kumipapa

#3です。
一つ言い忘れました。
（２）に追記
＞　・数字をＡ、Ｂの２つのグループにわけた
＞　・ｎはＡとＢの継ぎ目に置いてしまう・・・山ができる
＞　・Ａ（またはＢ）から何かを除いてＡ（またはＢ）を２つに分ければ谷ができるね。
に加えて

・ＡとＢの継ぎ目にｎを置くと、Ａを高⇒低と並べ、Ｂを高⇒低と並べると、Ａの最後が折り返し点（谷）。その逆もあり。

お礼

回答ありがとうございます。
参考になりました。

回答No.3

kumipapa

（１）
おしいなー。
やりかけたんだから、自分の考え方で最後までやり抜いてみるのがいいですね。どうして(n-2)Ｃ1をかけのかな？それを除けば合ってるよ。

（２）
いろいろな考え方があると思う。（１）と似た考え方でできますから頑張ってみたら。
質問者さんはｎの位置を動かすように考えたんだけど、違う見方をすると、１～n－１の数字を２つのグループA,Bに分けて、ＡとＢの継ぎ目にｎを置いた、という考え方と同じですよね。

・数字をＡ、Ｂの２つのグループにわけた
・ｎはＡとＢの継ぎ目に置いてしまう・・・山ができる
・Ａ（またはＢ）から何かを除いてＡ（またはＢ）を２つに分ければ谷ができるね。

あなたなら出来そうな気がしますが。

お礼

回答ありがとうございます。
(n-2)Ｃ1はΣでの計算の段階で織り込み済みだったので
数え上げる必要はありませんでしたね。
iの変化はΣ一本に統一しておくべきでした。

回答No.1

rtz

そもそも(1)が間違っています。
n＝3や4を入れてみてください、違うことは明白です。

(1)
nが折り返しである以上、nを頂点とする山のようになっているわけで、
1は必ず左端か右端にくる。
2は1を置いた上での左端か右端にくる。
3は1と2を置いた上での左端か右端にくる。
…
n-1は余った2ヶ所のうちのどちらか。
これが2^(n-1)通り。
ただし1,2,3,4,…,nとn,n-1,…,2,1と並ぶ2つは折り返してないので除く。

お礼

なるほど、確かに
n=3を入れたら2のはずなのに4が出てきました。
2^(n-1)-2　が答えですね。
(n-1)はiの値がΣで全て網羅されているので最初のは
必要なかったようです。