Liczby Catalana

Liczby Catalana – szczególny ciąg liczbowy, mający zastosowanie w różnych aspektach kombinatoryki. Nazwane zostały na cześć belgijskiego matematyka Eugène Charlesa Catalana (1814–1894)[1]. Bywają również nazywane liczbami Segnera, na cześć Jána Andreja Segnera (1704–1777), matematyka pochodzącego z Karpat Niemieckich.

Każdy n-ty wyraz ciągu określony jest wzorem jawnym: c n = 1 n + 1 ( 2 n n ) = ( 2 n ) ! ( n + 1 ) ! n !  dla  n 0. {\displaystyle c_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\mbox{ dla }}n\geqslant 0.}

Rekurencyjnie ciąg jest określony w następujący sposób: c 0 = 1 ; c n = c 0 c n 1 + c 1 c n 2 + + c n 2 c 1 + c n 1 c 0 = i = 0 n 1 c i c n 1 i . {\displaystyle c_{0}=1;c_{n}=c_{0}\cdot c_{n-1}+c_{1}\cdot c_{n-2}+\ldots +c_{n-2}\cdot c_{1}+c_{n-1}\cdot c_{0}=\sum _{i=0}^{n-1}c_{i}\cdot c_{n-1-i}.}

Początkowe wartości ciągu, poczynając od wyrazu zerowego, to:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452,...

Własności

Liczby Catalana spełniają zależność:

C n = ( 2 n n ) ( 2 n n + 1 )  dla  n 1. {\displaystyle C_{n}={2n \choose n}-{2n \choose n+1}\quad {\mbox{ dla }}n\geqslant 1.}

W sposób oczywisty pokazuje to, iż każda liczba Catalana jest liczbą naturalną. Inną postacią wzoru rekurencyjnego (tym razem pierwszego stopnia) jest:

C 0 = 1 i C n + 1 = 2 ( 2 n + 1 ) n + 2 C n , {\displaystyle C_{0}=1\quad {\mbox{i}}\quad C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n},}

Przybliżenie wartości n {\displaystyle n} -tej liczby Catalana jest możliwe dzięki wzorowi Stirlinga na wartość silni i ma postać:

C n 4 n n 3 2 π {\displaystyle C_{n}\approx {\frac {4^{n}}{n^{\frac {3}{2}}{\sqrt {\pi }}}}}

Znaczenia kombinatoryczne

Liczby Catalana posiadają wiele różnych interpretacji kombinatorycznych. Podane niżej stanowią jedynie przykłady zastosowań:

Liczba dróg

Jeżeli rozważymy wszystkie łamane, zaczynające się w początku kartezjańskiego układu współrzędnych i kończące w ( 0 , 2 n ) {\displaystyle (0,2n)} dla każdego n = 0 , 1 , 2 , , {\displaystyle n=0,1,2,\dots ,} położone w jego I ćwiartce i złożone z pojedynczych odcinków o początku ( x , y ) {\displaystyle (x,y)} i końcu w punkcie ( x + 1 , y + 1 ) {\displaystyle (x+1,y+1)} lub ( x 1 , y + 1 ) {\displaystyle (x-1,y+1)} (gdzie x , y N {\displaystyle x,y\in \mathbb {N} } ), to ich liczba będzie wyrażona n {\displaystyle n} -tą liczba Catalana.

Liczba rozmieszczeń nawiasów

Poprzez {\displaystyle \star } rozumiemy pewne działanie dwuargumentowe. Dla n {\displaystyle n} -argumentów liczba c n 1 {\displaystyle c_{n-1}} wyraża liczbę sposobów, na które można rozmieścić nawiasy w takim wyrażeniu, czyli – dla działania niełącznego – maksymalną liczbę wyników, które można uzyskać. Przykładowo, dla trzech argumentów x 1 , x 2 , x 3 {\displaystyle x_{1},x_{2},x_{3}} otrzymać można ( x 1 x 2 ) x 3 {\displaystyle (x_{1}\star x_{2})\star x_{3}} lub x 1 ( x 2 x 3 ) , {\displaystyle x_{1}\star (x_{2}\star x_{3}),} co odpowiada c 3 1 = c 2 = 2. {\displaystyle c_{3-1}=c_{2}=2.}

