FC2ブログ

Welcome to my blog

[答502] 1ヶ所だけ大小の順

ヤドカリ

ヤドカリ


'


[答502] 1ヶ所だけ大小の順


 1,2,3,4,5,6,7,8,9 を全て並べてできる順列のうち、隣り合う数字の間8ヶ所に不等号を

 入れると、1ヶ所だけ > になり、他の7ヶ所は < になるものは、全部で何個?

 たとえば、246813579 は、2<4<6<8>1<3<5<7<9 で条件に合います。


[解答1]

 1,2,3,4,5,6,7,8,9 のそれぞれについて、

 「>」の前に配置するか後に配置するかで 29 通り、

  ( 「>」の前に配置された数字も後に配置された数字も小さい順に並べます )

 そのうち、条件に合わないのは、

 「>」の前にどの数字も配置しない場合と、

 「>」の前に、1,12,123,1234,12345,123456,1234567,12345678,123456789 を配置する場合。

 従って、29-10=502 通りになります。


[解答2]

 「>」の前に配置する数字の個数をk個(k=1,2,3,4,5,6,7,8)とすれば、

 そのうち、1 ~ k の場合だけ条件に合わないので、

 (91-1)+(92-1)+(93-1)+(94-1)+(95-1)+(96-1)+(97-1)+(98-1)

  =8+35+83+125+125+83+35+8=502 通りです。


[解答3]

 1,2,3,……,n のこの条件を満たす順列の個数を an 通りとします。

 1,2,3,……,n,n+1 のこの条件を満たす順列は、

 1,2,3,……,n を

 この条件を満たすように並べて、n+1 を「>」の直前か最後に配置する場合 2an 通りと、

 123……n と並べて、n+1 をそれぞれの数の前に配置する n 通りがあり、

 an+1=2an+n になります。

 a2=1 より、a3=2a2+2=2・1+2=4 ,a4=2a3+=2・4+3=11 ,a5=2a4+4=2・11+4=26 ,

 a6=2a5+5=2・26+5=57 ,a7=2a6+6=2・57+6=120 ,a8=2a7+7=2・120+7=247 ,

 a9=2a8+8=2・247+8=502 となります。


☆ 漸化式の一般解は、

 an+1+(n+1)+1=2(an+n+1) より、数列{ an+n+1 }の公比が 2、

 an+n+1=(a2+2+1)・2n-2=2n 、 an=2n-n-1 です。

 もちろん、[解答3]以外でもこの式は導けます。


☆ たけちゃんさんのコメントより(私も確認しました)

 >が2個の場合 3nn+11・2nn+12 通り

 >が3個の場合 4nn+11・3nn+12・2nn+13 通り

 以下、同様です。

.

スポンサーサイト



Comments 20

There are no comments yet.
uch*n*an  
No title

(解法4)
1 ~ 9 のうちから異なる 2 個以上 9 個以下の数を選び,
1 ~ 選んだ数の最小 - 1 と選んだ数の最小以外を > の左とし,
選んだ数の最小と残りの数を > の右とすれば,
条件を満たす順列と 1:1 に対応します。例えば,
3578 を選べば 125783469,123456789 を選べば 234567891,などとなり条件を満たし。
問題文の 246813579 は 12468 を選べば実現できます。
そこで,条件を満たす順列の個数は数の選び方の場合の数に等しいので,
9C2 + 9C3 + 9C4 + 9C5 + 9C6 + 9C7 + 9C8 + 9C9
= 36 + 84 + 126 + 126 + 84 + 36 + 9 + 1 = 502 個
になります。

ヤドカリ  
No title

樹ちゃん、早速のコメントとナイス!を有難う御座います。
長い間楽しませいてくれているアベリアの花です。
接写したらこんな写真になりました。

ヤドカリ  
No title

古い人さん、早速のコメントとナイス!を有難う御座います。
本当に長い間咲いてくれています。
少し前に撮ったアベリアの写真ですがこのまま放置するとボツになりそうで使いました。

ヤドカリ  
No title

ニリンソウさん、早速のコメントとナイス!を有難う御座います。
仰る通り、アベリアの花です。
あまり目立ちませんが、長い間咲いてくれているのが嬉しいです。
当方でもこの前、霰が降りました。

ヤドカリ  
No title

アキチャンさん、早速のコメントとナイス!を有難う御座います。
透き通るような白の花は渡すも好きです。
陽ざしの暖かさを感じる季節ですね。

ヤドカリ  
No title

tsuyoshik1942さん、早速のコメントを有難う御座います。
みなさん、だいたい[解答1][解答2]でした。
本のんに関しては漸化式はやや面倒なのですが、用途が豊富ですね。

