カタラン数 メモ
あらすじ
ネットをぶらぶらしていて、https://www.comp.tmu.ac.jp/masanori/Lecture/11discrete.pdf を見つけて読んだ。
カタラン数、名前は聞いたことがあったが真面目に追ったことはなかったけれど、PDFが分かりやすかった。
カタラン数
競技プログラミングにおける数え上げ問題について時々登場します。
自分も解けなかった問題のやり方を聞いたときに「あれはカタラン数というものがります」といわれてそんなのありかいと思った記憶があります。
カタラン数は計算過程が面倒なものの結果はとてもシンプルです。
というわけで実用的には、カタラン数が当てはまる性質を知っておいて結果を適当な所から引っ張ってこれるようにだけしておけばOK。
結果
とりあえず、結果だけ表示します。「これはカタラン数が答えになるはずだ」と分かっていればこの式を適用するだけです。
性質
カタラン数は、次の漸化式を満たすもの。
感覚的な理解として、以下のような問題であれば当てはまる。
- 分割する線をずらしながら二つの小問題に分けられる
- 分けられた二つの小問題はが小さくなるものの元の問題と同じであり、再帰的に解ける
始めに紹介したPDFでも取り上げられている例ですが、たとえば(n+2) 角形に対角線を引いてn個の三角形に分割する場合の数は上の漸化式を満たします。(ただし n=0 を便宜上1通りとする)
(説明) 基準となる辺を一つ決めます
頂点を一つ選ぶと領域が左右に分かれます 左右で分割の仕方は独立になっているので、分割iを決めたときの分け方総数は左右の積になります。
また加えて、各分割は重ならない(分割iと分割jに共通して現れる分け方がない) ので、最終的な答えは先に書いた漸化式で表せるということになります。
勘違い
勘違いというか、自分が整理する中で混乱した点ですが...
カタラン数のポイントを「分割して再帰的に解く」とだけ抑えていると、以下の過ちにハマる可能性があります(ハマった)。
- 左右の分割の添え字の和は n ではなくて n - 1
- それぞれの分割間で、共通して出てくる場合が存在してはいけない
三角形分割例で、たとえば以下のような考え方での分割をしてしまう可能性があります(誤り)。
この例では元のカタラン数のn = 8と比べて左右の分割のカタラン数の和(1+7, 2+6 ...) が減っていません。
ここで違和感なのですが、一番大きいのは各分割から共通してたどり着く分割方法があるということです。
というわけで、そもそも「重複して数え上げない」という数え上げの原則に違反するよろしくない考え方ということになります。
というわけで問題設定や添え字を適切に設定して正しい定義にフィットするようにしましょう。
適用例
見た目の異なる様々な数え上げ問題が実はカタラン数に帰着します。
ここまでで御託を述べましたが、正直初見でカタラン数であるということに気づいて正しく立式するのは難しい気がします(少なくとも自分には)
少なくとも競技プログラミングなどで使う用途であれば、具体例をたくさん覚えておく方が吉だと思います。身も蓋もない話ですが...
(初見で導くにしても、すでに持っている知識が多いほうが自分で埋めるべき考察の距離が短くなるはずです。)
以下のリンクなどから具体例を眺めてみて(、漸化式に当てはまるかを適宜確認してみて)ください。
急に雑ですみません
カタラン数 - Wikipedia
中締め(？)
本当は証明を追っていて埋めるのに時間がかかった行間をメモするつもりだったのですが、いざカタラン数の話をしようとしたときに自分の中でまとまっていなかった点を整理していたら思いのほか時間がかかってしまいました。
もともとしようと思っていた話は別に回します。
ここまで見ていただきありがとうございました
