Permütasyon ve Kombinasyon Konu Anlatımı

Konu anlatımı notları

1. Temel Sayma İlkeleri

   Ayrık ve bağımsız durumların modellenmesinde iki temel ilke kullanılır:

   • Toplama Yoluyla Sayma: Ayrık iki işlemden biri $m$ farklı yolla, diğeri $n$ farklı yolla gerçekleşebiliyorsa, bu işlemlerden biri veya diğeri $m + n$ farklı yolla yapılabilir.
   • Çarpma Yoluyla Sayma: Birinci işlem $m$ farklı yolla ve bu işlemin ardından ikinci işlem $n$ farklı yolla gerçekleşiyorsa, bu iki işlem birlikte sırasıyla $m \times n$ farklı yolla yapılabilir.

   Faktöriyel Tanımı

   $n$ bir doğal sayı olmak üzere, $1$'den $n$'ye kadar olan ardışık pozitif tam sayıların çarpımına $n$ faktöriyel denir ve $n!$ biçiminde gösterilir.

   $$n! = n \times (n-1) \times (n-2) \times \dots \times 2 \times 1$$

   Özel olarak; $0! = 1$ ve $1! = 1$ olarak tanımlanır.

   Permütasyon Kavramı

   Permütasyon, sonlu bir kümenin elemanlarının belirli bir sıra gözetilerek dizilişidir. Nesnelerin diziliş sırası değiştikçe elde edilen durumlar farklı birer permütasyon oluşturur.

   Permütasyon Sayısının Hesaplanması

   $n$ elemanlı sonlu bir kümeden seçilen $r$ elemanın sıralı dizilişlerinin sayısı $P(n, r)$ ile gösterilir (burada $0 \le r \le n$):

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

   Tekrarlı Permütasyon

   Toplam $n$ adet nesneden $n_1$ tanesi birinci türden, $n_2$ tanesi ikinci türden ve $n_k$ tanesi $k$. türden özdeş ise bu nesnelerin yan yana diziliş sayısı şu formülle bulunur:

   $$\frac{n!}{n_1! \times n_2! \times \dots \times n_k!}$$

   Kombinasyon Kavramı

   Kombinasyon, sonlu bir kümenin elemanları arasından yapılan sırasız seçimdir. Elemanların seçilme sırası önemli değildir; yalnızca hangi elemanların seçildiği dikkate alınır.

   Kombinasyon Sayısının Hesaplanması

   $n$ elemanlı bir kümenin $r$ elemanlı alt kümelerinin sayısı $C(n, r)$ veya $\binom{n}{r}$ ile gösterilir (burada $0 \le r \le n$):

   $$C(n, r) = \binom{n}{r} = \frac{n!}{r! \times (n - r)!}$$

   Temel Kombinasyon Özellikleri

   • $\binom{n}{0} = \binom{n}{n} = 1$
   • $\binom{n}{1} = \binom{n}{n-1} = n$
   • $\binom{n}{r} = \binom{n}{n-r}$ (Simetri özelliği)
   • $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}$ (Pascal özdeşliği)

   Sıralama ve Seçme Arasındaki Bağlantı

   $n$ elemandan $r$ tanesini seçip sıralamak iki aşamalı düşünülebilir: önce $r$ eleman seçilir, ardından seçilen bu $r$ eleman kendi arasında $r!$ farklı biçimde sıralanır.

   $$P(n, r) = C(n, r) \times r!$$

   Buradan kombinasyon sayısı açıkça türetilebilir:

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

   Problem Çözümünde Ayırt Edici Ölçüt

   • Sıra Önemli ise (Permütasyon): Görev dağılımı (başkan, başkan yardımcısı), şifre oluşturma, yarışma dereceleri, yan yana dizilimler.
   • Sıra Önemsiz ise (Kombinasyon): Komite ya da grup oluşturma, el sıkışma sayıları, geometrik şekil (üçgen, doğru) oluşturma, alt küme seçimi.