Catalan sayıları - Vikipedi
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,
formülüyle bulunur. Alternatif bir formül olan
- ’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 : alınır ve diğerleri için
uygulanır.
Hesaplamayı kolaylaştıran bir başka formül ise
- 'dir.
Örnekler
[değiştir | kaynağı değiştir]1. 3 çift parantez, bir cümle içinde kaç farklı şekilde bulunabilir?
Cevap olacak ve parantezler şu şekillerde kullanılabilecektir:
2. 3 düğümlü bir ikili ağaç, kaç farklı şekilde çizilebilir?
Cevap yine ’tir.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b4/Catalan_4_leaves_binary_tree_example.svg/650px-Catalan_4_leaves_binary_tree_example.svg.png)
3. 4x4’lük, karelere bölünmüş bir alanda, sol alt köşeden sağ üst köşeye kaç farklı şekilde çıkılabilir?
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f4/Catalan_number_4x4_grid_example.svg/450px-Catalan_number_4x4_grid_example.svg.png)
4. Bir altıgen, köşegenler yardımıyla oluşturulmuş üçgenlere kaç farklı şekilde ayrılabilir?
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Catalan-Hexagons-example.svg/400px-Catalan-Hexagons-example.svg.png)
5. 1’den 4’e kadar olan sayılar, sıralı bir üçlü oluşturmamak kaydıyla kaç farklı şekilde yan yana getirilebilir?
{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?
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/63/Catalan_stairsteps_4.svg/400px-Catalan_stairsteps_4.svg.png)
7. nxn boyutlu bir A matrisinde, her ise, o matrise Hankel matrisi denir ve determinant, boyuttan bağımsız olarak daima 1’dir.
Katalan sayılarının sayma problemlerindeki (Kombinatorik) uygulamaları
[değiştir | kaynağı değiştir]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.
;
- 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ı
[değiştir | kaynağı değiştir]1.İspat
[değiştir | kaynağı değiştir]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 , 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ı,
b de dengeli, yani eşit sayıda c ve c+ içeren, 2n uzunluğunda bir kelime ve olsun. Yukarıda olduğu gibi, dengeli bir kelime de [c]b ya da ] c+ [b olarak yazılabilir, öylseyse
Yanlış fakat dengeli olan bir kelime de c] ile başlar, dolayısıyla,
Bu eşitlikten ve Bi = di Ci ’den faydalanarak : elde edilir. Katsayılar Cn için verilen ilk formülle karşılaştırılınca di = i + 1 bulunur. O halde,
2.İspat
[değiştir | kaynağı değiştir]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 ;
- ’in binom formülü,: başlangıç koşulu ve bu bağıntı yoluyla doğrudan elde edilebilir.
Ayrıca bakınız
[değiştir | kaynağı değiştir]Dış bağlantılar
[değiştir | kaynağı değiştir]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.