131203 初版 131203 更新
3C2
+ Q1 • 1C1
+ Q2 = 4C2 … ③
5C3
+ Q1 • 3C2
+ Q2 • 1C1
+ Q3 = 6C3 … ④
7C4
+ Q1 • 5C3
+ Q2 • 3C2
+ Q3 • 1C1
+ Q4 = 8C4 … ⑤
9C5
+ Q1 • 7C4
+ Q2 • 5C3
+ Q3 • 3C2
+ Q4 • 1C1
+ Q5 = 10C5 … ⑥
11C6
+ Q1 • 9C5
+ Q2 • 7C4
+ Q3 • 5C3
+ Q4 • 3C2
+ Q5 • 1C1
+ Q6 = 12C6 … ⑦
⑥ の説明
例えば, a を 5文字、 b を 5文字 1列に並べることを考える。
総数は 10C5 とおり
左から j 番目で 初めて 左からの bの文字数が a の文字数より多くなるとする。
j を キーにして この 252 とおりを分類する。
j = 1
のこり 9 文字に a が 5 文字あるから 9C5 とおり
(のこり 9 文字に b が 4 文字あるから 9C4 とおり としてもよい)
この場合の数は 126 とおり
j = 3
のこり 7 文字に a が 4 文字あるから 7C4 とおり
(のこり 7 文字に b が 3 文字あるから 7C3 とおり としてもよい)
この level 1 のカタラン数 Q1 倍
この場合の数は 35 とおり
j = 5
のこり 5 文字に a が 3 文字あるから 5C3 とおり
(のこり 5 文字に b が 2 文字あるから 5C2 とおり としてもよい)
この level 2 のカタラン数 Q2 倍
この場合の数は 20 とおり
j = 7
のこり 3 文字に a が 2 文字あるから 3C2 とおり
(のこり 3 文字に b が 1 文字あるから 3C1 とおり としてもよい)
この level 3 のカタラン数 Q3 倍
この場合の数は 15 とおり
j = 9
のこり 1 文字に a が 1 文字あるから 1C1 とおり
(のこり 1 文字に b が 0 文字あるから 1C0 とおり としてもよい)
この level 4 のカタラン数 Q4 倍
この場合の数は 14 とおり
最後残っているのが level 5 のカタラン数 Q5
この場合の数は 42 とおり