Liczba drzew binarnych

c n {\displaystyle c_{n}} jest równa liczbie różnych ukorzenionych regularnych drzew binarnych o n + 1 {\displaystyle n+1} liściach.

Liczba monotonicznych dróg

Jeżeli rozpatrzymy wszystkie możliwe drogi w kwadracie n × n {\displaystyle n\times n} z dolnego lewego wierzchołka do górnego prawego, tak, by nigdy nie przekroczyć przekątnej łączącej te wierzchołki i były monotoniczne, łatwo jest zauważyć, że wyrażają się one n {\displaystyle n} -tą liczbą Catalana. Odpowiada to liczbie monotonicznych funkcji f {\displaystyle f} z 1 , 2 , , n {\displaystyle 1,2,\dots ,n} w 1 , 2 , , n {\displaystyle 1,2,\dots ,n} takich, by k f ( k ) , k 1 , 2 , , n {\displaystyle k\geqslant f(k),k\in {1,2,\dots ,n}}

Liczba podziałów na trójkąty

Liczba c n {\displaystyle c_{n}} wyraża liczbę sposobów podziału wielokąta wypukłego, mającego n + 2 {\displaystyle n+2} krawędzie, na różne trójkąty przy pomocy nieprzecinających się wewnątrz wielokąta przekątnych (zob. triangulacja).

Dowód wzoru jawnego

Dowód wzoru c n = 1 n + 1 ( 2 n n ) = ( 2 n ) ! ( n + 1 ) ! n !  dla  n 0. {\displaystyle c_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\mbox{ dla }}n\geqslant 0.} można otrzymać na wiele sposobów i zależnie od różnych interpretacji liczb Catalana. Przyjmując, że rozpatrujemy przypadek liczby dróg z punktu ( 0 , 0 ) {\displaystyle (0,0)} do ( 0 , 2 n ) {\displaystyle (0,2n)} i przy założeniu c 0 = 1 {\displaystyle c_{0}=1} otrzymamy:

c 1 = 1 {\displaystyle c_{1}=1} – bowiem do punktu ( 0 , 2 ) {\displaystyle (0,2)} prowadzi jedna tylko droga,
c 2 = 2 = c 0 c 1 + c 1 c 0 {\displaystyle c_{2}=2=c_{0}\cdot c_{1}+c_{1}\cdot c_{0}} – ponieważ do punktu ( 0 , 2 ) {\displaystyle (0,2)} prowadzi jedna droga c 1 , {\displaystyle c_{1},} zaś z tego punktu do ( 0 , 4 ) {\displaystyle (0,4)} można przejść zgodnie z założonymi możliwościami wyboru kolejnego odcinka składowego na jeden sposób.

Rozważmy teraz pewne przesunięcie układu współrzędnych tak, by punkt ( 1 , 1 ) {\displaystyle (1,1)} stał się środkiem nowego układu współrzędnych – wówczas do punktu ( 1 , 3 ) {\displaystyle (1,3)} prowadzi tyle samo dróg, co z punktu ( 0 , 0 ) {\displaystyle (0,0)} do ( 0 , 2 ) , {\displaystyle (0,2),} zaś z ( 1 , 3 ) {\displaystyle (1,3)} wykonując ruch zgodnie z założeniami można przejść na jeden sposób do punktu ( 0 , 4 ) . {\displaystyle (0,4).}

Postępując dalej analogicznie, otrzymamy:

