Katalanca sayılar nerede bulunur?
-Belirli sayıda parantez çiftine sahip psp sayısı
-Belirli sayıda yapraklı ikili ağaç sayısı
-n * n karede sol alt köşeden sağ üst köşeye giden ve köşegene değmeyen yolların sayısı
-n-gon'un üçgenlere bölünme sayısı
Nasıl sayılır?1) n'inci Katalan sayının formülü:
2)
•2n uzunluğunda bir PSS yapalım
•Tabii ki bir açılış ayracı ile başlıyor
•P = (A)B diyelim, burada A ve B – ayrıca psp (ayrıca A ve B boş olabilir)
•A'nın uzunluğu = 2k ise, A dizisi Ck yollarıyla oluşturulabilir
•O halde B = 2(n – k - 1) ve B'nin uzunluğu Cn-k-1 şeklinde yazılabilir
•dp için formülü görüyoruz: Cn = toplam(Ck * Cn-k-1) tüm k <
Kullanılan malzemeler: