Ẹ̀rọ Ìṣirò Òǹkà Catalan

Nípa ẹ̀rọ ìṣirò yìí

Ẹ̀rọ ìṣirò yìí ń wá òǹkà Catalan kínní n: Cn = (2n)! / ((n+1)! · n!), àyíká-ọ̀rọ̀ (1, 1, 2, 5, 14, 42, 132, …) tí ó ń ka iye combinatorial structure tí kò dàbí ẹni pé wọ́n jọra tí ó yanilẹ́nu ti ìwọ̀n n, títí kan iye ọ̀nà tí a lè fi bá àkàmọ́ tó dọ́gba n pàrà mu dáradára, iye binary search tree ọ̀tọ̀ọ̀tọ̀ tí ó ní n nodes, àti iye ọ̀nà tí a lè fi triangulate polygon convex kan tí ó ní n+2 ẹ̀gbẹ́.

Àwọn akẹ́kọ̀ọ́ àti olùṣewádìí kọ̀ǹpútà sáyẹ́ǹsì máa ń lò ó láti ka expression tree tó wúlò, àwọn àṣàyàn parsing, àti recursive data structure, nígbà tí àwọn olùfẹ́ ìṣirò fi ń lò ó gẹ́gẹ́ bí àpẹẹrẹ àtọwọ́dọ́wọ́ ti bí àjọṣe recurrence kan ṣe ń tún farahàn kọjá ọ̀pọ̀lọpọ̀ ìṣòro combinatorics tí ó yàtọ̀. Tẹ n sínú láti rí Cn.