Permütasyon ve Kombinasyon Açıklaması

Çarpma kuralı

Kombinatorik problemleri bir şeyin kaç farklı yolla gerçekleşebileceğini sorar. Temel, çarpma kuralıdır: bir seçim $m$ yolla, ondan bağımsız ikinci bir seçim $n$ yolla yapılabiliyorsa ikisi birlikte $m \times n$ yolla yapılabilir. Bu fikir istenen sayıda aşama için geçerlidir.

3 gömlek, 4 pantolon ve 2 çift ayakkabıyla $3 \times 4 \times 2 = 24$ farklı kombin oluşturulabilir. 0'dan 9'a kadar rakamlardan oluşan, tekrarın serbest olduğu dört haneli bir PIN kodunun $10 \times 10 \times 10 \times 10 = 10^4 = 10{,}000$ seçeneği vardır. Bu makaledeki tüm formüller böyle bir çarpmanın kısaltmalarıdır: problem tuhaf görünüyorsa aşama aşama saymaya dönmek her zaman güvenilirdir.

Faktöriyeller

$n$ farklı nesneyi bir sıraya dizmek için birinci yer için $n$, ikinci yer için $n - 1$ seçenek vardır ve bu böyle 1'e kadar sürer. Bu çarpıma $n$ faktöriyel denir:

Böylece $5! = 120$: beş kitap bir rafa 120 farklı şekilde dizilebilir. Tanım gereği $0! = 1$'dir; bu, aşağıdaki formülleri tutarlı tutar: «hiçbir şeyi» sıralamanın tam olarak bir yolu vardır. Faktöriyeller baş döndürücü bir hızla büyür: $10! = 3{,}628{,}800$, karıştırılmış bir iskambil destesinin ise $52!$ olası sırası vardır; bu 68 basamaklı bir sayıdır.

Permütasyonlar: sıra önemlidir

Permütasyon, $n$ farklı nesne arasından seçilen $r$ nesnenin sıralı bir dizisidir. Sıra önemli olduğundan «birinci, ikinci, üçüncü» dizisi «üçüncü, ikinci, birinci» dizisinden farklıdır. Permütasyonların sayısı şudur:

Yuvarlak bir masa etrafında oturma düzeni özel bir durumdur. Herkes bir sandalye kayarsa aynı düzen elde edilir; bu yüzden $n$ kişi $(n-1)!$ farklı şekilde oturtulabilir. Yuvarlak masadaki altı kişinin 720 değil, $5! = 120$ oturma düzeni vardır. Buna dairesel permütasyon denir.

Kombinasyonlar: sıra önemli değildir

Kombinasyon, yalnızca hangi elemanların seçildiğinin önemli olduğu bir seçimdir. Bir komisyon için Ayşe, Burak ve Ceren seçilirse hangi sırayla seçilirlerse seçilsinler aynı komisyon oluşur. $r$ nesneden oluşan her gruba $r!$ permütasyon karşılık gelir; bu yüzden bu sayıya böleriz:

Kombinasyonlar simetriktir: $\binom{n}{r} = \binom{n}{n-r}$, çünkü içeri girecek 3 kişiyi seçmek dışarıda kalacak 5 kişiyi seçmekle aynı şeydir. Bunlar aynı zamanda Pascal üçgenindeki sayılar ve $(a + b)^n$ binomunun açılımındaki katsayılardır.

Hangisinin gerektiği nasıl anlaşılır?

Tek bir soru sorun: seçilen iki elemanın yerini değiştirirseniz farklı bir sonuç elde eder misiniz? Evet ise sıra önemlidir ve permütasyon gerekir. Hayır ise kombinasyon kullanın.

• Yarışmadaki dereceler, sıralamalar, PIN kodları, oturma düzenleri ve programlar: permütasyon.
• Takımlar, komisyonlar, iskambil elleri, piyango biletleri ve pizza malzemeleri: kombinasyon.
• Grup içindeki görevler, örneğin başkan ve sayman, kişiler aynı gruptan seçilse bile sırayı önemli kılar.

Hızlı kontrol: permütasyon sayısı her zaman kombinasyon sayısının $r!$ katıdır. İki sonucunuz bu ilişkiyi sağlamıyorsa biri yanlıştır.

