Catalan sayıları sayfasının kaynağını görüntüle

'''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,

:<math>C_n = \frac{1}{n+1}{2n\choose n} = \frac{(2n)!}{(n+1)!\,n!}  \qquad n\ge 0  \mbox{ için}.</math>
formülüyle bulunur. 
Alternatif bir formül olan 
:<math>C_n = {2n\choose n} - {2n\choose n+1} \quad n\ge 0 \mbox{ için },</math>
:<math>C_n</math>’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 :<math>C_0=1</math> alınır ve diğerleri için 
:<math>\quad C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}\quad n\ge 0 \mbox{ için };</math>
uygulanır.

Hesaplamayı kolaylaştıran bir başka formül ise
:<math>\quad C_{n+1}=\frac{2(2n+1)}{n+2}C_n </math> 'dir.

== Örnekler ==

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

Cevap <math>C_3=5</math> olacak ve parantezler şu şekillerde kullanılabilecektir:

<div class="center"><big> ((())) &nbsp;&nbsp;&nbsp; ()(()) &nbsp;&nbsp;&nbsp; ()()() &nbsp;&nbsp;&nbsp; (())() &nbsp;&nbsp;&nbsp; (()()) </big></div>

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

Cevap yine <math>C_3=5</math> ’tir.

[[Dosya:Catalan number binary tree example.png|center]]

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

<math>C_4=14</math>

[[Dosya:Catalan number 4x4 grid example.svg|450px|center]]

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

<math>C_4=14</math>

[[Dosya:Catalan-Hexagons-example.svg|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?

<math>C_4=14</math>

{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?

<math>C_4=14</math>

[[Dosya:Catalan stairsteps 4.svg|400px|center]]

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

:<math>\det\begin{bmatrix}1 & 1 & 2 & 5 \\ 1 & 2 & 5 & 14 \\ 2 & 5 & 14 & 42 \\ 5 & 14 & 42 & 132\end{bmatrix} = 1.</math>

:<math>\det\begin{bmatrix}1 & 1 & 2 \\ 1 & 2 & 5 \\ 2 & 5 & 14 \end{bmatrix} = 1.</math>

=== 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.

<math>C_n</math> ;
* 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 tablosu]]nun 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 <math>C_n</math> , kurala uygun şekilde yazılmış kelimelerin sayısıdır. Bu kurala uygun, c ve c<sup>+</sup> ’lardan oluşan, (boş da olabilen) bir kelime oluşturur ve c’yi c=[c1]c2 şeklinde yazarsak, c<sup>+</sup> için uygun olan yerlerin toplamı,

:<math>C_0 = 1 \quad \text{ve} \quad C_{n+1} = \sum_{i=0}^n C_i\,C_{n-i}\quad n\ge 0.</math>

b de dengeli, yani eşit sayıda c ve c<sup>+</sup> içeren, 2n uzunluğunda bir kelime ve <math>\textstyle B_n = {2n\choose n} = d_n C_n</math> olsun.
Yukarıda olduğu gibi, dengeli bir kelime de [c]b ya da ] c<sup>+</sup> [b olarak yazılabilir, öylseyse
:<math>B_{n+1} = 2 \sum_{i=0}^n B_i C_{n-i}.</math>

Yanlış fakat dengeli olan bir kelime de c] ile başlar, dolayısıyla,
:<math>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}.</math>

Bu eşitlikten ve ''B''<sub>''i''</sub> = ''d''<sub>''i''</sub> ''C''<sub>''i''</sub> ’den faydalanarak :<math>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}.</math> elde edilir. Katsayılar ''C''<sub>''n''</sub> için verilen ilk formülle karşılaştırılınca ''d''<sub>''i''</sub> = ''i'' + 1 bulunur. O halde,
:<math>C_n = \frac{1}{n+1}{2n\choose n}.</math>

===2.İspat===	

Bu ispat da Katalan sayılarının [[üçgenleme]] tanımını kullanarak ''C<sub>n</sub>'' ve ''C''<sub>''n''+1</sub> 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<sub>n</sub>'' 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''<sub>''n''+1</sub> 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 ;
:<math>(4n+2)C_n = (n+2)C_{n+1}.</math>

:<math>C_n</math> ’in binom formülü,:<math>C_1=1</math> başlangıç koşulu ve bu bağıntı yoluyla doğrudan elde edilebilir.

== Dış bağlantılar ==

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]]