Dyck Yolu Sayacı

Bu hesaplama hakkında

Dyck yolu, aynı yükseklikte başlayıp biten ve hiçbir zaman başlangıç seviyesinin altına inmeyen, "yukarı" ve "aşağı" adımlardan oluşan merdiven benzeri bir kafes yoludur — doğru dengelenmiş bir parantez dizisiyle eşdeğerdir, burada "yukarı" adım açma parantezi, "aşağı" adım kapama parantezidir. Bu hesaplayıcı, verilen bir yarı uzunluk n için (n yukarı adım ve n aşağı adım, toplam 2n adım) kaç farklı Dyck yolu bulunduğunu sayar; bu sayı n'inci Katalan sayısına, C(2n,n)/(n+1)'e eşittir.

Dyck yolları üzerinden Katalan sayıları, kombinatorik ve bilgisayar biliminde sürekli karşımıza çıkar: bir ifadedeki parantezleri doğru şekilde eşleştirmenin yollarını, n düğümlü farklı ikili arama ağaçlarının sayısını, dışbükey bir çokgeni üçgenlere ayırmanın yollarını ve bir yığın üzerindeki geçerli push/pop dizilerini sayarlar — bu yüzden aynı C(2n,n)/(n+1) formülü, ayrık matematik derslerinde birbiriyle ilgisiz görünen sayma problemlerinde tekrar tekrar karşımıza çıkar.