Czym są liczby Catalana?

To szczególny ciąg liczbowy nazwany na cześć pochodzącego z Belgii matematyka Eugène Charlesa Catalana, który rozważał je jako liczbę sposobów rozmieszczenia nawiasów.

Natomiast liczby te przedstawione zostały w 1751 roku przez Leonarda Eulera na potrzeby badania liczby podziałów wielokątów na trójkąty. Kompletny dowód udało się uzyskać z pomocą Goldbacha i Segnera. Niemniej, ciąg liczb Catalana pojawił się w pewnej postaci już w latach 30. XVIII wieku w książce chińskiego matematyka Ming Antu.

Liczby Catalana bywają nazywane również liczbami Segnera na cześć matematyka Johanna Segnera. Termin liczby Catalana przedstawił John Riordan w 1948 roku w Math Reviews, a zyskał on popularność m.in. za sprawą Martina Gardnera, który w 1976 roku użył go w magazynie Scientific American.

Jak wyznaczyć kolejne liczby Catalana?

Sposób 1: wzór jawny

Tak jak w przypadku innych ciągów, n-tą liczbę Catalana można wyznaczyć jako n-ty wyraz ciągu określonego wzorem jawnym

$${\displaystyle c_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\mbox{ dla }}n\geqslant 0}$$

Sposób 2: wzór rekurencyjny

Znając wzór jawny, wzór rekurencyjny można prosto wyprowadzić w poniższy sposób $${\large\displaystyle \frac{c_{n+1}}{c_{n}}={\frac {\frac{(2(n+1))!}{(n+1+1)!(n+1)!}}{\frac{(2n)!}{(n+1)!n!}}}\qquad }$$ $${\displaystyle \frac{c_{n+1}}{c_{n}}={\frac {(2(n+1))!}{(n+2)!(n+1)!}} \cdot {\frac{(n+1)!n!}{(2n)!}}\qquad }$$ $${\displaystyle \frac{c_{n+1}}{c_{n}}={\frac {(2n+2)!}{(n+2)!(n+1)!}} \cdot {\frac{(n+1)!n!}{(2n)!}}\qquad }$$ $${\displaystyle \frac{c_{n+1}}{c_{n}}={\frac {(2n+2)!}{(n+2)(n+1) n!}} \cdot {\frac {n!}{(2n)!}}\qquad }$$ $${\displaystyle \frac{c_{n+1}}{c_{n}}={\frac {(2n+2)!}{(n+2) (n+1)}} \cdot {\frac {1}{(2n)!}}\qquad }$$ $${\displaystyle \frac{c_{n+1}}{c_{n}}={\frac {(2n+2) (2n+1) (2n)!}{(n+2) (n+1)}} \cdot {\frac {1}{(2n)!}}\qquad }$$ $${\displaystyle \frac{c_{n+1}}{c_{n}}={\frac {(2n+2) (2n+1)}{(n+2) (n+1)}} \cdot {\frac {1}{1}}\qquad }$$ $${\displaystyle \frac{c_{n+1}}{c_{n}}={\frac {2(n+1) (2n+1)}{(n+2) (n+1)}} \qquad }$$ $${\displaystyle \frac{c_{n+1}}{c_{n}}={\frac {2(2n+1)}{n+2}}\qquad }$$ $${\displaystyle c_{n+1}={\frac {2(2n+1)}{n+2}} c_{n} \qquad }$$

