131101 最短経路とカタラン数

131203 初版 131203 更新

数学の小部屋トップページ
もくじ > 拡張カタラン数カタラン数どうしの関係式旧バージョン

カタラン数どうしのこんな関係式がでてくる。

1 • ₁₂C₆ + 2 • ₁₀C₅ + 5 • ₈C₄ + 14 • ₆C₃ + 42 • ₄C₂ + 132 • ₂C₁ + 429 = ₁₄C₆ … ①

1 • ₁₃C₆ + 2 • ₁₁C₅ + 5 • ₉C₄ + 14 • ₇C₃ + 42 • ₅C₂ + 132 • ₃C₁ + 429 = ₁₅C₆ … ②

最短経路による説明 (説明)

出発点を変えると次のような式も出てくる。

₃C₂ + Q₁ • ₁C₁ + Q₂ = ₄C₂ … ③

₅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₁ + Q₅ = ₁₀C₅ … ⑥

₁₁C₆ + Q₁ • ₉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₄ + Q₂ • ₅C₃ + Q₃ • ₃C₂ + Q₄ = ₁₀C₄ … ⑩

だから，⑥ ⑩ より

Q₅ = ₁₀C₅ -₁₀C₄