Kombinasyon

Bir nesne kümesinden belli sayıda nesne seçiyorsak ve nesneleri hangi sırayla seçtiğimiz önemli değilse kombinasyonu kullanırız. Tipik bir örnek 6/49’luk lotodur: torbada 49 sayı var ve bunlardan 6’sını çekiyoruz; hangi sırayla çektiğimiz fark etmez.

Formülün Çıkarılması

Şans çarkı

Bir M kümemiz olsun, örneğin M = {a, b, c, d, e}. O zaman r’li kombinasyon, tam olarak r eleman içeren bir K ⊂ M alt kümesidir. K bir küme olduğu için sıra elbette önemli değildir. Yani M kümesinden üçlü bir kombinasyon örneğin {a, b, d} veya {b, c, d} olabilir.

r’li permütasyonlardan farkı şudur: r’li permütasyonlarda sıra önemliydi; bu yüzden (a, b, e) ve (e, b, a) farklı r’li permütasyonlardır, ama aynı kombinasyondur, çünkü (a, b, e) de (e, b, a) da aynı elemanları içerir; elemanların farklı sırada olması kombinasyonlarda bizi ilgilendirmez.

Yine de farklı kombinasyonların sayısı için bir formül elde etmek üzere r’li permütasyonlardan yararlanabiliriz. n elemanlı kümeden r’li permütasyonların sayısının tam olarak

$P (n, r) = \frac{n!}{(n - r)!}$

olduğunu biliyoruz. Önceki M = {a, b, c, d, e} kümesindeki tüm 3’lü permütasyonları sayarsak P(5, 3) = 60 farklı 3’lü permütasyon buluruz. Ancak her üçlü için onun tüm permütasyonları da orada olurdu. Yani orada abc üçlüsü de olurdu, ama acb, bac, bca, cab ve cba üçlüleri de. Bunlar altı farklı 3’lü permütasyondur, ama tek bir kombinasyondur, çünkü hepsi aynı elemanlara sahiptir.

Elimizde bir üçlü varsa bu üçlünün kaç farklı permütasyonu vardır? Tam olarak 3!. Başka bir deyişle, 3’lü permütasyonlar, 3’lü kombinasyonlardan tam olarak 3! kat daha fazladır. Tek bir kombinasyonla saymak yerine, verilen üçlünün her permütasyonuyla birlikte 3! kat fazla 3’lü permütasyonla sayıyoruz. Dolayısıyla 3’lü permütasyonların sayısını 3!’e bölersek kombinasyonların sayısını elde ederiz.

Önceki yöntemi genelleştirip şunu söyleyebiliriz: n elemanlı bir kümeden tüm farklı r’li kombinasyonların sayısını arıyorsak bu sayı, ona C(n, r) dersek, şuna eşittir:

$C (n, r) = \frac{P (n, r)}{r!},$

yani r’li permütasyonların sayısı bölü r!; bu da her r’linin permütasyon sayısıdır. Formülü, r’li permütasyonların formülünü açarak düzenleyebiliriz:

$C (n, r) = \frac{P (n, r)}{r!} = \frac{n!}{(n - r)!} \cdot \frac{1}{r!} = \frac{n!}{(n - r)! \cdot r!} .$

Örnek: {a, b, c} kümesinden ikili kombinasyonların sayısı

$C (3, 2) = \frac{3!}{1! \cdot 2!} = 3$

ve bu kombinasyonlar şunlardır: {a, b}, {a, c} ve {b, c}. İlk M = {a, b, c, d, e} kümesinden üçlü kombinasyonlarda ise

$C (5, 3) = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

sayısını elde ederdik ve bu kombinasyonlar şunlardır: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

Binom Katsayısı

Önceki C(n, r) gösterimi pek kullanılmaz; onun yerine binom katsayısı kullanılır. Binom katsayısı şu biçimdedir:

$(\binom{n}{r})$

Kesir çizgisi olmayan bir kesir gibidir (alışkanlıktan çizgiyi yine de yazma eğiliminde olacaksın), ama parantezli; o parantezler isteğe bağlı değildir, mutlaka orada olmalıdır. Binom katsayısı “n üzeri r” diye okunur. Binom katsayısının değeri C(n, r) ile aynıdır.

$(\binom{n}{r}) = \frac{n!}{(n - r)! \cdot r!}$

Yani 5 elemanlı bir kümemiz varsa ve ondan dörtlüler seçiyorsak bunların toplam sayısı

$(\binom{5}{4}) = \frac{5!}{1! \cdot 4!} = 5$

olur.

Temel Bağıntılar

Binom katsayısı ve n ∈ ℕ için şunlar geçerlidir:

$\begin{array}{rcl} (\binom{n}{0}) = (\binom{n}{n}) = (\binom{0}{0}) & = & 1 \\ (\binom{n}{1}) & = & n \end{array}$