Tekrarlı seçimler ve tekrar eden harflerle saymak

Elemanlar tekrar edebiliyorsa formüller değişir. PIN kodu örneğindeki gibi tekrarlı sıralı seçimlerin sayısı $n^r$'dir. Tekrarlı sırasız seçimlerin sayısı, örneğin tatlar tekrar edebilirken 5 tattan 3 top dondurma seçmek, şudur:

Tekrar eden harflerin dizilişi bir düzeltme daha gerektirir: aynı harflerin yer değiştirmesi hiçbir şeyi değiştirmediğinden her tekrar sayısının faktöriyeline bölmek gerekir. Mississippi nehrinin İngilizce yazılışı 11 harften oluşur; bunların 4'ü I, 4'ü S ve 2'si P harfidir: demek ki $\frac{11!}{4!\,4!\,2!} = 34{,}650$ farklı anagramı vardır.

Olasılık hesapları için saymak

Çıktılar eşit olasılıklıysa olasılık, istenen çıktıların sayısının tüm olası çıktıların sayısına bölümüdür; bu yüzden asıl işi permütasyonlar ve kombinasyonlar yapar. Bu oranın temelini olasılık kuramının temelleri açıklar.

İskambil oyunları daha da fazla alıştırma sunar. Beş kartlık $\binom{52}{5} = 2{,}598{,}960$ olası el vardır. Dört asın birden bulunduğu bir el, kalan 48 karttan seçilecek yalnızca bir kart daha gerektirir; bu yüzden olasılık $\frac{48}{2{,}598{,}960} = \frac{1}{54{,}145}$'tir.

Tipik hatalar

• Bir takım ya da komisyon için permütasyon kullanmak; bu, sayımı $r!$ kat şişirir.
• $0! = 1$ olduğunu unutmak; bu da $\binom{n}{n}$ gibi formülleri bozar.
• Örneğin tekrar eden harfli anagramlarda aynı elemanları hesaba katmamak.
• Sonraki sayıları düzeltmeden bağımlı aşamaları çarpmak.

Permütasyon ve kombinasyon hesap makinesi ${}_nP_r$ ve ${}_nC_r$ değerlerini faktöriyeller üzerinden tüm adımlarıyla hesaplar; olasılık hesap makinesi ise bu sayıları olasılıklara dönüştürür.

Pascal üçgeni ve alt kümeler

Pascal üçgenindeki her sayı hemen üstündeki iki sayının toplamıdır ve $n$. satır $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$ değerlerini içerir. 4. satır 1, 4, 6, 4, 1'dir; bunlar tam olarak $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$ açılımının katsayılarıdır. Üçgenin oluşturulma kuralı da bir sayma sonucudur:

Nedenini anlamak için bir elemanı sabitleyin. $r$ elemanlı her seçim ya onu içerir ve bu durumda kalan $n - 1$ eleman arasından $r - 1$ eleman seçmek kalır, ya da içermez ve bu durumda $r$ elemanın tamamı kalan $n - 1$ eleman arasından seçilir. Tüm satırın toplamı $2^n$'dir, yani $n$ elemanlı bir kümenin toplam alt küme sayısı, çünkü her eleman ya girer ya girmez. Bu yüzden 8 malzemesi olan bir pizzacı, hiç malzemesiz pizzayı da sayarak $2^8 = 256$ farklı pizza yapabilir.

Alıştırmalar

1. 7 farklı kitap arasından seçilen 4 kitap bir rafa kaç farklı şekilde dizilebilir? Çözüm: ${}_7P_4 = 7 \times 6 \times 5 \times 4 = 840$.
2. 10 malzeme arasından 4 malzeme kaç farklı şekilde seçilebilir? Çözüm: $\binom{10}{4} = 210$.
3. ANANAS kelimesinin kaç farklı anagramı vardır? Çözüm: $\frac{6!}{3!\,2!} = 60$.
4. Tekrara izin verilirse 26 harften beş harfli kaç kod oluşturulabilir? Çözüm: $26^5 = 11{,}881{,}376$.

Sıkça sorulan sorular