131027 初版 131027 更新
最短経路が、同じものを含む順列、組合せと同型なのだから、
カタラン数も、最短経路問題の一部となる。
実際、level 5 のカタラン型の例として、
ababababab あるいは 1010101010 は、
階段型の街路の最短経路になっている。
一般に、A か Aでないか 繰り返しの場合の数は、
街路の最短経路問題の一部である。
問題を解く際には、
どうやって考えるかを与えるのが学習にはよい。
私はよく、言いかえというが、
同値な条件に言いかえるとか、同型なものへの対応とかいわれることである。
この階段型の右端がカタラン数である。
Qn: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …
左右の図を比べると予想ができる。
| 1 | = | 2 | - | 1 | = | 1 | - | 0 |
= | 2 | ÷ | 2 |
| 2 | = | 6 | - | 4 | = | 3 | - | 1 |
= | 6 | ÷ | 3 |
| 5 | = | 20 | - | 15 | = | 10 | - | 5 |
= | 20 | ÷ | 4 |
| 14 | = | 70 | - | 56 | = | 35 | - | 21 |
= | 70 | ÷ | 5 |
| 42 | = | 252 | - | 210 | = | 126 | - | 84 |
= | 252 | ÷ | 6 |
| 132 | = | 924 | - | 792 | = | 462 | - | 334 |
= | 924 | ÷ | 7 |
Qn = 2nCn - 2nCn+1 =
\(\dfrac{(2n)!}{n!\cdot n!}-\dfrac{(2n)!}{(n+1)!\cdot (n-1)!}\)
Qn = 2n-1Cn - 2n-1Cn+1 =
\(\dfrac{(2n-1)!}{n!\cdot (n-1)!}-\dfrac{(2n-1)!}{(n+1)!\cdot (n-2)!}\)
Qn = \(\dfrac{{}_{2n}{\rm C}_{n}}{n+1} = \dfrac{(2n)!}{n!\cdot(n+1)!}\)
9C5
+ Q1 • 7C4
+ Q2 • 5C3
+ Q3 • 3C2
+ Q4 • 1C1
+ Q5 = 10C5
126
+ 1 • 35
+ 2 • 10
+ 5 • 3
+ 14 • 1
+ 42 = 252
11C5
+ Q1 • 9C4
+ Q2 • 7C3
+ Q3 • 5C2
+ Q4 • 3C1
+ Q5 = 12C5
462
+ 1 • 126
+ 2 • 35
+ 5 • 10
+ 14 • 3
+ 42 = 792
Q
1 •
9C
4
+ Q
2 •
7C
3
+ Q
3 •
5C
2
+ Q
4 •
3C
1
+ Q
5 =
11C
4
…
説明
1 • 126
+ 2 • 35
+ 5 • 10
+ 14 • 3
+ 42 = 330