英語版Wikipedia “Catalan number”に、凸n角形の三角形分割の場合の数が
と表されることの証明として以下のようなものが紹介されていたのですが、単語の意味を調べても理解することができませんでした。
この証明の内容を解説していただけると嬉しいです。よろしくお願いします。
![](https://res.cloudinary.com/bend/c_scale,f_auto,q_auto,w_500/qa/ugc/manabitimes/question/1670590073_8syvak.jpeg)
ベストアンサー
![ベストアンサー](https://res.cloudinary.com/bend/image/upload/f_auto,q_50,w_80/v1608343659/manabitimes/illust/medal_udx9ah.png)
翻訳だけですが、どうぞ。
解説は申し訳ないですが、
出来そうにないです。
この証明では、カタロニア数字の三角測量の定義を使って C と Ch+1• の関係を確立します。
辺が n + 2 で三角形になっている多角形 P が与えられたら、その辺の 1 つを底辺としてマークし、合計 2n + 1 の辺のうちの 1 つの向きも合わせます。与えられた底辺には、(4n + 2) Cの三角形分割のようなマークがついています。
辺が n + 3 で、三角形分割が (異なる) ポリゴン Q が与えられたら、その辺の 1 つを底辺としてマークします。底辺以外の辺の1つに印を付けます(内側の三角形の端ではありません)。
与えられた底辺には、(n + 2) C. + 1 個のこのようなマークが付いた三角形があります
これら 2 つのマークが付いた三角形の間には単純な二乗法があります。Q の辺に印を付けた三角形を (2 つの方法で折りたたみ、底辺が折りたためない 2 つを引く) か、逆に P の方向を向いた辺を三角形に広げてマークします。
したがって
(4n + 2) Cn = (n+ 2) Cn+ 1。
I Cn-1 = Ch と入力します。
なぜなら(2n)!= (2n)!!(2n-1)!!
=2"n!(2n-1)!!
それから
(2 n)!= 2"(2n-1)!!
= (4n-2)!!!!
C = 1 で再帰を適用すると、結果が得られます。