Bilgisayar Olimpiyat Kampından Notlar I
Temel sayma problemlerinin çoğu iki sonlu kümenin elemanları arasında kaç çeşit eşleme yapılabileceği sorularına indirgenebilir. Örneğin bir basketbol takımının K oyuncusunu bir otelin N odasına yerleştirmeye çalıştırdığımızı düşünelim. Öncelikle bir odada kaç kişi kalabileceği sorusuna göre üç farklı tip problem tanımlayabiliriz:
A. Bir odada herhangi sayıda oyuncu kalabilir.
B. Bir odada en çok bir kişi kalmalı (K <= N).
C. Bir odada en az bir kişi kalmalı (K >= N).
Diğer yandan K ya da N küme elemanlarının kimliklerinin önemli olup olmadığı, ya da permutasyonlarının (değişik sıralamalarının) farklı çözüm olarak sayılıp sayılmadığı da bize dört farklı tip problem verir. Bu problem tiplerini değişik objelerle örneklendirecek olursak:
0. K ve N elemanlarının kimlikleri önemli. (K kişiyi N odaya dağıtıyoruz)
1. K'lar birbiriyle eş, N'ler farklı. (K topu N odaya dağıtıyoruz)
2. K'lar farklı, N'ler birbiriyle eş. (K kişiyi N takıma ayırıyoruz)
3. K'lar da N'ler de birbiriyle eş. (K topu N gruba ayırıyoruz)
Burada birbiriyle eşlenmesi daha kolay olduğu için kişi yerine top, oda yerine takım ya da grup kullandık. (0) probleminde kimin hangi odada kaldığı önemliyken, (1) probleminde sadece hangi odada kaç top olduğu önemli. (2) probleminde ABCD isminde dört kişiyi (AB) ve (CD) gibi iki takıma ayırmakla (CD) ve (AB) gibi iki takıma ayırmak aynı çözüm sayılıyor. (3) probleminde ise ne topların ne grupların kimliği önemli, burada örneğin 6 topu 3+2+1 olarak ayırmak ile 4+1+1 olarak ayırmak farklı çözümler sayılsa da 3+2+1 ile 1+2+3 aynı çözüm sayılıyor.
Matematikçi Gian-Carlo Rota bu seçenekleri göz önüne alarak temel sayma problemlerini A0, A1, ..., C2, C3 şeklinde 12 kategoride sınıflandırmayı öneriyor. Örneğin lisede öğrendiğimiz permutasyon B0, kombinasyon B1 problemlerine denk geliyor. Malesef bu sınıflamanın dışında kalan Catalan objelerini, permutasyon tiplerini, ağaç tiplerini sayma problemleri de var fakat onları başka bir notta ele alırız.
Bu problemlerin bazıları şu teknikle çözülebilir: saymamız istenilen çözümlerden herhangi birini oluşturmak için K aşama tanımlayalım. i'nci aşamada $n_i$ potansiyel farklı seçenek olsun. İzleyebileceğimiz farklı yol sayısı bu durumda $n_1 n_2 \ldots n_k$ çarpımı olarak ifade edilebilir. Hemen bir iki örnek:
A0. K kişiyi N odaya herhangi bir sınırlama olmadan dağıtmak için her kişiye tek tek hangi odayı istediklerini sorarız. K sorunun (aşamanın) her birine N farklı cevap (seçenek) gelme olasılığı var. Dolayısıyla potansiyel çözüm sayımız $N^K$ olur.
B0. K kişiyi N odaya her odada en fazla bir kişi kalacak şekilde dağıtmak için yine herkese tek tek hangi odayı istediklerini sorabiliriz. Fakat sırası gelen kişi kendinden önce seçilmiş odaları seçemez, boş odalardan birini seçebilir. Yani birinci kişi N oda, ikinci kişi (N-1) oda, üçüncü kişi (N-2) odadan birini seçebilir. Bu durumda çözüm sayımız N(N-1)...(N-K+1)=$N^\underline{K}$ olur.
Bazan yukarıda verdiğimiz sayma tekniği kendi başına yeterli olmaz, çözümleri bilerek fazla ya da eksik sayıp sonradan bir düzeltme yapmak gerekebilir.
B1. K topu N odaya her odada en fazla bir top olacak şekilde dağıtma problemine bakalım. Topların kimliği önemli olmadığına göre buna N odadan K tanesini seçme problemi olarak da bakabiliriz. Çözüme B0 gibi başlayıp her topa hangi odayı istediğini soralım. Örneğin 3 top ve 5 oda varsa 123, 231, 245 gibi $N^\underline{K}$ farklı cevap alabiliriz. Fakat topların kimlikleri önemli olmadığına göre 123, 132, 213, 231, 312, 321 cevaplarının hep aynı 3 odayı doldurdukları için aynı konfigürasyon olarak sayılmaları gerekir. Diğer bir deyişle aslında B0 çözümü kullanarak biz her konfigürasyonu 6=3!=K! defa saymış olduk. Doğru cevabı elde etmek için B0'daki cevabı K!'e bölerek $N^{\underline{K}} / K! = \tbinom{N}{K}$ formülünü elde ederiz.
Bazı problemlerde en pratik çözüm ise önce eldeki problemi saymasını bildiğimiz başka bir probleme dönüştürmekten geçer:
A1. K topu N odaya herhangi bir sınırlama olmaksızın dağıtmayı düşünelim. Bu topları N odaya koymakla onları sıraya dizip aralarına N-1 duvar yerleştirmek birbirine eş iki problem olarak görülebilir. İkinci problemde duvarlarla toplar K+N-1 pozisyon işgal ederler. Bu pozisyonlardan hangi K tanesini topların işgal edeceğini sorarsak $\binom{K+N-1}{K}$ çözümünü elde ederiz.
C1. K topu N odaya her odada en az bir top olacak şekilde dağıtma (K>=N) probleminde ise önce her odaya birer top koyarak boş oda kalmamasını garantiler, daha sonra kalan K-N top üzerinde A1 çözümünü uygulayabiliriz: $\binom{K-1}{K-N}$.
Son olarak bu problemlerin bir kısmının kapalı bir formülle çözümü yoktur. Bu durumlarda özyinelemeli (recursive) formüller aramak tek çıkar yol olabilir:
C2. K kişiyi N takıma (her takımda en az bir kişi olacak şekilde, K>=N) ayırma problemini ele alalım. Özyinelemeli çözümlerin ana fikri problemin daha küçük bir halini çözebildiğimizi varsaymak, ve buna dayanarak orijinal problemi çözmektir. C2 için önce K-1 kişiyi takımlara ayırmanın yollarını sayabildiğimizi varsayalım. K'inci kişiyi ne yapacağımızı düşünelim. Bu son kişi ya kendi başına bir takım olacak (bu durumda geri kalan K-1 kişi N-1 takım oluşturacak), ya da diğerlerinin oluşturduğu takımlardan birinin içine eklenecek (bu durumda geri kalan K-1 kişinin N takım oluşturması, ve son kişinin bunlardan birini seçmesi gerek). Bu dediklerimizi formüle dökersek: f(K, N) = f(K-1, N-1) + N f(K-1, N). Formülü tamamlamak için problemin en küçük halini elle çözebiliriz f(1,1) = 1. Bu çözüm bize genel olarak K elemanlı bir kümenin elemanlarının kaç değişik şekilde N parçaya ayrılabileceğini verir ve hesapladığımız f fonksiyonu da ikinci tip Stirling sayısı olarak bilinir.
C3. K topu N gruba ayırma problemi için ise en küçük grupta tek top olan çözümlerle birden fazla top olan çözümleri ayrı ayrı sayalım. En küçük grupta tek top olan çözümlerin sayısını geri kalan K-1 topu N-1 gruba ayırarak bulabiliriz. En küçük grupta birden fazla top olan çözümleri ise (daha önce C1'de yaptığımız gibi) önce her gruba garanti olan birer topu koyup geri kalan K-N topu N gruba ayırarak sayabiliriz. Formüle dökecek olursak: f(K, N) = f(K-1, N-1) + f(K-N, N) ve f(1, 1) = 1. Bu çözüm bize genel olarak bir K tamsayısının kaç değişik şekilde N parçaya ayrılabileceğini verir.
Diğer çözdüğümüz problemlerde de benzer tekniklerle özyinelemeli formüller bulabiliriz. Örneğin:
A0. K-1 kişi hangi odalarda kalacaklarına karar verdikten sonra son kişi yine N odadan birini seçer.
$N^K$: f(N,K) = N f(N,K-1)
B0. Son odada kimsenin kalmadığı ve birinin kaldığı çözümleri toplarız.
$N^{\underline{K}}$: f(N,K) = f(N-1,K) + K f(N-1,K-1)
B1. Son odaya top konulan ve konulmayan çözümleri toplarız.
$\tbinom{N}{K}$: f(N,K) = f(N-1,K-1) + f(N-1,K)
Kalan problemlerin çözümünü okuyucuya bırakıyorum. İpucu olarak C0 ve A2'nin C2 kullanarak, A3'un ise C3 kullanarak çözülebileceğini B2 ile B3'un ise pek ilginç çözümleri olmadığını söyleyebilirim.
Full post...
Related link
