Na siatce 4 × 4 trasy z lewego dolnego rogu do prawego górnego, które idą tylko w górę i w prawo, liczą 8!/(4!·4!) = 70 — stół roboczy wypisuje to jako drugi link. Większość ludzi dodaje regułę „nigdy nie idź powyżej przekątnej”, i wtedy zliczenie to 8!/(4!·5!) = 14. Oba wzory różnią się jednym czynnikiem n + 1 w mianowniku, i to cała poprawka Catalana.
56 nielegalnych ścieżek nie jest rozrzuconych: przez argument odbicia przekroczenie przekątnej paruje je jeden do jednego z trasami do przesuniętego punktu końcowego, a tych jest 8!/(3!·5!) = 56. Więc 70 − 56 = 14 i oba ekrany się zgadzają. Ten sam ciąg 1, 2, 5, 14, 42 liczy sposoby wstawiania nawiasów w ciąg czynników, triangulacje wielokąta wypukłego i legalne ciągi nawiasów — trzeci link to C₅ = 10!/(5!·6!) = 42, następna w górę, czyli liczba triangulacji siedmiokąta.
Odpowiedź
14
Jak to czytać
C₄ jako 8!/(4!·5!) na stole roboczym. Drugi link to zliczenie bez ograniczeń 8!/(4!·4!) = 70, a trzeci to następna liczba Catalana, 42.
Źródło
The Catalan numbers Cₙ = (2n)!/(n!(n+1)!) count monotone lattice paths that stay on one side of the diagonal; Euler used the sequence for polygon triangulations in 1751, the Chinese mathematician Ming'an derived the formula in the 1730s, and Eugène Catalan gave the name in 1838
Rozwiąż w kalkulatorze
Te linki otwierają właściwy kalkulator z już wpisanymi liczbami tego zadania. Powyższa linia to to, co powinien pokazać ekran — sprawdź sam.