問題5416・・・やどかりさんの問題(
http://blogs.yahoo.co.jp/oka_yadokary/31614841.html)からのアナロジー Orz〜
1,2,3,4,5,6,7,8,9 を全て並べてできる順列のうち、隣り合う数字の間8ヶ所に不等号を
入れると、2ヶ所だけ > になり、他の6ヶ所は < になるものは、全部で何個?
たとえば、426813579 は、4>2<6<8>1<3<5<7<9 で条件に合います。
解答
・わたしの....
...>...>... の...の3カ所に数を入れられ、その中の数は一意に大小が決まる。
(a)...<9>...
(b)...<8>...
の場合の最後の...の部分にもう1個の>が入ればいい。
(b)の場合は...9は最初には入れない。
(a) は...やどかりさんの問題のアナロジーから...
前半にk個入れば、後半は8-k個の場合を考えればいい。... an=2n−n−1
8C1*(2^7-8)+8C2*(2^6-7)+8C3*(2^5-6)+8C4*(2^4-5)+8C5*(2^3-4)+8C6*(2^2-3)=5034
(b) は...9が後半にしか入らないので...
7C1*(2^6-7)+7C2*(2^5-6)+7C3*(2^4-5)+7C4*(2^3-4)+7C5*(2^2-3)=1491
けっきょく、5034+1491=6525
でいいのかな...^^;...?
↑
全然間違ってる...^^;...Orz...
☆ たけちゃんさんのコメントより(私も確認しました)
>が2個の場合 3n−n+1C1・2n+n+1C2 通り
>が3個の場合 4n−n+1C1・3n+n+1C2・2n−n+1C3 通り
以下、同様です。
・たけちゃんさんのコメより Orz〜
>が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)C1)*k^n+((n+1)C2)*(k-1)^n-((n+1)C3)*(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)
を用いて考えてみました.
・uch*n*anさんのもの Orz〜
たけちゃんさんの結果ですが,単純に,
「>」が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 個の場合も同様にできるとは思いますが,この方法だと計算が大変そうです。
・鍵コメT様よりのもの Orz〜
考え方のポイントですが,
「>」が1箇所である数をa[n],「>」が2箇所である数をb[n]として,
a[n]=2^n-n-1.
(以下,「a[n]の順列」などの言い方をします.正しい言い方ではないですが...)
例えばb[9]の順列(例:124685937とか124683957)について,
9を取り除くと,「>」の個数は2個のままか,1個に減るかです.
b[8]の順列の1つ(例:12468537)については,
もともと>であるところ,または末尾のいずれかに9を挿入して,
b[9]の順列が3つできます.
a[8]の順列の1つ(例:12468357)については,
もともと<であるところ,または先頭のいずれかに9を挿入して,
b[9]の順列が7つできます.
つまり,b[9]=3b[8]+7a[8].
この考え方から,
b[3]=1,
b[4]=3b[3]+2a[3]=11
b[5]=3b[4]+3a[4]=66
b[6]=3b[5]+4a[5]=302
b[7]=3b[6]+5a[6]=1191
b[8]=3b[7]+6a[7]=4293
b[9]=3b[8]+7a[8]=14608
*熟読玩味ぃ〜☆
みなさん凄いなぁ!!♪...嬉しくなってきちゃう♡