{ c 3 = c 0 c 2 + c 1 c 1 + c 2 c 0 c n = c 0 c n 1 + c 1 c n 2 + + c n 2 c 1 + c n 1 c 0 = i = 0 n 1 C i C n 1 i . {\displaystyle {\begin{cases}c_{3}=c_{0}\cdot c_{2}+c_{1}\cdot c_{1}+c_{2}\cdot c_{0}\\\vdots \\c_{n}=c_{0}\cdot c_{n-1}+c_{1}\cdot c_{n-2}+\ldots +c_{n-2}\cdot c_{1}+c_{n-1}\cdot c_{0}=\sum _{i=0}^{n-1}\;C_{i}\,C_{n-1-i}\end{cases}}.}

Aby otrzymać wzór jawny, którym określony jest ciąg, można użyć techniki funkcji tworzących ciągu.

Niech C ( x ) = c 0 + c 1 x + c 2 x 2 + {\displaystyle C(x)=c_{0}+c_{1}\cdot x+c_{2}\cdot x^{2}+\ldots } będzie funkcją tworzącą tego ciągu. Wówczas:

C ( x ) = c 0 + c 1 x + c 2 x 2 + = 1 + x [ c 1 + c 2 x + c 3 x 2 + ] = 1 + x [ c 0 c 0 + ( c 0 c 1 + c 1 c 0 ) x + ( c 0 c 2 + c 1 c 1 + c 2 c 0 ) x 2 + ] = 1 + x C ( x ) C ( x ) = 1 + x C ( x ) 2 , {\displaystyle {\begin{aligned}C(x)&=c_{0}+c_{1}\cdot x+c_{2}\cdot x^{2}+\ldots \\&=1+x\left[c_{1}+c_{2}\cdot x+c_{3}\cdot x^{2}+\dots \right]\\&=1+x\left[c_{0}\cdot c_{0}+(c_{0}\cdot c_{1}+c_{1}\cdot c_{0})x+(c_{0}\cdot c_{2}+c_{1}\cdot c_{1}+c_{2}\cdot c_{0})x^{2}+\ldots \right]\\&=1+x\cdot C(x)\cdot C(x)\\&=1+x\cdot C(x)^{2},\end{aligned}}}

co wynika z definicji operacji mnożenia funkcji tworzących. Mamy więc

C ( x ) = 1 + x C ( x ) 2 , {\displaystyle C(x)=1+x\cdot C(x)^{2},}
x C ( x ) 2 C ( x ) + 1 = 0. {\displaystyle x\cdot C(x)^{2}-C(x)+1=0.}

Rozwiązując to równanie, po przyjęciu za szukaną zmienną C ( x ) {\displaystyle C(x)} otrzymujemy:

c ( x ) = 1 ± 1 4 x 2 x . {\displaystyle c(x)={\frac {1\pm {\sqrt {1-4x}}}{2x}}.}

Ponieważ

lim x 0 1 + 1 4 x 2 x = , lim x 0 1 1 4 x 2 x = c 0 = 1 , {\displaystyle \lim _{x\to 0}\;{\frac {1+{\sqrt {1-4x}}}{2x}}=\infty ,\quad \lim _{x\to 0}\;{\frac {1-{\sqrt {1-4x}}}{2x}}=c_{0}=1,}

to rozpatrujemy jedynie pierwiastek c ( x ) = 1 1 4 x 2 x . {\displaystyle c(x)={\frac {1-{\sqrt {1-4x}}}{2x}}.}

Korzystając z uogólnionego na liczby rzeczywiste symbolu Newtona oraz jego własności okazuje się, że

c ( x ) = 1 1 4 x 2 x = 1 n = 0 ( 1 2 n ) ( 4 x ) n 2 x = 1 1 n = 1 ( 1 2 n ) ( 4 x ) n 2 x = n = 1 ( 1 2 n ) ( 4 x ) n ( 2 x ) 1 = n = 1 1 2 ( 1 2 n ) 4 n x n 1 ( 1 ) n 1 {\displaystyle {\begin{aligned}c(x)&={\frac {1-{\sqrt {1-4x}}}{2x}}\\&={\frac {1-\sum _{n=0}^{\infty }{{\tfrac {1}{2}} \choose n}(-4x)^{n}}{2x}}\\&={\frac {1-1-\sum _{n=1}^{\infty }{{\tfrac {1}{2}} \choose n}(-4x)^{n}}{2x}}\\&=-\sum _{n=1}^{\infty }{{\tfrac {1}{2}} \choose n}(-4x)^{n}(2x)^{-1}\\&=\sum _{n=1}^{\infty }{\tfrac {1}{2}}{{\tfrac {1}{2}} \choose n}4^{n}x^{n-1}(-1)^{n-1}\end{aligned}}}

Po zmianie granic sumowania otrzymujemy

n = 0 1 2 ( 1 2 n + 1 ) 4 n + 1 ( 1 ) n x n . {\displaystyle \sum _{n=0}^{\infty }{\frac {1}{2}}{{\tfrac {1}{2}} \choose n+1}4^{n+1}(-1)^{n}x^{n}.}

Z własności funkcji tworzących wiemy, że n {\displaystyle n} -ty wyraz ciągu jest równy współczynnikowi przy n {\displaystyle n} -tej potędze x , {\displaystyle x,} czyli;

c n = 1 2 ( 1 2 n + 1 ) 4 n + 1 ( 1 ) n = 4 1 2 1 2 ( 1 2 1 ) ( 1 2 2 ) ( 1 2 n ) ( n + 1 ) ! ( 1 ) n 4 n = 1 n + 1 ( 1 1 2 ) ( 2 1 2 ) ( n 1 2 ) n ! 2 n 2 n = 1 n + 1 1 3 ( 2 n 1 ) n ! n ! n ! 2 n = 1 n + 1 1 3 ( 2 n 1 ) 2 4 6 2 n n ! n ! = 1 n + 1 ( 2 n ) ! n ! n ! = 1 n + 1 ( 2 n n ) {\displaystyle {\begin{aligned}c_{n}&={\frac {1}{2}}{{\tfrac {1}{2}} \choose n+1}4^{n+1}(-1)^{n}\\&=4\cdot {\frac {1}{2}}{\frac {{\tfrac {1}{2}}({\tfrac {1}{2}}-1)({\tfrac {1}{2}}-2)\ldots ({\tfrac {1}{2}}-n)}{(n+1)!}}(-1)^{n}4^{n}\\&={\frac {1}{n+1}}{\frac {(1-{\tfrac {1}{2}})(2-{\tfrac {1}{2}})\ldots (n-{\tfrac {1}{2}})}{n!}}2^{n}2^{n}\\&={\frac {1}{n+1}}{\frac {1\cdot 3\cdot \ldots \cdot (2n-1)\cdot n!}{n!n!}}2^{n}\\&={\frac {1}{n+1}}{\frac {1\cdot 3\cdot \ldots \cdot (2n-1)\cdot 2\cdot 4\cdot 6\cdot \ldots \cdot 2n}{n!n!}}\\&={\frac {1}{n+1}}{\frac {(2n)!}{n!n!}}\\&={\frac {1}{n+1}}{2n \choose n}\end{aligned}}}

Historia

Liczby te zostały po raz pierwszy wprowadzone przez Leonarda Eulera w XVIII wieku, który badał liczbę podziałów wielokątów na trójkąty. Zostały nazwane na cześć Eugène Charlesa Catalana, który rozważał je jako liczbę sposobów rozmieszczeń nawiasów[potrzebny przypis].

Przypisy

  1. Ronald Graham, Donald Knuth, Oren Patashnik: Matematyka konkretna. Warszawa: PWN, 2006, s. 233.

Linki zewnętrzne

  • (pol.) Liczby Catalana w skrypcie z matematyki dyskretnej
  • Eric W.E.W. Weisstein Eric W.E.W., Catalan Number, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).
  • (ang.) Stanley, R.P – dodatek do książki Enumerative Combinatorics, poświęcony liczbom Catalana
Kontrola autorytatywna (liczba całkowita dodatnia):
  • LCCN: sh2008005833
  • GND: 1072323532
  • BNCF: 61477
  • NKC: ph1202458
  • J9U: 987007561759805171