Konu anlatımı
Eş karelerden oluşan bir sokak planında yalnızca sağa ve yukarı gidilerek bir köşeden ötekine ulaşmanın yollarını saymayı TYT'den biliyorsun. Bu alt başlıkta zorunlu noktaları, yasak noktaları, kapalı yol parçalarını ve formülün işlemediği planlarda adım adım saymayı göreceksin.
Temel sayım
Bir en kısa yol m kez sağa, n kez yukarı gidiyorsa bu yol m tane S ve n tane Y harfinden oluşan bir dizidir; yol sayısı (m + n)!/(m!·n!) = C(m + n, n) olur. 3 sağ ve 2 yukarı adım için 10 yol vardır. Noktaları koordinatla düşünmek kolaylık sağlar: A(0, 0) noktasından B(5, 4) noktasına 5 sağ ve 4 yukarı adımla gidilir ve C(9, 4) = 126 yol vardır.
Zorunlu ve yasak noktalar
Bir P noktasından geçen yollar iki parçaya ayrılır: A'dan P'ye ve P'den B'ye. Parçalar birbirinden bağımsız seçildiği için yol sayıları çarpılır. İki zorunlu nokta varsa üç parçanın sayıları çarpılır; noktaların sırası, biri ötekinin sağında ve yukarısında olacak biçimde uygun olmalıdır. Bir noktadan geçmeyen yollar tümleyenle bulunur: bütün yollardan o noktadan geçenler çıkarılır.
Kapalı yol parçası
İki komşu köşe arasındaki bir sokak kapalıysa o sokağı kullanan yollar sayılıp çıkarılır. Sokağı kullanan bir yol, sokağın başlangıç köşesine kadar gelir, sokağı geçer ve bitiş köşesinden hedefe gider; baştaki ve sondaki parçaların yol sayıları çarpılır. Kapalı sokak ile yasak nokta aynı şey değildir: sokağın iki ucundaki köşelerden başka yönlere geçmek serbesttir.
Köşelere sayı yazarak saymak
Plan düzgün bir dikdörtgen değilse ya da birkaç kapalı sokak varsa her köşeye, başlangıçtan o köşeye gelen yol sayısı yazılır. Başlangıç köşesine 1 yazılır; bir köşenin sayısı, solundaki ve altındaki köşelerin sayılarının toplamıdır, çünkü o köşeye yalnızca bu iki yönden gelinir. Kapalı bir sokaktan gelen katkı toplama alınmaz. Düzgün ızgarada bu sayılar Pascal üçgenindeki sayılardır: başlangıcın 2 adım sağında ve 2 adım yukarısında bulunan köşeye 6 yol vardır.
Çözümlü örnekler
Örnek 1. Bir ızgarada A(0, 0) noktasından B(5, 4) noktasına yalnızca sağa ve yukarı gidilerek ulaşılacaktır. Bu en kısa yollardan kaçı C(2, 2) noktasından geçmez?
Çözüm. Bütün yollar C(9, 4) = 126 tanedir. A'dan C'ye 2 sağ ve 2 yukarı adımla C(4, 2) = 6 yol, C'den B'ye 3 sağ ve 2 yukarı adımla C(5, 2) = 10 yol vardır; C'den geçen yollar 6·10 = 60 tanedir. C'den geçmeyen yollar 126 − 60 = 66 olur.
Örnek 2. A(0, 0) noktasından B(4, 3) noktasına giden en kısa yollarda (1, 1) ile (2, 1) köşeleri arasındaki sokak kapalıdır. Kaç farklı en kısa yol kullanılabilir?
Çözüm. Bütün yollar C(7, 3) = 35 tanedir. Kapalı sokağı kullanan yollar önce (1, 1) köşesine gelir: 2 yol. Sokağı geçtikten sonra (2, 1) köşesinden B'ye 2 sağ ve 2 yukarı adım kalır: C(4, 2) = 6 yol. Sokağı kullanan yollar 2·6 = 12 tanedir; kullanılabilen yollar 35 − 12 = 23 olur.
Örnek 3. A(0, 0) noktasından B(6, 4) noktasına giden en kısa yollardan kaçı hem C(2, 1) hem D(4, 3) noktasından geçer?
Çözüm. Yol üç parçadır. A'dan C'ye 2 sağ ve 1 yukarı adım: C(3, 1) = 3 yol. C'den D'ye 2 sağ ve 2 yukarı adım: C(4, 2) = 6 yol. D'den B'ye 2 sağ ve 1 yukarı adım: C(3, 1) = 3 yol. Çarpım 3·6·3 = 54 olur.
Sık yapılan hatalar
- Zorunlu noktadan geçen yollarda iki parçanın sayılarını toplamak; parçalar çarpılır.
- Adım sayılarını nokta koordinatlarının farkı yerine koordinatların kendisinden hesaplamak.
- Kapalı sokağı yasak nokta gibi düşünüp iki uç köşeden geçen bütün yolları çıkarmak.
- m sağ ve n yukarı adım: C(m + n, n) yol.
- Zorunlu nokta: parçaları çarp; yasak nokta: tüm yollardan çıkar.
- Düzensiz planda her köşeye, solundaki ve altındaki sayıların toplamını yaz.