Sayma: Permütasyon ve Kombinasyon

Saymak neden ayrı bir konu?

Bir sınıfta kaç öğrenci olduğunu bulmak için tek tek saymak yeter. Ama "altı arkadaş bir fotoğraf için yan yana kaç farklı biçimde durabilir?" sorusunda olası dizilişleri tek tek yazmaya kalkarsak 720 satır yazmamız gerekir. Sayma konusunun amacı, durumları yazmadan, düzenli bir akıl yürütmeyle saymaktır. Bunun için iki temel ilke yeterlidir: toplama ilkesi ve çarpma ilkesi. Permütasyon ve kombinasyon formülleri bu iki ilkenin kısaltılmış hâlidir. Formülü ezberleyip nereden geldiğini bilmeyen öğrenci, koşul eklenen ilk soruda takılır; ilkeyi anlayan öğrenci formülü gerekirse yeniden kurar.

Toplama yoluyla sayma

Bir iş birbirinden ayrık iki yoldan biriyle yapılabiliyorsa ve birinci yolda \(m\), ikinci yolda \(n\) seçenek varsa iş toplam \(m + n\) farklı biçimde yapılır. Buradaki anahtar bağlaç ya da bağlacıdır. Ayşe okula 3 farklı otobüs hattından biriyle ya da 2 farklı metro hattından biriyle gidebiliyorsa okula \(3 + 2 = 5\) farklı biçimde gidebilir; çünkü bir sabah ya otobüse ya metroya biner, ikisine birden binmez.

Toplama ilkesinin tek şartı, durumların ayrık olmasıdır, yani aynı seçeneğin iki grupta birden sayılmamasıdır. Kümeler konusundaki \(s(A \cup B) = s(A) + s(B) - s(A \cap B)\) eşitliği bu şartı hatırlatır: ortak eleman varsa bir kez çıkarılır. Sayma problemlerinde durumları "ilk rakam 2 olanlar", "ilk rakam 3 olanlar" gibi çakışmayan gruplara ayırıp her grubu ayrı saymak ve sonra toplamak, en güvenli yöntemlerden biridir.

Çarpma yoluyla sayma ve ağaç şeması

Bir iş art arda yapılan iki adımdan oluşuyorsa ve birinci adım \(m\), ikinci adım (birinci adımın her sonucu için) \(n\) farklı biçimde yapılabiliyorsa iş toplam \(m \cdot n\) farklı biçimde yapılır. Buradaki anahtar bağlaç ve bağlacıdır. Bir kafede 3 içecekten biri ve 2 tatlıdan biri seçilecekse her içecek seçimine 2 tatlı seçimi eklenir; toplam \(3 \cdot 2 = 6\) farklı ikili oluşur.

Ağaç şeması çarpma ilkesinin neden doğru olduğunu gösterir: ilk adımın her seçeneği bir dal, ikinci adımın her seçeneği o daldan çıkan bir alt daldır. Uçların sayısı, dal sayılarının çarpımıdır. Adım sayısı arttıkça ağaç çizmek zorlaşır ama ilke aynı kalır: \(k\) adımlı bir işte adımların seçenek sayıları \(n_1, n_2, \dots, n_k\) ise toplam \(n_1 \cdot n_2 \cdots n_k\) olur. Önemli olan, her adımdaki seçenek sayısının önceki adımlarda ne seçildiğine bağlı olmamasıdır. Bağlıysa (örneğin "ilk rakam 0 olamaz, son rakam çift olmalı" gibi koşullar çakışıyorsa) durumları gruplara ayırıp her grupta çarpma ilkesini ayrı uygularız, sonra toplama ilkesiyle birleştiririz.

Faktöriyel

1'den \(n\)'ye kadar olan doğal sayıların çarpımına \(n\) faktöriyel denir ve \(n!\) ile gösterilir:

