10. Sınıf Sayma Yöntemleri ve Algoritma — Konu Anlatımı

Başkan ve Yardımcı mı, İki Temsilci mi?

6 kişilik bir kulüpte iki ayrı seçim yapılacak.

Birinci soru: Bir başkan ve bir yardımcı seçilecek. Başkan için 6 aday var; başkan belli olunca yardımcı için 5 kişi kalır. $6 \cdot 5 = 30$ farklı sonuç.

İkinci soru: Okul meclisine iki temsilci gönderilecek. İlk akla gelen yine $6 \cdot 5 = 30$. Ama Ayşe-Mert seçimi ile Mert-Ayşe seçimi aynı iki kişilik gruptur; temsilcilerin sırası yok. Her grup iki kez sayılmış: $\dfrac{30}{2} = 15$.

Fark tek bir soruda: sıra önemli mi? Görev farklıysa (başkan ≠ yardımcı) sıra önemlidir ve buna permütasyon denir. Görev aynıysa sıra önemsizdir; buna kombinasyon denir:

$P(n, r) = \dfrac{n!}{(n - r)!} \qquad C(n, r) = \dfrac{n!}{r!\,(n - r)!}$

$P(6, 2) = 30$ ve $C(6, 2) = 15$. Bölünen $2! = 2$, iki kişinin kendi arasındaki sıralamalarının sayısıdır.

"Ve" Çarpar, "Ya da" Toplar

4 üst ve 3 alt giysiden bir takım seçmek, bir üst ve bir alt seçmektir: $4 \cdot 3 = 12$. İki şehir arasında 5 otobüs ve 3 tren seferi varsa yolculuk otobüsle ya da trenle yapılır: $5 + 3 = 8$.

A'dan B'ye 3, B'den C'ye 4 yol varsa B üzerinden A'dan C'ye $3 \cdot 4 = 12$ yol vardır; çünkü iki etabın ikisi de yürünür. 5 kız ve 4 erkekten bir kız ve bir erkek seçmek $5 \cdot 4 = 20$ yoldur.

4 rakamla (0 hariç), rakam tekrarına izin verilerek 3 basamaklı sayı yazılırsa her basamağa 4 seçenek düşer: $4^3 = 64$. Tekrar yasak olsaydı $4 \cdot 3 \cdot 2 = 24$ olurdu.

Faktöriyel ve Masanın Etrafı

$n!$, 1'den $n$'e kadar sayıların çarpımıdır; $5! = 120$. KİTAP sözcüğünün farklı beş harfi $5! = 120$ biçimde sıralanır. Faktöriyelli bölmede sadeleştirme hesabı kısaltır: $\dfrac{7!}{5!} = 7 \cdot 6 = 42$.

6 kişiden 3'ünü sıraya dizmek $P(6, 3) = 6 \cdot 5 \cdot 4 = 120$; yalnız seçmek $C(6, 3) = \dfrac{120}{3!} = 20$ yoldur.

5 kişi yuvarlak bir masaya oturursa? Düz sırada 120 dizilim var, ama masayı döndürmek oturuşu değiştirmez: her oturuş 5 kez sayılmış. $\dfrac{5!}{5} = 4! = 24$. Kural: $(n - 1)!$.

Aynı Harfler Ayırt Edilemez

ANNE sözcüğünde iki N var. İki N'nin yerini değiştirmek yeni bir sözcük üretmez; bu yüzden $4!$ sonucu $2!$'ye bölünür: $\dfrac{24}{2} = 12$.

Daha uzun bir örnek: KELEBEK. 7 harf; E üç kez, K iki kez geçiyor.

$\dfrac{7!}{3! \cdot 2!} = \dfrac{5040}{12} = 420$

Sık yapılan hata: Üç kişiden ikisinin seçileceği bir soruda $3 \cdot 2 = 6$ bulmak. Bu sayı sıralı seçimi verir; seçimde AB ile BA aynı olduğundan cevap 3'tür. Aynı hata tokalaşmada da yapılır: 8 kişinin birer kez tokalaşması $8 \cdot 7 = 56$ değil, $C(8, 2) = 28$'dir, çünkü Ali'nin Can'la tokalaşması Can'ın Ali'yle tokalaşmasıdır.

"En Az" Görünce Tümleyeni Düşün

5 kişilik gruptan en az 4 kişilik takım kaç türlü kurulur? "En az 4" demek 4 ya da 5 demek: $C(5, 4) + C(5, 5) = 5 + 1 = 6$.

4 kişiden en az biri seçilecekse her kişi için "seçilir / seçilmez" iki seçenek var: $2^4 = 16$. İçinden hiç kimsenin seçilmediği 1 durum çıkarılır: $16 - 1 = 15$.

Ters yönde bir soru: $C(n, 2) = 15$ ise $n$ kaçtır? $\dfrac{n(n - 1)}{2} = 15$, yani $n(n - 1) = 30 = 6 \cdot 5$ ve $n = 6$. Kulüp örneğindeki 15 temsilci ikilisi buydu.

Binom Açılımında Katsayılar

$(a + b)^n$ açılımının katsayıları kombinasyonlardır: $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$. Katsayılar 1, 4, 6, 4, 1 Pascal üçgeninin 4. satırıdır ve $n + 1 = 5$ terim vardır.

$(x + 2)^5$ açılımında $x^3$'lü terim: genel terim $\binom{5}{r} x^{5 - r} 2^r$ ve $5 - r = 3$ için $r = 2$. Terim $\binom{5}{2} \cdot 4 \cdot x^3 = 40x^3$. Katsayılar toplamı için $x = 1$ yazılır: $3^5 = 243$.

Bir Akış Şemasını Adım Adım İzlemek

Şema: $n \leftarrow 5$, $s \leftarrow 1$; $n > 1$ olduğu sürece $s \leftarrow s \cdot n$ ve $n \leftarrow n - 1$; bitince $s$ yazdırılır. Ne yazar? Tahmin etmek yerine bir izleme tablosu tutalım:

$n = 1$ olunca döngü durur ve 120 yazılır: algoritma $5!$'i hesaplamıştır.

Algoritmalar adım sayısıyla da karşılaştırılır. 1.000 isimlik sıralı bir listede baştan tek tek bakmak 1.000 adıma kadar sürebilir. Her adımda listenin yarısını eleyen ikili arama en fazla 10 adımda biter, çünkü $2^{10} = 1024$.

Sınav ipucu: Soruda "sıralama", "dizilim", "başkan-yardımcı" gibi görev farkı varsa permütasyon; "grup", "takım", "temsilci", "tokalaşma" varsa kombinasyon. Şıklarda iki sayıdan biri ötekinin $r!$ katıysa soru tam olarak bu farkı ölçüyordur.

Sık sorulanlar