Końcowo otrzymujemy wzór rekurencyjny w postaci $$\large\left\{\begin{array}{cc} c_{0} = 1\\ c_{n+1} = {\frac {2(2n+1)}{n+2}} c_{n}\\ \end{array} \right.$$

Kolejne liczby Catalana

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, ...

Co ciekawe, liczby te można otrzymać po podzieleniu środkowych liczb w trójkącie Pascala przez kolejne liczby całkowite dodatnie.

Program wyznaczajacy n-tą liczbę Catalana

Zadania

Liczby Catalana znajdują zastosowanie w wielu ciekawych problemach z zakresu kombinatoryki. Za sprawą m.in. tego poświęcone jest im najwięcej tekstu w Encyklopedii Ciągów Liczb Całkowitych w Wersji On-Line (OEIS).

I. Liczba monotonicznych dróg

Dany jest kwadrat o boku n. Ilość wszystkich monotonicznych dróg z lewego dolnego wierzchołka do prawego górnego wierzchołka, przy założeniu, że nie możemy przekroczyć przekątnej, która łączy te wierzchołki, jest n-tą liczbą Catalana.

Sprawdźmy tę prawidłowość!

Kwadrat ABCD o boku n = 5 umieszczamy w układzie współrzędnych. Początek drogi jest w punkcie A(0, 0), a koniec w punkcie C(5, 5). Dozwolone są jedynie ruchy o jedną kratkę do góry lub o jedną kratkę w prawo. Dodatkowo, niedozwolone jest przekraczanie przekątej AC.

Dozwolone są tylko ruchy do góry, czyli (x, y) → (x, y+1) lub w prawo, czyli (x, y) → (x+1, y). Natomiast niedozwolone jest przekroczenie przekątnej y = x, czyli jest sytuacja, w której y > x. Ruch do góry możemy oznaczyć jako U, ruch w prawo jako R.

Zauważmy, że drogi z A do C składają się zawsze z 5 ruchów do góry i 5 ruchów w prawo. Ponadto, droga na drugim obrazku stała się niepoprawna w czwartym ruchu, kiedy liczba ruchów w górę przekroczyła liczbę dotychczasowych ruchów w prawo.

Przeanalizujemy inny przykład niepoprawnej drogi na schemacie po lewej. Trzeci ruch jest niedozwolony. Po trzecim ruchu zamieniamy kierunku wszystkich następnych ruchów, początek zostawiamy bez zmian. Otrzymujemy schemat po prawej. Wówczas w nowej drodze mamy 4 ∙ R i 6 ∙ U oraz, co ciekawe, trafiamy do punktu (4, 6) na układzie współrzędnych.

Dla potwierdzenia, że nie jest to przypadek, te same kroki powtarzamy dla kolejnego przykładu niepoprawnej drogi.

To potwierdza, że punkt, w którym schodzimy na niepoprawną drogę, ma miejsce gdy pojawia się więcej ruchów do góry niż ruchów w prawo dotychczas. Bez znaczenia, w którym miejscu przekroczymy przekątną, w końcowym opisie drogi już po odwróceniu dalszej części jest o 2 więcej ruchów do góry niż w prawo.

Podsumowując, wszystkie możliwe sposoby przejścia z punktu A do punktu C wymagają 10 ruchów, wybieramy z nich 5 ruchów do góry. Natomiast w każdej niepoprawnej ścieżce, z 10 ruchów wybieramy 6 ruchów do góry. Odejmując od wszystkich możliwych dróg ilość niepoprawnych dróg, otrzymujemy ilosć wszystkich poprawnych dróg.

$${\displaystyle {10 \choose 5} - {10 \choose 6} = 42 \qquad}$$

To samo otrzymamy skupiając się na ruchach w prawo. Wszystkie możliwe sposoby przejścia z punktu A do punktu C wymagają 10 ruchów, wybieramy z nich 5 ruchów w prawo. Natomiast w każdej niepoprawnej ścieżce, z 10 ruchów wybieramy 4 ruchy w prawo.

$${\displaystyle {10 \choose 5} - {10 \choose 4} = 42 \qquad}$$

To prowadzi nas do wzoru na liczby Catalana

$${\displaystyle c_{n}={2n \choose n} - {2n \choose n+1}={2n \choose n} - {2n \choose n-1} = {\frac {(2n)!}{(n+1)!\,n!}} = {\frac {1}{n+1}}{2n \choose n}\qquad }$$

Z pierwszej zależności przy okazji widać, że liczby Catalana są liczbami naturalnymi.

Odpowiedź: W kwadracie o boku długości 5, istnieją 42 możliwe drogi z dolnego lewego wierzchołka do prawego górnego wierzchołka bez przekraczania przekątnej, która je łączy.

Przykład

Oblicz, ile jest możliwych dróg z wierzchołka A do wierzchołka C bez przekraczania łączącej je przekątnej w kwadracie o boku n = 3.

Zgodnie z wyprowadzonym wzorem obliczamy C3

$${\displaystyle c_{3} = {\frac {1}{3+1}} {2 \cdot 3 \choose 3} = 5 \qquad}$$

Możemy również zweryfikować obliczenia rysując wszystkie możliwe drogi

Odpowiedź: W kwadracie o boku długości 3, istnieje 5 możliwych dróg z dolnego lewego wierzchołka do prawego górnego wierzchołka bez przekraczania przekątnej, która je łączy.

II. Liczba podziałów na trójkąty

To problem rozważany przez Eulera. Dany jest wielokąt wypukły o n + 2 krawędziach. Liczba sposobów, na które można przy użyciu przekątnych podzielić go na różne trójkąty jest n-tą liczbą Catalana.

Przykład

Oblicz, na ile sposobów można podzielić ośmiokąt foremny na różne trójkąty za pomocą przekątnych.

Ośmiokąt foremny ma 8 krawędzi, zatem w tym przypadku n = 6. Należy zatem obliczyć szóstą liczbę Catalana.

$${\displaystyle c_{6}={\frac {1}{6+1}}{2 \cdot 6 \choose 6}= 132\qquad }$$

Odpowiedź: Istnieją 132 sposoby podziału ośmiokąta foremnego na różne trójkąty za pomocą jego przekątnych.

III. Liczba rozmieszczeń nawiasów

To problem rozważany przez Catalana. Liczba sposobów rozmieszczenia nawiasów w n-argumentowym działaniu jest równa Cn-1.

Przykład

Oblicz, ile różnych rozmieszczeń nawiasów w działaniu można otrzymać dla czterech argumentów a, b, c, d.

Odpowiedź: W czteroargumentowym działaniu nawiasy można rozmieścić na 5 sposobów.

IV. Liczba drzew binarnych

Drzewo binarne to taka struktura danych, w której liczba dzieci każdego z wierzchołków wynosi nie więcej niż 2, a wśród nich co najwyżej jedno jest lewym i co najwyżej jedno jest prawym dzieckiem. Liściem nazywamy węzeł, który nie ma żadnego dziecka. Drzewa binarne są szeroko wykorzystywane w informatyce.

Liczba różnych drzew binarnych o n węzłach wewnętrznych, czyli n + 1 liściach, jest równa n-tej liczbie Catalana.

Przykład

Oblicz, ile różnych drzew binarnych o trzech węzłach wewnętrznych (jednocześnie czterech liściach) można utworzyć.

Odpowiedź: Można utworzyć 5 takich drzew.

V. Liczba dróg

Rozważamy wszystkie możliwe łamane, które rozpoczynają się w początku kartezjańskiego układu współrzędnych (0, 0) a kończą się w punkcie (0, 2n) dla n ∈ ℕ. Łamane złożone są z pojedynczych odcinków o początku (x, y) i końcu w punkcie (x+1, y+1) lub (x-1, y+1), gdzie x, y ∈ ℕ.

Wówczas liczba tych łamanych, czyli możliwych dróg z (0, 0) do (0, 2n) jest równa n-tej liczbie Catalana.

Przykład

Podaj liczbę możliwych dróg od początku układu współrzędnych do punktu (0, 4). Możesz poruszać się jedynie o jedną kratkę w górę i w prawo lub o jedną kratkę w górę i w lewo, nie przekraczając osi OY.

Odpowiedź: Są dwie takie drogi.

Zadania dla Ciebie!

W tej części strony znajdują się zadania, które możesz rozwiązać samodzielnie w ramach sprawdzenia swojej wiedzy!
W razie problemów, kliknij przycisk wskazówka, aby otrzymać podpowiedź.
Jeśli zadanie dalej sprawia Ci problem, nie wahaj się wrócić do zakładek wprowadzenie i zastosowania, aby ponownie prześledzić podobne przykłady.

Zadanie 1

Ile jest możliwych dróg z dolnego lewego do górnego prawego wierzchołka kwadratu o obwodzie 40 cm, przy zastrzeżeniu, że nie można przekroczyć przekątnej łączącej wymienione wierzchołki? Możesz poruszać się jedynie 1 cm w górę lub 1 cm w prawo.

Zadanie 2

Jaką figurę można podzielić za pomocą jej przekątnych na trójkąty na 4862 sposoby?

Zadanie 3

Wiedząc, że x jest równy liczbie sposobów, na które można podzielić pięciokąt wypukły na różne trójkąty za pomocą nieprzecinających się przekątnych, a y jest równy czwartej liczbie Catalana, rozwiąż układ równań

$$\left\{\begin{array}{cc} a^{2} + (3 - a)ab + 4b^{2} = -b^{2} + y\\ b = 4b - ab - 5 + x\\ \end{array} \right.$$

Zadanie 4

Oblicz, na ile sposobów można rozmieścić nawiasy w działaniu zawierającym następujące argumenty: k, l, m, n, o, p.

Zadanie 5

Oblicz, ile jest możliwych dróg z początku układu współrzędnych do punktu (0, a), z czego a jest równe c4. Możesz poruszać się jedynie o jedną kratkę w górę i w prawo lub o jedną kratkę w górę i w lewo, nie przekraczając osi y = 0.

O stronie i autorce

Nazywam się Kinga Żmuda, jestem uczennicą klasy o profilu matematyczno-fizycznym w III LO im. Adama Mickiewicza w Katowicach, a tę stronę stworzyłam jako pracę na konkurs Zobaczyć Matematykę (edycja 2021/2022) organizowany przez Akademię Górniczo-Hutniczą im. Stanisława Staszica w Krakowie.

W mojej pracy podjęłam taki a nie inny temat przede wszystkim ze względu na szerokie zastosowanie liczb Catalana w kombinatoryce oraz sam fakt, że to zagadnienie bardzo mnie zainteresowało, a nie jest szeroko omawiane w szkole.

Za cel obrałam zebranie na niej informacji o sekwencji liczb Catalana nie tylko od strony czysto matematycznej i praktycznej, ale zadbałam też o umieszczenie informacji na temat ich historii, z którą rzadko spotykałam się w pracach na ich temat w języku polskim. Ułożyłam również dedykowany treści strony zestaw zadań do przećwiczenia dla użytkownika wraz z możliwością sprawdzenia odpowiedzi, a także umieściłam prosty program do obliczania n-tej liczby Catalana. Bardzo istotnym aspektem mojej pracy było również uczynienie wyglądu strony nowoczesnym i miłym dla oka oraz przyjemnym i intuicyjnym w użytkowaniu. Dlatego wszystkie niepodlikowane niżej obrazy to grafiki wykonane przeze mnie specjalnie na potrzeby tej witryny.

Research wykonany na potrzeby tego projektu przypomniał mi, jak niezwykle ciekawa potrafi być szerokopojęta matematyka, czego życzę również Tobie, Użytkowniku, Użytkowniczko. Tworzenie tej rozbudowanej strony, jej treści i oprawy graficznej z użyciem wielu narzędzi to dla mnie bardzo cenne doświadczenie na przyszłość, zarówno w zakresie czysto technicznym, jak i choćby rozplanowywania własnej pracy.

Owocnej nauki!

Użyte technologie i oprogramowanie niekomercyjne

  • HTML
  • CSS
  • JavaScript
  • jQuery
  • MathJax
  • Canva
  • GIMP

Źródła pomocne przy tworzeniu treści strony

Wykorzystane obrazy

Pozostałe grafiki umieszczone na stronie zostały wykonane przeze mnie.

Czcionka