Saymaya giriş ve güvercin yuvası ilkesi

Bu hafta sayma (counting) başlıyor. Bu dönemin vizesinde yok, final konusu. Ama kombinatorik sınavda en çok puanın döndüğü yerlerden biri, çünkü sorular kısa ve cevap tek sayı. Mesele hangi kuralı uygulayacağını doğru seçmek. Altın kurallar:

1. “Ve” çarpılır, “veya” toplanır (seçenekler çakışmıyorsa).
2. Çakışma varsa içerme-dışlama: iki kere saydığını bir kere çıkar.
3. “En az bir” sorusu tümleyenle çözülür: hepsi eksi hiç olmayanlar.
4. Sıra önemliyse permütasyon, önemsizse kombinasyon. Her soruda kendine sor: “AB ile BA farklı mı?”
5. Güvercin yuvasında kutuyu ve nesneyi açıkça adlandır. Yarı puan o cümlede.

Temel sayma kuralları

Çarpım kuralı (product rule)

Bir iş art arda iki adımda yapılıyorsa, birinci adım $n_1$, ikinci adım (her durumda) $n_2$ yoldan yapılabiliyorsa iş $n_1 \cdot n_2$ yoldan yapılır.

Örnek: 3 başlangıç, 4 ana yemek, 2 tatlıdan bir menü: $3 \cdot 4 \cdot 2 = 24$ menü. Ağaç diyagramı (tree diagram) çizsen 24 yaprak çıkar.

Çarpım kuralının en önemli sonuçları:

• $n$ uzunluklu bit dizisi: $2^n$.
• $m$ elemanlı kümeden $n$ elemanlı kümeye fonksiyon: her eleman için $n$ seçenek, $n^m$.
• $n$ elemanlı kümenin alt kümeleri: her eleman ya içeride ya dışarıda, $2^n$ (hafta 4’teki kuvvet kümesi).

Toplam kuralı (sum rule)

İş ya birinci yoldan ($n_1$ seçenek) ya ikinci yoldan ($n_2$ seçenek) yapılıyorsa ve ortak seçenek yoksa: $n_1 + n_2$. Örnek: proje A listesinde 12, B listesinde 9 konu var, ortak konu yok. Bir konu seçmenin $12 + 9 = 21$ yolu var.

Çıkarma kuralı (inclusion-exclusion)

Ortak seçenek varsa iki kere sayarsın, bir kere çıkarırsın:

$\lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert.$

Örnek. 7 bitlik dizilerden kaç tanesi 1 ile başlar veya 00 ile biter?

1 ile baslayan:          kalan 6 bit serbest  -> 2^6 = 64
00 ile biten:            kalan 5 bit serbest  -> 2^5 = 32
ikisi birden (1....00):  ortadaki 4 bit       -> 2^4 = 16
Toplam: 64 + 32 - 16 = 80

“En az bir” ve tümleyen

Örnek. 4 karakterli şifre, karakterler büyük harf (26) veya rakam (10). En az bir rakam içeren kaç şifre var?

Doğrudan saymak dağınık (bir rakam, iki rakam, …). Tümleyen ile:

$\underbrace{36^4}_{\text{all}} - \underbrace{26^4}_{\text{no digit}} = 1679616 - 456976 = 1222640.$

TUZAK · “en az bir”i çarpım kuralıyla yapmak. “Bir pozisyonu rakam yap (4 yol), o pozisyona 10 rakam, kalan 3 pozisyon 36” diye $4 \cdot 10 \cdot 36^3$ hesaplamak yanlış: iki rakamlı şifreleri birden fazla sayar. Tümleyen yöntemi her zaman güvenli.

Bölme kuralı (division rule)

Her sonucu tam $d$ kez sayıyorsan, toplamı $d$‘ye bölersin. Örnek: 5 kişi yuvarlak masada. Düz sırada $5! = 120$, ama döndürmeler aynı oturuş sayılır, her oturuş 5 kez sayıldı: $120/5 = 24$.

Güvercin yuvası ilkesi (pigeonhole principle)

İlke. $k$ kutuya $k + 1$ (veya daha fazla) nesne koyarsan, en az bir kutuda en az iki nesne olur.

Proof. Suppose, for contradiction, that k + 1 objects are placed
into k boxes and no box contains more than one object.
Then the total number of objects is at most k * 1 = k.
This contradicts having k + 1 objects. Hence some box contains
at least two objects. ∎

