Catalan sayıları

Katalan sayıları, kombinatorik matematikte birçok problemin çözümünde kullanılabilen özel bir sayı dizisi. Adını Belçikalı matematikçi Eugène Charles Catalan(1814-1894)’dan alan bu dizinin terimleri,

${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad n\geq 0{\mbox{ için}}.}$

formülüyle bulunur. Alternatif bir formül olan

${\displaystyle C_{n}={2n \choose n}-{2n \choose n+1}\quad n\geq 0{\mbox{ için }},}$

${\displaystyle C_{n}}$’in bir doğal sayı olduğunu bir önceki formülden daha açık bir şekilde gösterir.

Katalan sayılarının her biri, kendinden önceki terimlere bağlıdır. Yani :${\displaystyle C_{0}=1}$ alınır ve diğerleri için

${\displaystyle \quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad n\geq 0{\mbox{ için }};}$

uygulanır.

Hesaplamayı kolaylaştıran bir başka formül ise

${\displaystyle \quad C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n}}$ 'dir.

Örnekler

1. 3 çift parantez, bir cümle içinde kaç farklı şekilde bulunabilir?

Cevap ${\displaystyle C_{3}=5}$ olacak ve parantezler şu şekillerde kullanılabilecektir:

((()))     ()(())     ()()()     (())()     (()())

2. 3 dallı bir ikili ağaç, kaç farklı şekilde çizilebilir?

Cevap yine ${\displaystyle C_{3}=5}$ ’tir.

3. 4x4’lük, karelere bölünmüş bir alanda, sol alt köşeden sağ üst köşeye kaç farklı şekilde çıkılabilir?

${\displaystyle C_{4}=14}$

4. Bir altıgen, köşegenler yardımıyla oluşturulmuş üçgenlere kaç farklı şekilde ayrılabilir?

${\displaystyle C_{4}=14}$

5. 1’den 4’e kadar olan sayılar, sıralı bir üçlü oluşturmamak kaydıyla kaç farklı şekilde yan yana getirilebilir?

${\displaystyle C_{4}=14}$

{1432, 2143, 2413, 2431, 3142, 3214, 3241, 3412, 3421, 4132, 4213, 4231, 4312,4321}

6. 4 basamaklı bir merdiven, 4 karoyla kaç farklı şekilde kaplanabilir?

${\displaystyle C_{4}=14}$

7. nxn boyutlu bir A matrisinde, her ${\displaystyle a_{ij}=C_{i+j-2}}$ ise, o matrise Hankel matrisi denir ve determinant, boyuttan bağımsız olarak daima 1’dir.

${\displaystyle \det {\begin{bmatrix}1&1&2&5\\1&2&5&14\\2&5&14&42\\5&14&42&132\end{bmatrix}}=1.}$

${\displaystyle \det {\begin{bmatrix}1&1&2\\1&2&5\\2&5&14\end{bmatrix}}=1.}$

Katalan sayılarının sayma problemlerindeki (Kombinatorik) uygulamaları

Bu dizinin terimleri, kombinatorik matematiğin problemlerini çözmede fayda sağlar. Yukarıda gördüğümüz örnekler bunlardan bazılarıdır. Farklı başlangıç değerleri için problemin cevabı, başlangıç değerini n yerine yazarak elde edilen Katalan sayısına eşit olur.

${\displaystyle C_{n}}$ ;

• n çift parantezin kaç farklı şekilde düzgün konumlanabileceğini, (düzgün konumlanmakla kastedilen, açılan her parantezin kapanması ve bir parantez açılmadan kapatma parantezi konmamasıdır.)
• n+1 dallı bir ikili ağacın kaç farklı şekilde oluşturulabileceğini,
• nxn karelik bir alanda, diagonalin üzerine çıkmayacak şekilde, sol alt köşeden sağ üst köşeye kaç farklı şekilde ulaşılabileceğini,
• n+2 kenarlı bir konveks çokgenin, köşegenler aracılığıyla kaç üçgene bölünebileceğini,
• 1’den n’e kadar olan sayıların, sıralı üçlü oluşturmamak koşuluyla kaç farklı şekilde dizilebileceğini,
• n basamaklı bir merdivenin, n tane karoyla kaç farklı şekilde kaplanabileceğini,
• {1,…,n} kümesinin kesişmeyen kısımlarının sayısını,
• 2xn boyutlu bir standart Young tablosunun kaç farklı şekilde oluşturulabileceğini,