Örneğin \(4! = 24\), \(5! = 120\), \(6! = 720\). Tanım gereği \(0! = 1\) ve \(1! = 1\) alınır. \(0! = 1\) keyfî bir kabul değildir: \(n! = n \cdot (n-1)!\) bağıntısı \(n = 1\) için de geçerli olsun istiyorsak \(1! = 1 \cdot 0!\) olmalı, yani \(0! = 1\) olmalıdır. Sayma açısından da anlamlıdır: hiç nesne yokken onları dizmenin tek yolu "hiçbir şey yapmamak"tır.

Faktöriyelli ifadeleri sadeleştirirken büyük faktöriyeli küçüğe kadar açarız: \(\frac{10!}{8!} = \frac{10 \cdot 9 \cdot 8!}{8!} = 90\). Toplama ya da çıkarma varsa önce ortak çarpan parantezine alırız: \(7! + 6! = 6!(7 + 1) = 8 \cdot 6!\). Faktöriyeller çok hızlı büyür; \(10! = 3\,628\,800\) olduğundan sorularda faktöriyeli hesaplamak yerine sadeleştirmek hem zaman kazandırır hem hata riskini azaltır.

Permütasyon: sıralı diziliş

\(n\) farklı nesneyi bir sıraya dizmenin kaç yolu olduğunu çarpma ilkesiyle bulabiliriz. Birinci yere \(n\) nesneden biri, ikinci yere kalan \(n - 1\) nesneden biri gelir ve böyle devam eder. Toplam \(n \cdot (n-1) \cdots 1 = n!\) diziliş olur. Altı arkadaşın yan yana fotoğraf çektirmesi bu yüzden \(6! = 720\) farklı biçimde olur.

Nesnelerin hepsini değil de \(r\) tanesini sıraya dizmek istiyorsak çarpma \(r\) adım sürer. \(n\) farklı nesnenin \(r\)'li permütasyonu

olur. 10 kişilik bir kulüpte başkan, başkan yardımcısı ve sayman seçmek \(P(10, 3) = 10 \cdot 9 \cdot 8 = 720\) farklı biçimde yapılır. Burada sıra önemlidir: Ali başkan, Banu yardımcı olduğunda ortaya çıkan yönetim, Banu başkan, Ali yardımcı olduğundakinden farklıdır. Permütasyonu kombinasyondan ayıran soru tam olarak budur: seçilenlerin yerleri değişince yeni bir durum oluşuyor mu?

Tekrarlı permütasyon

Dizilen nesnelerin bazıları birbirinin aynısıysa \(n!\) sayısı fazla sayar. KALEM kelimesinin harfleri birbirinden farklıdır; yerleri değiştirilerek \(5! = 120\) farklı dizi yazılır. ANKARA kelimesinde ise üç tane A vardır. A harflerini geçici olarak \(A_1, A_2, A_3\) diye ayırırsak \(6! = 720\) dizi elde ederiz. Ama \(A_1\), \(A_2\) ve \(A_3\) kendi aralarında \(3! = 6\) farklı biçimde yer değiştirdiğinde gözümüzün gördüğü kelime değişmez. Her gerçek dizi 6 kez sayılmıştır; doğru sonuç \(\frac{720}{6} = 120\)'dir.

Genel olarak \(n\) nesnenin \(n_1\) tanesi bir türden, \(n_2\) tanesi başka bir türden, …, \(n_k\) tanesi bir başka türden aynıysa (\(n_1 + n_2 + \dots + n_k = n\)) farklı dizilişlerin sayısı

olur. Bu formül yalnızca kelimelerde değil, "3 kırmızı ve 2 mavi özdeş bayrak bir direğe kaç farklı sırayla dizilir?" (\(\frac{5!}{3! \cdot 2!} = 10\)) ya da birazdan göreceğimiz ızgara yolu sorularında da kullanılır.

Dairesel permütasyon

Yuvarlak bir masada koltuklar numaralı değilse önemli olan, herkesin kimin sağında ve solunda oturduğudur. Herkes aynı yönde bir koltuk kayarsa oturuş değişmiş sayılmaz. \(n\) kişiyi düz bir sıraya \(n!\) biçimde dizebiliriz; her dairesel oturuş, bu düz dizilişlerden \(n\) tanesine karşılık gelir (dizinin hangi kişiyle başlatıldığı). Bu yüzden \(n\) farklı kişinin yuvarlak masaya oturuş sayısı

