正方形が一行目に五列、二行目に四列、三行目に三列、隙間なく並んでいる。 この正方形の中に1〜12の整数を入れていく。そのさい、 同じ行では左側が小さく、右側が大きくなるように入れる。 同じ列では上側が小さく、下側が大きくなるように入れる。 例えば 1471012 25811 369 は題意を満たしている。このような並べ方の総数を求めよ。
教えてください。
FLH1Age171.hyg.mesh.ad.jp (220.102.54.171)
Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.0; Trident/4.0; SLCC1; .NET CLR 2.0.50727; Media Center PC 5.0; .NET CLR 3.5.30729; OfficeLiveConnector.1.3; OfficeLivePatch.0.0; .NET CLR 3.0.30729)
|
6123.Re: カタラン数? |
| 名前:中川 幸一 日付:11月22日(日) 11時6分 |
こういう問題は, 具体的に見ていくと解答の方針が立ったりします. また, 一般化して考えるという方法も手です.
N = i + j + k (i>j>k) とおく. 上段には正方形が i 個 中段には正方形が j 個 下段には正方形が k 個 となるように左端を揃えて隙間なく並んでいるとする. この正方形の中に 1〜N までの整数を以下の条件に従い 1 つずつ入れていく. ・同じ行では左側が小さく, 右側が大きくなるように入れる. ・同じ列では上側が小さく, 下側が大きくなるように入れる. この 2 つの条件を満たすように 1〜N を並べる並べ方の総数を f(i, j, k) とする.
今回の場合は 『f(5, 4, 3) を求めよ.』 という問題に帰着されます.
それでは順にこの問題の条件の性質を見ていきましょう. i>j>k>2 のとき, 数字の配置方法として, 1 と N はどこに配置されるかは容易に分かると思います. 1:上段の左端 N:各段の右端のいずれか よって, N の配置方法により以下の等式が成り立つことが分かります. f(i, j, k) = f(i-1, j, k) + f(i, j-1, k) + f(i, j, k-1) また, i=j のとき, f(i, i, k) = f(i, i-1, k) + f(i, i, k-1) j=k のとき, f(i, j, j) = f(i-1, j, j) + f(i, j, j-1) i=j=k のとき, f(i, i, i) = f(i, i, i-1) という関係も容易に分かると思います.
あとはこれらの関係を元に順次値を求めていけば求まるはずです. ちなみに, 初期値として以下のことが容易に分かると思います. f(1, 1, 1) = 1 f(n-2, 1, 1) = (n-1)(n-2)/2 f(i, j, 1) = f(i-1, j, 1) + f(i, j-1, 1) + f(i, j, 0) = Σ[a=1 to i](Σ[b=1 to j] f(a, b, 0)) (ただし, f(1, 1, 0) = 1)
http://www3.ezbbs.net/01/k-nakagawa/
ZB157019.ppp.dion.ne.jp (219.125.157.19)
Mozilla/5.0 (Windows; U; Windows NT 5.1; ja; rv:1.9.1.5) Gecko/20091102 Firefox/3.5.5
|
|
6124.Re: カタラン数? |
| 名前:z 日付:11月22日(日) 13時1分 |
丁寧な解答ありがとうございました。 ただ、 >よって, N の配置方法により以下の等式が成り立つことが分かります. f(i, j, k) = f(i-1, j, k) + f(i, j-1, k) + f(i, j, k-1) また, i=j のとき, f(i, i, k) = f(i, i-1, k) + f(i, i, k-1) j=k のとき, f(i, j, j) = f(i-1, j, j) + f(i, j, j-1) i=j=k のとき, f(i, i, i) = f(i, i, i-1) という関係も容易に分かると思います.
の部分がまだ理解できていません。もう少し考えてみたいと思います。
FLH1Age171.hyg.mesh.ad.jp (220.102.54.171)
Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.0; Trident/4.0; SLCC1; .NET CLR 2.0.50727; Media Center PC 5.0; .NET CLR 3.5.30729; OfficeLiveConnector.1.3; OfficeLivePatch.0.0; .NET CLR 3.0.30729)
|
|
|