Kafes Yolu Sayacı Hesaplayıcı

Bu hesaplama hakkında

m × n boyutundaki bir ızgara üzerindeki monoton kafes yolu, ızgara çizgileri boyunca yalnızca sağa veya yukarı hareket ederek (asla sola veya aşağı gitmeden) bir köşeden karşı köşeye giden bir rotadır. Bu tür yolların sayısı klasik bir kombinatorik sonucudur: herhangi bir yol tam olarak m sağa ve n yukarı hareketten oluştuğundan, toplam sayı binom katsayısı C(m+n, m)'e eşittir — toplam m+n hareketten hangi m tanesinin “sağa” hareketi olacağını seçmenin yol sayısı.

Bu, kombinatorik ve ayrık matematik derslerinde öğretilen ilk önemsiz olmayan sonuçlardan biridir ve Pascal üçgeni, binom katsayıları ile bir köşegeni aşmaması gereken yollar gibi daha ileri sayma problemlerini çözmek için kullanılan yansıma ilkesiyle (Catalan sayılarının temeli) doğrudan bağlantılıdır. Bilgisayar bilimi öğrencileri, ağırlıklı veya engel kaçınmalı yol saymaya geçmeden önce standart bir ısınma alıştırması olan dinamik programlama ızgara problemlerinde aynı yapıyla karşılaşır.