olur. Aynı sonucu şöyle de düşünebiliriz: bir kişiyi masaya oturtup onu sabit bir başlangıç kabul ederiz; kalan \(n - 1\) kişi onun sağından itibaren \((n - 1)!\) biçimde dizilir.

Koşullu dizilişler: yan yana olma, olmama ve belirli yerler

ÖSYM'nin en sevdiği permütasyon soruları bir koşul içerir. Üç temel teknik vardır.

Yan yana olma (paketleme): Birlikte durması istenen kişileri tek bir paket gibi düşün. 4 erkek ve 3 kız sıraya girecek ve kızlar yan yana olacaksa 3 kızlık paket ile 4 erkek, toplam 5 birim \(5!\) biçimde dizilir. Paketin içinde kızlar da kendi aralarında \(3!\) biçimde yer değiştirebilir. Sonuç \(5! \cdot 3! = 720\) olur. Paketin iç düzenini unutmak en sık yapılan hatadır.

Yan yana olmama (boşluk yöntemi): Hiçbir iki kızın yan yana gelmemesi isteniyorsa önce kısıtsız grubu (erkekleri) dizeriz: \(4! = 24\) biçim. Dört erkeğin arasında ve iki ucunda 5 boşluk oluşur. Kızları bu boşluklardan üçüne, her boşluğa en çok bir kız gelecek biçimde yerleştiririz: \(P(5, 3) = 60\) biçim. Toplam \(24 \cdot 60 = 1\,440\) olur.

Burada dikkat edilmesi gereken şey, "kızların hepsi yan yana olmasın" ile "hiçbir iki kız yan yana olmasın" ifadelerinin farklı olmasıdır. Birincisi tümleyenle bulunur: \(7! - 5! \cdot 3! = 5\,040 - 720 = 4\,320\). Bu sayının içinde iki kızın yan yana, üçüncünün ayrı durduğu dizilişler de vardır. İkincisi boşluk yöntemiyle bulunur ve 1 440'tır.

Belirli yerlerde belirli kişiler: Kısıtı olan kişiye ya da yere önce karar ver, sonra kalanları diz. 7 kişilik sırada Ali uçlardan birinde olacaksa Ali'nin yeri 2 biçimde seçilir, kalan 6 kişi \(6!\) biçimde dizilir: \(2 \cdot 720 = 1\,440\). İki kişinin arasında tam \(k\) kişi olması istendiğinde önce bu iki kişinin oturabileceği yer çiftlerini sayarız, sonra iki kişinin kendi arasındaki sırasını (2) ve kalanların dizilişini çarparız.

Rakamlarla sayı oluşturma

Rakam sorularında basamaklar birer "kutu", rakamlar da bu kutulara konan nesnelerdir. İki kural sonucu belirler: en soldaki basamak 0 olamaz ve "rakamları farklı" deniyorsa her rakam bir kez kullanılır. Koşulu en kısıtlı olan kutudan başlamak gerekir. Çift sayı isteniyorsa birler basamağı, 5'e bölünebilme isteniyorsa birler basamağı (0 ya da 5), belirli aralık isteniyorsa en büyük basamak önce doldurulur.

Zorluk, iki kısıtın aynı rakamı ilgilendirdiği durumlarda çıkar. 0, 1, 2, 3, 4, 5 rakamlarıyla rakamları farklı üç basamaklı çift sayıları sayalım. Birler basamağı 0, 2 ya da 4 olabilir; ama birler basamağı 0 olunca yüzler basamağı için 0 zaten kullanılmış olur, değilse yüzler basamağı için 0 da yasaklıdır. Bu yüzden iki durum ayrı sayılır:

• Birler basamağı 0: yüzler için 5, onlar için 4 seçenek; \(5 \cdot 4 = 20\).
• Birler basamağı 2 ya da 4: yüzler için 0 ve kullanılan rakam dışında 4, onlar için 4 seçenek; \(2 \cdot 4 \cdot 4 = 32\).

