niacin https://blog.hatena.ne.jp/niacin/ 一数学教師日記 https://niacin.hatenadiary.org/ 数学雑記 原点と(n,n)を結ぶ最短経路はだが、このうち領域に含まれるものの個数はカタラン数になる。鏡像を使う方法が簡単だが思いつきにくい。ここでは漸化式を考える。上記の場合の数をA(n)と書くことにする。これらの経路を、直線y=x上(ただし原点を除く)に初めて到着する点(k,k)で分類する。ただし、 である。すると、原点→(1,0)→(k,k-1)→(k,k)→(n,n)となる。(1,0)→(k,k-1)の経路はA(k-1)通りであり、(k,k)→(n,n)の経路はA(n-k)通りである。ただし、k=1の場合は前者は１通りなので、A(0)=1 と約束しておく。すると、全体では となる。右辺はいわゆる合… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fniacin.hatenadiary.org%2Fentry%2F20060822%2Fp3" title="カタラン数と経路の数と漸化式 - 一数学教師日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2006-08-22 00:00:02 rich https://niacin.hatenadiary.org/entry/20060822/p3 1.0 100%