HesapHanem

Dyck Yolu Sayacı

O boyuttaki Dyck yollarını saymak için bir yarı uzunluk n girin.

Sonuç

14 yol
8 adım
n = 4

Nasıl hesaplanır?

Yarı uzunluğu n olan Dyck yollarının sayısı Katalan sayısıdır: C(n) = (2n)! / (n! × (n+1)!), yani C(2n, n) / (n+1). Araç büyük faktöriyeller yerine bunu adım adım, C(0) = 1 ve C(k) = C(k−1) × 2(2k−1) / (k+1) bağıntısıyla ve tam sayı aritmetiğiyle kurar. Yarı uzunluğu n olan bir yolda n yukarı ve n aşağı adım vardır, yani toplam 2n adım; araç bunu da gösterir. Yalnızca 0 ile 30 arasındaki tam sayılar kabul edilir: C(30) = 3.814.986.502.092.304 hâlâ tam hesaplanır, daha büyük değerler hesaplanmaz; ondalık, negatif ya da boş girdi sonuç vermez. Araç girdiğiniz n değerini de gösterir.

Örnek hesaplama

n = 4 alalım: dört yukarı, dört aşağı adım; toplam 8 adım. C(0) = 1'den başlıyoruz. Sonra C(1) = 1 × 2 × 1 / 2 = 1, C(2) = 1 × 2 × 3 / 3 = 2, C(3) = 2 × 2 × 5 / 4 = 5 ve C(4) = 5 × 2 × 7 / 5 = 14 bulunur. Araç 14 yol ve 8 adım gösterir; bu, C(8, 4) / 5 = 70 / 5 = 14 ile uyuşur. Bu 14 yol, dört çift parantezi doğru yazmanın tam olarak 14 yoludur.

Bu örneği dene →

Sık yapılan hatalar

  • Yarı uzunluk (4) yerine toplam adım sayısını (8) girmek. Araç n'yi, yani yukarı adım sayısını bekler ve uzunluk için ikiyle çarpar.
  • Dyck yollarını tüm yukarı/aşağı yollarla karıştırmak. Yolun başlangıç seviyesinin altına inmeme kuralı olmasa C(2n, n) yol olurdu; n = 4 için bu 70'tir, 14 değil.
  • 2,5 gibi ondalık ya da negatif bir n girmek. Yalnızca 0 ve üzeri tam sayılar geçerlidir, diğerleri sonuç vermez.
  • 30'dan büyük bir n girip çok büyük bir sayı beklemek. Sayımı tam tutmak için araç 30'da durur; daha büyük n için büyük tam sayı destekleyen bir araç gerekir.
  • n = 0 için sonucun sıfır olacağını sanmak. Tek bir boş yol vardır, dolayısıyla n = 0 için sayı 1'dir (0 adımla).

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.

Bu faydalı oldu mu?

En fazla 3 tepki seçebilirsiniz.

Yorumlar

  • İlk yorumu siz yazın.

Popüler hesaplayıcılar

Kredi Hesaplama

Aylık taksit, toplam faiz ve ödeme planını hesaplayın.

Yüzde Hesaplama

Yüzde değişim, indirim ve oran hesaplamaları.

İndirim Hesaplama

İndirimli fiyatı, kazancı ve indirim tutarını hesaplayın.

Vücut Kitle Endeksi (VKİ)

Boy ve kiloya göre vücut kitle endeksini hesaplayın.

Yaş Hesaplama

Doğum tarihinden bugüne tam yıl, ay ve gün cinsinden yaşınızı hesaplayın.

Bileşik Faiz Hesaplama

Ana para, faiz oranı ve süreye göre bileşik faizle nihai tutarı hesaplayın.

Tüm Hesaplayıcılar