Toplam \(20 + 32 = 52\) sayı vardır. Durumları ayırmadan "birler için 3, yüzler için 4, onlar için 4" diye çarpmak 48 verir ve yanlıştır.

Aralık sorularında sayıyı büyük basamaktan başlayarak gruplara ayır. "250 ile 500 arasında" deniyorsa yüzler basamağı 2, 3 ya da 4'tür; yüzler 2 olduğunda onlar basamağı da sınırlanır. Sınır sayılarının (250 ve 500) aralığa girip girmediğine ve oluşturulabilir olup olmadıklarına ayrıca bak.

Kombinasyon: sırasız seçim

Bir gruptan yalnızca seçim yapılıyor, seçilenlere görev ya da sıra verilmiyorsa sıra önemsizdir. 10 kişiden 3 kişilik bir ekip seçerken {Ali, Banu, Can} ekibi ile {Can, Ali, Banu} ekibi aynıdır. \(n\) farklı nesneden \(r\) tanesini sırasız seçmenin sayısına \(n\)'nin \(r\)'li kombinasyonu denir ve \(C(n, r)\) ya da \(\binom{n}{r}\) ile gösterilir.

Formülü permütasyondan elde ederiz. \(r\) nesneyi seçip sıraya dizmek \(P(n, r)\) biçimde olur. Bu işi iki adıma ayırabiliriz: önce \(r\) nesneyi seç (\(C(n, r)\) biçim), sonra seçtiklerini diz (\(r!\) biçim). Çarpma ilkesiyle \(P(n, r) = C(n, r) \cdot r!\) olur, buradan

bulunur. 10 kişiden 3 kişilik ekip \(\binom{10}{3} = \frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1} = 120\) biçimde seçilir. Aynı 10 kişiden başkan, yardımcı ve sayman seçmenin 720 olduğunu görmüştük; \(720 = 120 \cdot 3!\) eşitliği, her ekibin üç kişisine görevlerin \(3!\) biçimde dağıtılabildiğini söyler.

Kombinasyonun özellikleri ve Pascal özdeşliği

Kombinasyonun birkaç özelliği hesabı kısaltır ve soruların önemli bir bölümü bunlara dayanır:

• \(\binom{n}{0} = \binom{n}{n} = 1\) ve \(\binom{n}{1} = n\).
• \(\binom{n}{r} = \binom{n}{n - r}\). Nedeni sözel olarak açıktır: 10 kişiden ekibe girecek 3 kişiyi seçmek, ekibe girmeyecek 7 kişiyi seçmekle aynı şeydir. Bu yüzden \(\binom{n}{a} = \binom{n}{b}\) ise ya \(a = b\) ya da \(a + b = n\)'dir.
• Pascal özdeşliği: \(\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}\).

Pascal özdeşliğinin gerekçesi de bir sayma düşüncesidir. \(n + 1\) kişiden \(r + 1\) kişi seçelim ve bu kişilerden biri Ali olsun. Seçilen grup ya Ali'yi içerir ya içermez. Ali'yi içeren gruplarda kalan \(r\) kişi diğer \(n\) kişiden \(\binom{n}{r}\) biçimde seçilir. Ali'yi içermeyen gruplarda \(r + 1\) kişinin hepsi diğer \(n\) kişiden \(\binom{n}{r+1}\) biçimde seçilir. Toplama ilkesiyle eşitlik çıkar.

Pascal üçgeni bu özdeşliğin tablosudur. Satırlar simetriktir, bu da \(\binom{n}{r} = \binom{n}{n-r}\) özelliğinin görüntüsüdür.

Komite ve takım seçme; seçip sıralama

Komite sorularında grubu türlere (kadın-erkek, öğretmen-öğrenci) ayırıp her türden kaç kişi seçileceğine göre durumlar oluşturulur. 5 kadın ve 4 erkekten 3 kişilik, içinde tam 2 kadın bulunan komite sayısı \(\binom{5}{2} \cdot \binom{4}{1} = 40\)'tır: kadınları ve erkeği seçeriz, çarparız. "En az iki kadın" deniyorsa tam 2 ve tam 3 kadınlı durumlar ayrı sayılıp toplanır ya da tümleyen kullanılır.

