Cztery kroki w górę i cztery w bok bez przekraczania przekątnej: 14 z 70 ścieżek

Środkowy współczynnik dwumianowy liczy wszystkie trasy; wzór Catalana liczy te legalne.

Statystyka i dane · Poziom: Klasyczny wynik · Zaktualizowano 2026-11-10

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.

To niezależny serwis informacyjny prowadzony przez stronę trzecią. Nie jest powiązany z firmami Casio, Texas Instruments ani ich dystrybutorami, nie jest przez nie sponsorowany ani autoryzowany. Nazwy modeli i produktów są znakami towarowymi ich właścicieli i pojawiają się tutaj wyłącznie w celu identyfikacji urządzeń.

Sekwencje naciskania klawiszy w tych instrukcjach powstały na podstawie własnych danych o układzie klawiatury z tego serwisu — tych samych, które renderuje kalkulator online — oraz publicznie dostępnych informacji o produktach. Specyfikacje i konfiguracje regionalne są potwierdzane na fizycznym urządzeniu i w najnowszych materiałach producenta.