131101 カタラン数がらみの問題を作ろう02a

131202 初版 131202 更新

某有名参考書新課程版 (旧課程版にもあり)

1を n 個、2を n 個、計 2n 個並べる列
a₁a₂…a_2n を考える。
このような列
a₁a₂…a_2n の並べ方の総数を P_n とすると
P₃ = 20, P₄ = 70
また、どの i=1, 2, …, 2n に対しても、 a₁a₂…a_i の中で
1の現れる回数が2の現れる回数以上である列
a₁a₂…a_2n の並べ方の総数を Q_n とすると
Q₃ = 5, Q₄ = 14, Q₅ = 42

最短経路問題だというのを頭の片隅において，

左から j 番目で初めて2の個数が1の個数より多くなるとする。

n = 1 のとき，

P₁ = ₂C₁ = 2
j = 1: あと1つのうち 1 が 1 つ ₁C₁

₁C₁ + Q₁ = ₂C₁
1+ Q₁ = 2
よって，Q₁ = 1

n = 2 のとき，

P₂ = ₄C₂ = 6
j = 1: あと3つのうち 1 が 2 つ ₃C₂
j = 3: あと1つのうち 1 が 1 つ Q₁ × ₁C₁

₃C₂ + Q₁ × ₁C₁ + Q₂ = ₄C₂
3 + 1 + Q₂ = 6
よって，Q₂ = 2

n = 3 のとき，

P₃ = ₆C₃ = 20
j = 1: あと5つのうち 1 が 3 つ ₅C₃
j = 3: あと3つのうち 1 が 2 つ Q₁ × ₃C₂
j = 5: あと1つのうち 1 が 1 つ Q₂ × ₁C₁

₅C₃ + Q₁ × ₃C₂ + Q₂ × ₁C₁ + Q₃ = ₆C₃
10 + 3 + 2 + Q₃ = 20
よって，Q₃ = 5

n = 4 のとき，

P₄ = ₈C₄ = 70
j = 1: あと7つのうち 1 が 4 つ ₇C₄
j = 3: あと5つのうち 1 が 3 つ Q₁ × ₅C₃
j = 5: あと3つのうち 1 が 2 つ Q₂ × ₃C₂
j = 7: あと1つのうち 1 が 1 つ Q₃ × ₁C₁

₇C₄ + Q₁ × ₅C₃ + Q₂ × ₃C₂ + Q₃ × ₁C₁ + Q₄ = ₈C₄
35 + 10 + 6 + 5 + Q₄ = 70
よって，Q₄ = 14

n = 5 のとき，

₉C₅ + Q₁ × ₇C₄ + Q₂ × ₅C₃ + Q₃ × ₃C₂ + Q₄ × ₁C₁ + Q₅ = ₁₀C₅

ここで，

₉C₅ + Q₁ × ₇C₄ + Q₂ × ₅C₃ + Q₃ × ₃C₂ + Q₄ × ₁C₁ = ₉C₄ + Q₁ × ₇C₃ + Q₂ × ₅C₂ + Q₃ × ₃C₁ + Q₄ × ₁C₀

また，カタラン数と最短経路の関係式より，

₇C₄ + Q₁ × ₅C₃ + Q₂ × ₃C₂ + Q₃ × ₁C₁ + Q₄ = ₈C₄ から
₉C₄ + Q₁ × ₇C₃ + Q₂ × ₅C₂ + Q₃ × ₃C₁ + Q₄ × ₁C₀ = ₁₀C₄

よって，
Q₅ = ₁₀C₅ - ₁₀C₄ = 252 - 210 = 42