Genelleştirilmiş ilke. $N$ nesneyi $k$ kutuya koyarsan, bir kutuda en az $\lceil N/k \rceil$ nesne vardır.

Örnek: 40 öğrencilik sınıfta en az $\lceil 40/12 \rceil = 4$ kişi aynı ayda doğmuştur. Gerekçe: her ayda en fazla 3 kişi olsaydı toplam en fazla $12 \cdot 3 = 36 < 40$.

“Garanti için en az kaç tane?” soruları

Tarif: en kötü durumu kur, bir ekle. Not 5 harf (A, B, C, D, F). Aynı notu alan 5 öğrenci garanti olsun diye sınıf en az kaç kişi olmalı? En kötü durum: her nottan 4 kişi, $5 \cdot 4 = 20$ kişi ve henüz 5 aynı yok. Bir kişi daha: $21$.

Genel kalıp: $k$ kutu, $r$ tane aynı istiyorsan cevap $k(r-1) + 1$.

İPUCU · kutuyu doğru seç. Soru “farkı 4’e bölünen iki sayı” diyorsa kutular mod 4 kalanlardır. “Toplamı 10 olan iki sayı” diyorsa kutular $\{1, 9\}, \{2, 8\}, \dots$ çiftleridir. Kutuyu bulduğun an soru biter.

Permütasyon ve kombinasyon

Permütasyon (r-permutation): $n$ farklı nesneden $r$ tanesini sıralı dizmek.

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

Kombinasyon (r-combination): $n$ farklı nesneden $r$ tanesini sırasız seçmek (alt küme).

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

Bağlantı: $P(n, r) = C(n, r) \cdot r!$. Önce hangi $r$ nesne (kombinasyon), sonra onları kaç türlü dizeceğin ($r!$).

$C(n, r) = C(n, n - r)$: 4 kişiyi seçmek, dışarıda kalacak 6 kişiyi seçmekle aynı iş.

İPUCU · faktöriyeli elle sadeleştir. Hesap makinesi yok. $C(10,4)$ için $10!$‘i hesaplama: $\frac{10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1}$ yaz, önce sadeleştir. $8 / (4 \cdot 2) = 1$, $9 / 3 = 3$, geriye $10 \cdot 3 \cdot 7 = 210$ kalır. Payda her zaman tam bölünür, çünkü sonuç bir sayımdır.

Çözümlü örnek: kısıtlı sıralama

6 kişi sıraya giriyor, A ile B yan yana olmalı.

1) A ve B'yi tek blok yap: [AB] + 4 kisi = 5 nesne
2) 5 nesneyi sirala: 5! = 120
3) Blok icinde AB veya BA: 2
4) Carpim kurali: 2 * 120 = 240

“Yan yana olmasın” diye sorarsa tümleyen: $6! - 240 = 720 - 240 = 480$.

Hangi kural? Karar sırası

Soruyu okuyunca şu sırayla kendine sor:

1. Kaç adımda kuruluyor? Art arda adımlar varsa çarpım kuralı.
2. Ayrı durumlar mı var? “Ya şu ya bu” diye bölünüyorsa her durumu ayrı say, topla.
3. Durumlar çakışıyor mu? Çakışıyorsa kesişimi çıkar.
4. “En az”, “en fazla” kelimesi var mı? Tümleyen genelde daha kısa.
5. Seçilenlerin sırası önemli mi? Önemliyse $P$, değilse $C$.

Çözümlü örnek. $\{1, 2, \dots, 10\}$ kümesinin 5 elemanlı alt kümelerinden kaç tanesi 1’i veya 2’yi içerir?

Tum 5 elemanli alt kumeler:          C(10,5) = 252
Ne 1 ne 2 iceren (kalan 8'den 5):    C(8,5)  = 56
En az birini iceren (tumleyen):      252 - 56 = 196

Aynı cevabı içerme-dışlamayla da bul: 1’i içeren $C(9,4) = 126$, 2’yi içeren $126$, ikisini de içeren $C(8,3) = 56$. $126 + 126 - 56 = 196$. İki yoldan aynı sayı çıkıyorsa güvenle yaz. Sınavda vaktin varsa bu çapraz kontrolü yap.

Sık yapılan hatalar