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, :C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!} \qquad n\ge 0 \mbox{ için}. formülüyle bulunur. Alternatif bir formül olan :C_n = {2n\choose n} - {2n\choose n+1} \quad n\ge 0 \mbox{ için }, :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 :C_0=1 alınır ve diğerleri için :\quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad n\ge 0 \mbox{ için }; uygulanır. Hesaplamayı kolaylaştıran bir başka formül ise :\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 C_3=5 olacak ve parantezler şu şekillerde kullanılabilecektir: ((())) ()(()) ()()() (())() (()()) 2\. 3 düğümlü bir ikili ağaç, kaç farklı şekilde çizilebilir? Cevap yine C_3=5 ’tir. orta 3\. 4x4’lük, karelere bölünmüş bir alanda, sol alt köşeden sağ üst köşeye kaç farklı şekilde çıkılabilir? C_4=14 450px|center 4\. Bir altıgen, köşegenler yardımıyla oluşturulmuş üçgenlere kaç farklı şekilde ayrılabilir? C_4=14 400px|center 5\. 1’den 4’e kadar olan sayılar, sıralı bir üçlü oluşturmamak kaydıyla kaç farklı şekilde yan yana getirilebilir? 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? C_4=14 400px|center 7\. nxn boyutlu bir A matrisinde, her a_{ij}=C_{i+j-2} ise, o matrise Hankel matrisi denir ve determinant, boyuttan bağımsız olarak daima 1’dir. :\det\begin{bmatrix}1 & 1 & 2 & 5 \\\ 1 & 2 & 5 & 14 \\\ 2 & 5 & 14 & 42 \\\ 5 & 14 & 42 & 132\end{bmatrix} = 1. :\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. 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 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ı, :C_0 = 1 \quad \text{ve} \quad C_{n+1} = \sum_{i=0}^n C_i\,C_{n-i}\quad n\ge 0. b de dengeli, yani eşit sayıda c ve c+ içeren, 2n uzunluğunda bir kelime ve \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 :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, :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 Bi = di Ci ’den faydalanarak :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 Cn için verilen ilk formülle karşılaştırılınca di = i + 1 bulunur. O halde, :C_n = \frac{1}{n+1}{2n\choose n}. ===2.İspat=== Bu ispat da Katalan sayılarının üçgenleme tanımını kullanarak Cn ve Cn+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) Cn 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) Cn+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 ; :(4n+2)C_n = (n+2)C_{n+1}. :C_n ’in binom formülü,:C_1=1 başlangıç koşulu ve bu bağıntı yoluyla doğrudan elde edilebilir. == Ayrıca bakınız == * Catalan problemi == 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 http://www.math.utah.edu/mathcircle/notes/mladen2.pdf http://en.wikipedia.org/wiki/Catalan_number Kategori:Tamsayı dizileri