Ve bunlara benzer sayma problemlerinin nasıl çözülebileceğini gösterir.,

Formülün İspatları

1.İspat

Bu ispat, Dyck kelimelerinin(baştan sona doğru nereden bölünürse bölünsün, X’lerin sayısının Y’lerden az olmadığı, X ve Y’den oluşan kelimeler) yazılışına dayanır. Bu durumda ${\displaystyle C_{n}}$ , kurala uygun şekilde yazılmış kelimelerin sayısıdır. Bu kurala uygun, c ve c⁺ ’lardan oluşan, (boş da olabilen) bir kelime oluşturur ve c’yi c=[c1]c2 şeklinde yazarsak, c⁺ için uygun olan yerlerin toplamı,

${\displaystyle C_{0}=1\quad {\text{ve}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad n\geq 0.}$

b de dengeli, yani eşit sayıda c ve c⁺ içeren, 2n uzunluğunda bir kelime ve ${\displaystyle \textstyle B_{n}={2n \choose n}=d_{n}C_{n}}$ olsun. Yukarıda olduğu gibi, dengeli bir kelime de [c]b ya da ] c⁺ [b olarak yazılabilir, öylseyse

${\displaystyle B_{n+1}=2\sum _{i=0}^{n}B_{i}C_{n-i}.}$

Yanlış fakat dengeli olan bir kelime de c] ile başlar, dolayısıyla,

${\displaystyle B_{n+1}-C_{n+1}=\sum _{i=0}^{n}{2i+1 \choose i}C_{n-i}=\sum _{i=0}^{n}{\frac {2i+1}{i+1}}B_{i}C_{n-i}.}$

Bu eşitlikten ve B_i = d_i C_i ’den faydalanarak :${\displaystyle C_{n+1}=2\sum _{i=0}^{n}d_{i}C_{i}C_{n-i}-\sum _{i=0}^{n}{\frac {2i+1}{i+1}}d_{i}C_{i}C_{n-i}=\sum _{i=0}^{n}{\frac {d_{i}}{i+1}}C_{i}C_{n-i}.}$ elde edilir. Katsayılar C_n için verilen ilk formülle karşılaştırılınca d_i = i + 1 bulunur. O halde,

${\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}.}$

2.İspat

Bu ispat da Katalan sayılarının üçgenleme tanımını kullanarak C_n ve C_n+1 arasında bir bağıntı kurmamızı sağlar. n+2 kenarlı bir P çokgeninin bir kenarını temel olarak alalım. P çokgeni üçgenlenebiliyorsa 2n+1 kenarından birini seçip devam edebiliriz. Bu şekilde oluşturulabilecek (4n+2) C_n farklı durum vardır. Bir de n+3 kenarlı bir Q çokgeni verilsin. Yine bir kenarını temel aldığımızda, Q üçgenlenebilir bir çokgense, ilkinden farklı bir kenar daha seçebiliriz. Bu kez oluşturabileceğimiz (n+2) C_n+1 farklı durum vardır. Şimdi bu ikisi arasında bir geçiş yapabiliriz: ya Q çokgenini, bir kenarı işaretli olan bir üçgenini çıkararak küçülteceğiz ya da P’nin işaretli kenarının yerine bir üçgen koyarak P’yi genişletip bir kenarını işaretleyeceğiz. Öyleyse ;

${\displaystyle (4n+2)C_{n}=(n+2)C_{n+1}.}$

${\displaystyle C_{n}}$ ’in binom formülü,:${\displaystyle C_{1}=1}$ başlangıç koşulu ve bu bağıntı yoluyla doğrudan elde edilebilir.

Dış bağlantılar

https://web.archive.org/web/20040808170406/http://www.math.harvard.edu/~mantovan/ADMIN/catalan2.pdf

http://www.geometer.org/mathcircles/catalan.pdf 17 Eylül 2011 tarihinde Wayback Machine sitesinde arşivlendi.

http://www.math.utah.edu/mathcircle/notes/mladen2.pdf 7 Haziran 2011 tarihinde Wayback Machine sitesinde arşivlendi.

http://en.wikipedia.org/wiki/Catalan_number 6 Ekim 2011 tarihinde Wayback Machine sitesinde arşivlendi.