KPSS A İstatistik Sayma Yöntemleri ve Kombinatorik konu anlatımı

Olasılık hesaplarının büyük bölümü, eşit olasılıklı sonuçlardan oluşan bir örnek uzayda "istenen durum sayısı / tüm durumların sayısı" oranına dayanır. Bu nedenle sonuçları tek tek yazmadan saymak gerekir. Sayma yöntemleri (kombinatorik) bu işin araç kutusudur: toplama ve çarpma ilkeleri, permütasyon (sıralı seçim), kombinasyon (sırasız seçim), tekrarlı permütasyon ve kombinasyon, binom ve çok terimli (multinom) açılım ile içerme-dışarma ilkesi.

Soruyu çözmeye başlamadan önce iki şeyi netleştirmek gerekir:

• Sıra önemli mi? (Başkan–yardımcı seçimi: evet; komisyon seçimi: hayır)
• Tekrar/iade var mı, nesneler özdeş mi? (Rakamlar tekrar edebilir mi, toplar özdeş mi, kutular farklı mı?)

Bu iki soruya verilen cevap hangi formülün kullanılacağını belirler.

Toplama ve çarpma ilkeleri

• Toplama ilkesi: Bir iş, ayrık (aynı anda gerçekleşemeyen) k yoldan biriyle yapılabiliyorsa ve bu yolların sırasıyla n1, n2, …, nk seçeneği varsa toplam seçenek sayısı n1 + n2 + … + nk'dır.
• Çarpma ilkesi: Bir iş art arda k aşamada yapılıyor ve i'inci aşamada (öncekilerden bağımsız olarak) ni seçenek varsa toplam seçenek sayısı n1 · n2 · … · nk'dır.

Permütasyon (sıralı diziliş)

• n farklı nesnenin tamamının sıralanması: n!
• n farklı nesneden r tanesinin seçilip sıralanması: P(n, r) = n! / (n − r)!

Kombinasyon (sırasız seçim)

• n farklı nesneden r tanesinin sırasız seçimi: C(n, r) = n! / (r! · (n − r)!)
• Özellikler: C(n, r) = C(n, n − r); C(n, 0) = C(n, n) = 1; Pascal özdeşliği C(n, r) = C(n − 1, r − 1) + C(n − 1, r); Σ C(n, r) = 2^n (n elemanlı kümenin alt küme sayısı).
• Permütasyonla ilişki: P(n, r) = r! · C(n, r).
• Vandermonde özdeşliği: C(m + n, r) = Σ C(m, k) · C(n, r − k).

Tekrarlı kombinasyon ve "yıldız–çubuk" yöntemi

• n farklı türden, tekrara izin verilerek r nesnenin sırasız seçimi: C(n + r − 1, r).
• Buna denk olarak x1 + x2 + … + xn = r denkleminin negatif olmayan tamsayı çözüm sayısı C(r + n − 1, n − 1)'dir.
• Pozitif: tamsayı çözüm sayısı (her xi ≥ 1): C(r − 1, n − 1).
• Alt sınırlı durumlarda (xi ≥ ai) önce yi = xi − ai dönüşümü yapılır, sonra formül uygulanır.
• r özdeş nesnenin n farklı kutuya dağıtımı da aynı formülle sayılır.

Farklı nesnelerin farklı kutulara dağıtımı

• r farklı nesne n farklı kutuya (kutu boş kalabilir) n^r biçimde dağıtılır.
• Boş kutu kalmaması isteniyorsa içerme-dışarma uygulanır: Σ (−1)^k · C(n, k) · (n − k)^r (k = 0, …, n).
• n kişiyi büyüklükleri n1, n2, …, nk olan adlandırılmış gruplara ayırma sayısı n!/(n1!·…·nk!); gruplar eşit büyüklükte ve adsız ise eşit gruplar arasındaki sıralama sayısına (m eşit grup için m!) ayrıca bölünür.

Binom ve multinom açılımı

• Binom teoremi: (a + b)^n = Σ C(n, k) · a^(n−k) · b^k, k = 0, 1, …, n. Genel terim T(k+1) = C(n, k) · a^(n−k) · b^k'dır; açılımda n + 1 terim bulunur. Katsayılar toplamı, değişkenlere 1 verilerek bulunur.
• Multinom teoremi: (x1 + … + xk)^n açılımında x1^n1 · … · xk^nk teriminin katsayısı n!/(n1! · … · nk!) (n1 + … + nk = n).

İçerme-dışarma ilkesi

• |A ∪ B| = |A| + |B| − |A ∩ B|
• |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|
• Düzensiz permütasyon (derangement): n nesnenin hiçbirinin kendi yerinde olmadığı dizilişlerin sayısı D(n) = n! · (1 − 1/1! + 1/2! − … + (−1)^n/n!). D(1) = 0, D(2) = 1, D(3) = 2, D(4) = 9, D(5) = 44.

Kafes yolları

Izgarada yalnızca sağa ve yukarı adım atarak (0, 0)'dan (m, n)'ye giden yolların sayısı C(m + n, m)'dir; çünkü m + n adımın hangi m tanesinin "sağ" olacağı seçilir. Belirli bir noktadan geçen yollar çarpma ilkesiyle, geçmeyenler tümleyenle bulunur.

Örnek 1 (tekrarlı permütasyon). "ISTATISTIK" sözcüğünün harfleriyle kaç farklı 10 harfli dizilim yazılabilir?

Harfler: I (3 tane), S (2), T (3), A (1), K (1); toplam 10 harf. Özdeş harfler kendi aralarında yer değiştirdiğinde yeni diziliş oluşmaz: 10! / (3! · 2! · 3!) = 3 628 800 / (6 · 2 · 6) = 3 628 800 / 72 = 50 400.

Örnek 2 (kısıtlı kombinasyon). 10 kişilik bir gruptan 3 kişilik bir komisyon seçilecektir. Belirli iki kişi (Ali ve Banu) aynı komisyonda yer almak istemiyor. Kaç farklı komisyon kurulabilir?

Kısıtsız seçim C(10, 3) = 120'dir. Ali ile Banu'nun birlikte bulunduğu komisyonlarda üçüncü kişi kalan 8 kişiden seçilir: C(8, 1) = 8. Tümleyen yaklaşımıyla 120 − 8 = 112.

Örnek 3 (yıldız–çubuk). x + y + z = 10 denkleminin negatif olmayan ve pozitif tamsayı çözüm sayıları kaçtır?

Negatif olmayan çözümler: 10 yıldız ve 2 çubuk dizilir, C(12, 2) = 66. Pozitif çözümler için x' = x − 1 vb. dönüşümle x' + y' + z' = 7 elde edilir: C(9, 2) = 36 (ya da doğrudan C(10 − 1, 3 − 1) = C(9, 2)).

Örnek 4 (binom katsayısı). (2x − y)^6 açılımında x^4 · y^2 teriminin katsayısı kaçtır?

Genel terim C(6, k) · (2x)^(6−k) · (−y)^k'dir. y'nin kuvveti 2 olmalı: k = 2. Katsayı C(6, 2) · 2^4 · (−1)^2 = 15 · 16 · 1 = 240.