|
なか |
|
一般化すべく、漸化式による解法を考えてみました。
1,2,...n を、小大小大・・・の順に並べることを考える。 先頭が m のときに a(n,m) 通りの並べ方があるとする。 a(n,n)=0 である。 m=1 の場合、 残る n-1 個に、改めて逆順に 1〜n-1 の番号を振りなおすと、問題は元の形にもどり、 a(n,1) = a(n-1,1) + a(n-1,2)...+ a(n-1,n-2) + a(n-1,n-1) m=2 の場合、同様に、ただし２番目に並べない数がひとつあるので、 a(n,2) = a(n-1,1) + a(n-1,2)...+ a(n-1,n-2) 以下同様に、m=1..n-1 について、 a(n,m) = a(n-1,1) + ...a(n-1,n-m) ・・・(1) ※１ n=2 のとき、並び方は{1,2}のひと通りで a(2,1)=1。 漸化式(1) により、実際 a(n,m) の表は以下のとおり。 ｎ＝２ １， ０ （ｍ＝１，２に対応して、以下同様） ｎ＝３ １， １， ０ ｎ＝４ ２， ２， １， ０ ｎ＝５ ５， ５， ４， ２， ０ ｎ＝６ １６，１６，１４，１０， ５， ０ ｎ＝７ ６１，６１，５６，４６，３２，１６，０ 以上により、��a(6,m) = a(7,1) = 61 。 ※１ 補足説明（n=6,m=3 の例） １〜６を小大小大・・と並べるのに、先頭が３の場合、 残る５個、１２４５６を大小大小・・の順に並べればよい。 大きい順に１から番号を振りなおすと、（かっこ内はもとの番号） １（６）,２（５）,３(４）,４（２）,５（１）となる。 新しい番号で、１〜５を小大小大・・と並べる問題に帰着した。 ただし、５人の先頭として４以上（もとの番号２以下）は不適。 こうして、a(6,3) = a(5,1)+a(5,2)+a(5,3) となる。 |
|
3月8日（木） 12:36:20
MAIL:naka@sansu.org 29526 |