4214：条件付きの数字の並べ方...

問題4214・・・ヤドカリさんのブログ http://blogs.yahoo.co.jp/oka_yadokary/24525254.html#24525254 より Orz〜

　1，2，3，4，5，6，7，8，9 の数字の全てを１回ずつ並べてできる順列のうち、

　次の条件を満たすものの個数は？

条件1： １番目の数字はどれでもよい.

条件2： ２番目以後の数字は次のいずれかにする.

残っている数字のうち、手前の数字より大きい数字のなかで最小のもの
残っている数字のうち、手前の数字より小さい数字のなかで最大のもの

例として、453261789 はこの条件に合います。

解答

上記サイトhttp://blogs.yahoo.co.jp/oka_yadokary/24628946.html より Orz〜

[解答1] 

例のように、最初をにすると、
より大きい数だけに着目すれば、の順に並び、
より小さい数だけに着目すれば、の順に並びます。
つまり、で始まる順列は残り８ヶ所のうちを入れる３ヶ所を選ぶ、₈Ｃ₃ 通りです。
一般に、ｋで始まる順列は８ヶ所のうち k−1 ヶ所を選ぶ、₈Ｃ_k-1 通りです。
従って、₈Ｃ₀＋₈Ｃ₁＋₈Ｃ₂＋₈Ｃ₃＋₈Ｃ₄＋₈Ｃ₅＋₈Ｃ₆＋₈Ｃ₇＋₈Ｃ₈＝2⁸＝256 個あります。


[解答2] 

逆に９番目の数字から考えると、 は  になります。
９番目は、のうちの最大の数字または最小の数字で、
８番目は、９番目に使った残りの数字のうちの最大の数字または最小の数字、
同様に、２番目まで、残りの数字のうちの最大の数字または最小の数字を選び、
１番目は、残り１個の数字になります。
従って、2⁸＝256 個あります。

[解答3] crazy_tomboさんのコメントより 

＋，− の２種類のものを重複を許して８個を並べ、
一番右の − から …… 、 一番右の ＋ から …… と書き換え、
残った数字を先頭につけると、条件に合う順列ができます。

例えば、
＋−−＋−＋＋＋ → ＋＋＋＋＋ →  として先頭にをつけると、
 になります。

　逆に、２番目から後の数字を、先頭の数字と比べて大小を＋−で表せば、
 → ＋−−＋−＋＋＋ に直せます。

　従って、２種類のものを重複を許す８個の並べ方で、 2⁸＝256 個あります。

*解答2が素直でしたね♪

ちなみにわたしの crude な解答は...(やどかりさんに洗練していただきグラッチェです ^^;...Orz〜)

ある数と次の数との大小の関係を+1 or -1 で表すとき...
つまり...これは向きだけを意味する...
ある数からの向きは...1~9 の8個の間を動くので...
8回、右か左に向きを変えて動くことに１対１に対応 !!
つまり...2^8

例えば...1,1,1,-1,-1,-1,1,-1=567843291
となってる♪

[スモークマン]

＞鍵コメ様へ ^^
グラッチェ♪
デフォルメされたらそうなるんだぁ ^^;v Orz~

[スモークマン]

↑
やどかりさんの解答がアップされました♪