131102 初版 131102 更新
カタラン数どうしのこんな関係式がでてくる。
1 • 12C6
+ 2 • 10C5
+ 5 • 8C4
+ 14 • 6C3
+ 42 • 4C2
+ 132 • 2C1
+ 429 = 14C6 … ①
1 • 13C6
+ 2 • 11C5
+ 5 • 9C4
+ 14 • 7C3
+ 42 • 5C2
+ 132 • 3C1
+ 429 = 15C6 … ②
1 •
14C
6
+ 2 •
12C
5
+ 5 •
10C
4
+ 14 •
8C
3
+ 42 •
6C
2
+ 132 •
4C
1
+ 429 =
16C
6 … ③
(
説明)
\(1 \cdot \dfrac{n(n-1)(n-2)(n-3)(n-4)(n-5)}{6!}
+ 2 \cdot \dfrac{(n-2)(n-3)(n-4)(n-5)(n-6)}{5!}\)
\(+ 5 \cdot \dfrac{(n-4)(n-5)(n-6)(n-7)}{4!}
+ 14 \cdot \dfrac{(n-6)(n-7)(n-8)}{3!}\)
\(+ 42 \cdot \dfrac{(n-8)(n-9)}{2!}
+ 132(n-10)
+ 429\)
\(=\dfrac{(n+2)(n+1)n(n-1)(n-2)(n-3)}{6!}\) … ④
二項係数の漸化式を用いると
① ② より
1 • 12C5
+ 2 • 10C4
+ 5 • 8C3
+ 14 • 6C2
+ 42 • 4C1
+ 132 = 14C5
これは 一手前 level 6 までのカタラン数の関係式
④ で n = 3 とすると
\(429= -5
+ 14 \cdot {}_5{\rm C}_{3}
- 42 \cdot {}_6{\rm C}_{2}
+ 132 \cdot {}_7{\rm C}_{1}\)
この手の式も面白くて，
\(1 \cdot \dfrac{n(n-1)(n-2)(n-3)}{4!}
+ 2 \cdot \dfrac{(n-2)(n-3)(n-4)}{3!}\)
\(+ 5 \cdot \dfrac{(n-4)(n-5)}{2!}
+ 14 (n-6)+42
=\dfrac{(n+2)(n+1)n(n-1)}{4!}\)
\(1 \cdot \dfrac{n(n-1)(n-2)}{3!}
+ 2 \cdot \dfrac{(n-2)(n-3)}{2!}
+ 5 (n-4)
+ 14
=\dfrac{(n+2)(n+1)n}{3!}\)
\({\rm Q}_4=14=-2 \cdot {}_3{\rm C}_{2}
+ 5 \cdot {}_4{\rm C}_{1}\)
\({\rm Q}_5 = 42=2 \cdot {}_3{\rm C}_{3}
- 5 \cdot {}_4{\rm C}_{2}
+ 14 \cdot {}_5{\rm C}_{1}\)
\({\rm Q}_6 =429= -5
+ 14 \cdot {}_5{\rm C}_{3}
- 42 \cdot {}_6{\rm C}_{2}
+ 132 \cdot {}_7{\rm C}_{1}\)
\({\rm Q}_7 = 1430 =
- 14 \cdot {}_5{\rm C}_{4}
+ 42 \cdot {}_6{\rm C}_{3}
- 132 \cdot {}_7{\rm C}_{2}
+ 429 \cdot {}_8{\rm C}_{1}\)
\(\dfrac{(n+2)(n+1)n}{3!}
-\dfrac{n(n-1)(n-2)}{3!}\)
\(=2 \cdot \dfrac{(n-2)(n-3)}{2!}
+ 5 (n-4) + 14\)