ヤドカリ  
No title

yasukoさん、早速のコメントとナイス!を有難う御座います。
よく見かけ、長い間楽しませてくれるアベリアの花、好きな花の1つです。
少し前に撮ったのですが、このまま写真を放置するとボツになりそうで……。

ヤドカリ  
No title

スモークマンさん、コメントを有難う御座います。
[>] が2個になったら、なんて恐ろしいことを書かれますね。
きちんと考えるとかなり時間がかかりそうですし、
下手するとただ調べるだけになりそうで、考えておりません。

ヤドカリ  
No title

uch*n*anさん、コメントと別解の提示を有難う御座います。
考え方はいろいろあるかも知れませんが、
[解答1]のようなまず全体を考える方法
[解答2]のような8通りの場合分け
みなさん、このような考え方でしたので、却って複雑ですが、
これと計算が全然違う漸化式を解答に追加しました。

たけちゃん  
No title

>が2個の場合ですが,多分3^n-(n+1)*2^n+(n+1)n/2通りだと思います.

ついでに言えば,
>が3個なら,多分4^n-(n+1)*3^n+(n+1)n/2*2^n-(n+1)n(n-1)/6通り,
>がk個なら,(k+1)^n-((n+1)P1)*k^n+((n+1)P2)*(k-1)^n-((n+1)P3)*(k-2)^n+…
と思います.
upの回数a,downの回数b に対する個数をN(a,b) として,
漸化式N(a,b)=(b+1)N(a-1,b)+(a+1)N(a,b-1)
を用いて考えてみました.

たけちゃん  
No title

失礼,Pと書いたところはCでした.
(k+1)^n-((n+1)C1)*k^n+((n+1)C2)*(k-1)^n-((n+1)C3)*(k-2)^n+…
です.肝心なところを間違えた...

ゆうこ つれづれ日記  
No title

こんばんは~
初めて見るお花です。
木に咲くお花ですか?
まだまだ咲くお花が見られていいですね。
ナイス☆

さっちゃんこ  
No title

こんばんは
アベリアのようですがまだ咲いているのですネ
此の花も花期がいので好きな花です ナイス☆

ヤドカリ  
No title

たけちゃんさん、コメントを有難う御座います。
確認し、本文に加筆させて頂きました。
途中の式を書いていくと長くなりますので省略しますが、
それで良いと思います。

ヤドカリ  
No title

ゆうこさん、コメントとナイス!を有難う御座います。
アベリアの花は長い間咲いています。
小さな花だけに可愛いです。

ヤドカリ  
No title

さっちゃんこさん、コメントとナイス!を有難う御座います。
花期の長い花ですね。
長く咲いている花はアップし忘れて写真をボツにすることがあるのですが、
綺麗に咲いていたのでここで使いました。

uch*n*an  
No title

たけちゃんさんの結果ですが,単純に,
「>」が2個の場合
(3^n - 3C2 * 2^n + 3C1 * 1^n) - (n-2)C1 * (2^n - (n+1)C1) - (n-1)C2
= 3^n - (n+1)C1 * 2^n + (n+1)C2
「>」が3個の場合
(4^n - 4C3 * 3^n + 4C2 * 2^n - 4C1 * 1^n)
- (n-3)C1 * (3^n - (n+1)C1 * 2^n + (n+1)C2)
- (n-2)C2 * (2^n - (n+1)C1)
- (n-1)C3
= 4^n - (n+1)C1 * 3^n + (n+1)C2 * 2^n - (n+1)C3
と求まります。
ただ,「>」が k 個の場合も同様にできるとは思いますが,この方法だと計算が大変そうです。

ヤドカリ  
No title

uch*n*anさん、コメントを有難う御座います。
昨日は考える気がしなかったのですが、
考えて見ると思ったほどではありませんでした。
「>」が k 個の場合は、計算式がかなり長くなり面倒ですね。

スモークマン  
No title

グーテンターク ^^
調べてみました...^^
この数列は...Euler's triangleに現れるオイラー数って呼ばれてるもののようですね☆
数列大辞典A000460

http://www.iis.it-hiroshima.ac.jp/~ohkawa/pdf/pascal.pdf
「オイラー数」 という。
集合{1,2,...,n }上の置換の中 で,k 個の上昇をもっている置換の数がオイラ ー数nOkである。」

...半知半解なわたし...^^;...Orz~

ヤドカリ  
No title

スモークマンさん、コメントを有難う御座います。
オンライン整数列大辞典で[解答3]で出た答で検索してもいいですね。
[解答3]を示したのにも関わらず、調べることは思いつきませんでした。