Ayrıca n, r ∈ ℕ ve r ≤ n için

$\begin{array}{rcl} (\binom{n}{n - r}) & = & (\binom{n}{r}) . \end{array}$

ve n, r ∈ ℕ ile r < n için

$\begin{array}{rcl} (\binom{n}{r}) + (\binom{n}{r + 1}) & = & (\binom{n + 1}{r + 1}) . \end{array}$

geçerlidir.

Hesap Makinesi

Aşağıdaki hesap makinesi n üzeri r binom katsayısını hesaplar.

Çözümlü Örnekler

Daha önce söz ettiğimiz 6/49’luk lotoyla başlayalım. Bu oyunda 49 toplu bir torbadan toplam 6 top çekilir. Kaç farklı sonuç çekilebilir?

Her şeyden önce sayıların çekilme sırası önemli mi? Önemli değil, yalnızca sayıları tahmin ediyoruz, sıralarını değil. Kombinasyon kullanacağız. Toplam 49 topumuz var, 6 top çekiyoruz; şu binom katsayısına ulaşırız:

$(\binom{49}{6}) = \frac{49!}{(49 - 6)! \cdot 6!} = \frac{49!}{43! \cdot 6!} = 13.983 .816$

Çekilebilecek toplam 13.983.816 sonuç vardır. Bu da bize, bu arada, tek bir kuponla kazanma olasılığını verir: 1/13.983.816; bu da %0,00000715112 eder.
Kerem’in sınıfında 13 arkadaşı var. Hafta sonu pikniğine onlardan 4 farklı kişiyi çağırabiliyor. Kerem kaç farklı dörtlü arasından seçim yapabilir?

Bu yine kombinasyonla ilgili basit bir örnek; sıra önemli değil, Kerem için ilk çağırdığı da fark etmez, sonuncusu da. Böylece 13 arkadaştan oluşan bir kümemiz var ve her seferinde bunlardan 4 arkadaş seçiyoruz. Bu da şu binom katsayısına götürür:

$(\binom{13}{4}) = 715.$
Yarısı erkek, yarısı kız olan elli kişilik bir grubun var. Üçlüler tek bir cinsiyetten oluşmamalıysa (yani üçlüde üç erkek ya da üç kız bulunmamalıysa) kaç farklı üçlü vardır?

Bu, biraz daha karmaşık bir kombinasyon. Tek cinsiyetli üçlüleri dışarıda bırakırsak üçlünün oluşabileceği yalnızca iki yol kalır: iki erkek ve bir kız ya da bir erkek ve iki kız; ilk grubun (iki erkek ve bir kız) kombinasyon sayısı ikinci grubun kombinasyon sayısıyla aynıdır. Bu yüzden ilk grubun kombinasyon sayısını hesaplayıp ikiyle çarpmamız yeterli. Şimdi yine çok kolay. Erkeklerin farklı ikililerinin kombinasyon sayısını belirleriz; bu, 25 üzeri 2’dir; bunu bir kızın seçilme kombinasyon sayısıyla çarparız (o da 25’tir, yukarıdaki temel bağıntılara, özellikle ikinci satıra bak). Bu sonucu yalnızca ikiyle çarparız ve sonuca ulaşırız.

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
Bir kutuda 15 ürün var ve bunların 4’ü kusurlu. 6 ürünü kaç yolla seçebiliriz ki
- hiçbiri kusurlu olmasın? Bu durumda 6 ürünü kusurlu olmayan 15 − 4 = 11 üründen seçiyoruz. Böylece şu binom katsayısını elde ederiz:
  
  $(\binom{11}{6}) = 462.$
- tam olarak bir ürün kusurlu olsun? Yani 5 sağlam ve 1 kusurlu ürün içeren bir küme seçiyoruz. Toplam 11 sağlam ürünümüz, 4 kusurlu ürünümüz var. Çarpma yoluyla sayma kuralını kullanır ve sonucu buluruz:
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- en fazla bir ürün kusurlu olsun? Çözmek için önceki sonuçlardan yararlanırız. 6 sağlam ürünü seçmenin toplam 462 yolu olduğunu ve beş sağlam, bir kusurlu ürünü seçmenin 1848 yolu olduğunu biliyoruz. Böylece toplama yoluyla sayma kuralını kullanır, bu sonuçları toplar ve istediğimiz sonucu, yani en fazla bir kusurlu ürün olan seçimlerin sayısını buluruz (= ya hiç kusurlu ürün yok ya da tam olarak bir tane var). Sonuç: 462 + 1848 = 2310.

Bölümler: Kombinatorik, r’li Permütasyon, Permütasyon, Kombinasyon, Tekrarlı Dizilişler, Tekrarlı Kombinasyon, Kaç Farklı PIN Vardır?

« Önceki: Permütasyon

Sonraki: Tekrarlı Dizilişler »