Nombor Catalan


Di manakah nombor Catalan berlaku?
 
-Bilangan psp dengan bilangan pasangan kurungan yang diberikan
-Bilangan pokok binari dengan bilangan daun yang diberikan
-Bilangan laluan dari sudut kiri bawah ke sudut kanan atas dalam petak n * n yang tidak menyentuh pepenjuru

-Bilangan pembahagian n-gon kepada segi tiga



Bagaimana untuk mengira?
 
1) Formula untuk nombor Catalan ke-n:



2)
•Mari kita mempunyai PSS panjang 2n
•Jelas sekali ia bermula dengan pendakap buka
•Jadi, katakan P = (A)B, di mana A dan B – juga psp (lebih-lebih lagi, A dan B boleh kosong)
•Jika panjang A = 2k, maka urutan A boleh digubah dalam cara Ck
•Kemudian panjang B = 2(n – k - 1) dan B boleh digubah dalam cara Cn-k-1

Training problem

Bilangan nombor Catalan