131024 初版 131024 更新
ababababab, aaaaabbbbb のような並びを同じものを含む順列という
a 3文字, b 2 文字の5文字を一列に並べる場合の数は 10 とおり である。
5文字を
a
1, a
2, a
3, b
1, b
2,
のように区別して一列に並べる場合は 5! で 120 とおりある。
このうち、
例えば、
a
1 a
2 b
1 b
2 a
3,
a
1 a
3 b
1 b
2 a
2,
a
2 a
1 b
1 b
2 a
3,
a
2 a
3 b
1 b
2 a
1,
a
3 a
1 b
1 b
2 a
2,
a
3 a
2 b
1 b
2 a
1,
a
1 a
2 b
2 b
1 a
3,
a
1 a
3 b
2 b
1 a
2,
a
2 a
1 b
2 b
1 a
3,
a
2 a
3 b
2 b
1 a
1,
a
3 a
1 b
2 b
1 a
2,
a
3 a
2 b
2 b
1 a
1
の 12 とおり は
同一視するので、
120÷ 12 で 10 なのである。
a が m 文字, b が n 文字の2種類 m+n 文字 を一列に並べる場合の数は
\(\dfrac{(m+n)!}{m!\cdot n!}\) である。
まずは、
level 5 のカタラン数は
\(\dfrac{10!}{5!\cdot 5!}\) の 252 より小さい。
もっとも、先頭は a, 末尾は b なので
level 5 のカタラン数は
\(\dfrac{8!}{4!\cdot 4!}\) の 70 より小さい。