FC2ブログ

Welcome to my blog

[答1385] 偶数番目が奇数番目より小さい順列

ヤドカリ

ヤドカリ

P3310076.jpg



[答1385] 偶数番目が奇数番目より小さい順列


 1,2,3,……,n をすべて並べる方法のうち、偶数番目の数がその隣(最後以外は両隣)の数より

 小さい並べ方は何通りかを求めます。例えば、1,2,3 の並べ方は、213,312 の 2 通り、

 1,2,3,4 の並べ方は、2143,3142,3241,4132,4231 の 5 通りです。

 では、1,2,3,4,5,6,7,8 の並べ方は何通り?


[解答1]

 1,2,3,……,n の並べ方を f(n) 通り、f(0)=1 とします。

 最大数nは奇数番目に並べないといけません。nの左右の数の選び方と並べ方を考えます。

 nがk番目 (k=1,3,5,……,2[(n-1)/2]+1) にある場合は n-1k-1・f(k-1)・f(n-k) 通りです。

 明らかに f(1)=f(2)=1 、問題例より f(3)=2 ,f(4)=5 ですので、

 f(5)=f(4)+42・f(2)・f(2)+44・f(4)・f(0)=5+6・1・1+1・5・1=16 、

 f(6)=f(5)+52・f(2)・f(3)+54・f(4)・f(1)=16+10・1・2+5・5・1=61 、

 f(7)=f(6)+62・f(2)・f(4)+64・f(4)・f(2)+66・f(6)・f(0)=61+15・1・5+15・5・1+1・61・1=272 、

 f(8)=f(7)+72・f(2)・f(5)+74・f(4)・f(3)+76・f(6)・f(1)=272+21・1・16+35・5・2+7・61・1=1385 、

 f(8)=1385 です。


[解答2]

 1,2,3,……,n の並べ方を f(n) 通り、f(0)=1 とします。

 最小数1は偶数番目に並べないといけません。nの左右の数の選び方と並べ方を考えます。

 1がk番目 (k=2,4,6,……,2[n/2]) にある場合は n-1k-1・f(k-1)・f(n-k) 通りです。

 明らかに f(1)=f(2)=1 、問題例より f(3)=2 ,f(4)=5 ですので、

 f(5)=41・f(1)・f(3)+43・f(3)・f(1)=4・1・2+4・2・1=16 、

 f(6)=51・f(1)・f(4)+53・f(3)・f(2)+55・f(5)・f(0)=5・1・5+10・2・1+1・16・1=61 、

 f(7)=61・f(1)・f(5)+63・f(3)・f(3)+65・f(5)・f(1)=6・1・16+20・2・2+6・16・1=272 、

 f(8)=71・f(1)・f(6)+73・f(3)・f(4)+75・f(5)・f(2)+77・f(7)・f(0)=7・1・61+35・2・5+21・16・1+1・272・1=1385 、

 f(8)=1385 です。

.
スポンサーサイト



Comments 2

There are no comments yet.
ニリンソウ  

艶やかですね~
これは絞り柄ですが真紅な花も見かけます
赤を撮るのが苦手(うちの椿もよく撮れない)
さくらが終えると
次つぎ季節の花が廻りますね。

ヤドカリ
ヤドカリ  
Re: タイトルなし

ニリンソウさん、コメントを有難うございます。
源平桃といわれる桃の花、所々で見かけます。
赤と白のとりあわせの花は他にもときどきありますね。