"En az bir" koşulunda sık görülen bir tuzak vardır: önce bir kadını seçip (\(\binom{5}{1}\)) kalanları serbestçe seçmek (\(\binom{8}{2}\)) bazı komiteleri birden fazla sayar. İçinde iki kadın bulunan bir komite, "önce seçilen kadın" hangisi kabul edilirse o kadar kez sayılır. Doğru yol tümleyendir: \(\binom{9}{3} - \binom{4}{3} = 84 - 4 = 80\).

Belirli iki kişinin birlikte olmaması istendiğinde yine tümleyen kullanılır: tüm seçimlerden ikisinin birlikte bulunduğu seçimler çıkarılır. İkisinin birlikte bulunduğu seçimleri saymak kolaydır: bu iki kişi seçilmiş kabul edilir, kalan yerler diğer kişilerden doldurulur.

Seçip sıralama sorularında iş iki adımlıdır: önce kombinasyonla kimin seçileceği belirlenir, sonra seçilenler permütasyonla dizilir ya da görevlendirilir. Örneğin 5 matematik ve 4 fizik kitabından 2'şer kitap seçip bir rafa dizmek \(\binom{5}{2} \cdot \binom{4}{2} \cdot 4!\) biçimde yapılır. Yalnızca bir kısmına görev verilenlerde görevli olanlar permütasyonla, görevsiz üyeler kombinasyonla seçilir.

Geometride kombinasyon

Düzlemde herhangi üçü doğrusal olmayan \(n\) nokta varsa her iki nokta tek bir doğru, her üç nokta tek bir üçgen belirtir. Doğru sayısı \(\binom{n}{2}\), üçgen sayısı \(\binom{n}{3}\) olur. Çünkü doğruyu belirlerken noktaların sırası önemli değildir.

Noktaların bir kısmı aynı doğru üzerindeyse sayım düzeltilir. \(n\) noktanın \(k\) tanesi aynı doğru üzerinde, başka hiçbir üçü doğrusal değilse:

• Doğru sayısı: bu \(k\) noktadan seçilen \(\binom{k}{2}\) ikilinin hepsi aynı doğruyu verir. Onları çıkarıp o doğruyu bir kez ekleriz: \(\binom{n}{2} - \binom{k}{2} + 1\).
• Üçgen sayısı: aynı doğru üzerindeki üç nokta üçgen oluşturmaz, \(\binom{n}{3} - \binom{k}{3}\).

Birden fazla doğru varsa her doğru için aynı düzeltme yapılır. İki doğrunun kesişim noktası iki doğruda birden sayılır; bu noktayı her iki doğrunun nokta sayısına katmak gerekir.

Izgarada en kısa yollar

Kare ızgaralı bir sokak ağında A noktasından sağa ve yukarı giderek B noktasına ulaşmak istiyoruz. A'dan B'ye 5 birim sağa, 3 birim yukarı gitmek gerekiyorsa her en kısa yol 5 tane S (sağ) ve 3 tane Y (yukarı) adımından oluşur. Farklı yollar, bu 8 adımın farklı sıralarıdır. Bu bir tekrarlı permütasyondur:

Aynı sonuca kombinasyonla da ulaşılır: 8 adımdan hangi 3'ünün yukarı olacağını seçmek yeter.

Şekildeki düğümlerin yanındaki sayılar ikinci bir yöntemi gösterir: bir düğüme ya solundan ya altından gelinir, bu yüzden düğümün sayısı bu iki komşunun sayılarının toplamıdır. Bu, Pascal özdeşliğinin ta kendisidir. Bu toplama yöntemi, ızgarada kapalı bir kavşak ya da eksik bir sokak bulunduğunda çok işe yarar: kapalı kavşağa 0 yazılır ve toplama oradan devam eder.

Belirli bir C noktasından geçen yolların sayısı çarpma ilkesiyle bulunur: (A'dan C'ye yol sayısı) · (C'den B'ye yol sayısı). C'den geçmeyen yollar ise tümleyenle bulunur.