ÖABT Lise Mat. Kombinatorik konu anlatımı

Kombinatorik, sonlu kümelerde "kaç farklı yol vardır?" sorusunu sistematik biçimde yanıtlayan sayma matematiğidir. ÖABT Lise Matematik sınavında kombinatorik soruları lise müfredatındaki permütasyon–kombinasyonun ötesine geçer: tekrarlı permütasyon, dairesel permütasyon, özdeş nesnelerin dağıtımı (yıldız–çubuk), içerme–dışarma (kapsama–dışlama) ilkesi, düzensizlikler (derangement), örten fonksiyon sayısı, güvercin yuvası (çekmece) ilkesi, binom ve multinom katsayıları, Stirling ve Catalan sayıları, yinelemeli sayma gibi konular sıkça sorulur.

Temel sayma ilkeleri

Permütasyonlar

• n farklı nesnenin r'li sıralaması: P(n, r) = n!/(n − r)!
• Tekrarlı permütasyon: n nesneden n₁, n₂, …, nₖ tanesi kendi aralarında özdeş ise n!/(n₁!·n₂!·…·nₖ!).
• Dairesel permütasyon: n farklı nesne yuvarlak masada (n − 1)! şekilde; dönme ve yansıma özdeş sayılırsa (n − 1)!/2 (ör. kolye).
• Belirli nesnelerin yan yana olması: Bu nesneler tek blok sayılır, blok içi sıralamalarla çarpılır.
• Belirli k nesnenin kendi aralarında belirli bir sırada olması: n!/k!.

Kombinasyonlar ve binom

• C(n, r) = n!/(r!(n − r)!); C(n, r) = C(n, n − r); Pascal: C(n, r) = C(n − 1, r − 1) + C(n − 1, r).
• Binom açılımı: (a + b)ⁿ = Σ C(n, k) aⁿ⁻ᵏ bᵏ; genel terim Tₖ₊₁ = C(n, k) aⁿ⁻ᵏ bᵏ.
• Multinom: (a + b + c)ⁿ açılımında aᵖbᵍcʳ (p + q + r = n) katsayısı n!/(p!q!r!).
• Özdeşlikler: Σ C(n, k) = 2ⁿ; Vandermonde: Σ C(m, k)C(n, r − k) = C(m + n, r), özel olarak Σ C(n, k)² = C(2n, n).
• Ardışık iki eleman içermeyen k elemanlı alt küme sayısı ({1, …, n} içinde): C(n − k + 1, k).

Özdeş nesnelerin dağıtımı (yıldız–çubuk)

• x₁ + x₂ + … + xₖ = n denkleminin negatif olmayan tam sayı çözüm sayısı C(n + k − 1, k − 1).
• Pozitif: tam sayı çözüm sayısı C(n − 1, k − 1).
• Üst sınır varsa içerme–dışarma uygulanır.

İçerme–dışarma (kapsama–dışlama) ilkesi

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

Genel hâlde tekli kesişimler toplanır, ikililer çıkarılır, üçlüler eklenir, … Uygulamaları:

Güvercin yuvası (çekmece) ilkesi

• n + 1 nesne n kutuya yerleştirilirse en az bir kutuda en az 2 nesne bulunur.
• Genelleştirilmiş: kn + 1 nesne n kutuya yerleştirilirse bir kutuda en az k + 1 nesne bulunur.
• Sorularda "kutuların" doğru kurulması (ör. toplamı sabit olan sayı çiftleri, kalan sınıfları) anahtar adımdır.

Özel sayılar ve yinelemeler

• Catalan sayıları: Cₙ = C(2n, n)/(n + 1): 1, 1, 2, 5, 14, 42, … Dengeli parantez dizileri, köşegeni aşmayan kafes yolları, (n + 2)-genin üçgenlemeleri.
• Kafes yolları: (0, 0)'dan (a, b)'ye sağ/yukarı adımlarla C(a + b, a) yol.
• 2 × n tahtanın 1 × 2 dominolarla döşenmesi: aₙ = aₙ₋₁ + aₙ₋₂ (Fibonacci).
• 2n kişinin sırasız n ikiliye ayrılması: (2n)!/(2ⁿ·n!).

Örnek 1. "ANKARA" kelimesinin harfleri kaç farklı şekilde sıralanır?

Çözüm: 6 harfte A üç kez tekrar eder: 6!/3! = 120.

Örnek 2. 1'den 100'e kadar olan sayılardan kaç tanesi 2, 3 ya da 5'e bölünür?

Çözüm: |2| = 50, |3| = 33, |5| = 20; |6| = 16, |10| = 10, |15| = 6; |30| = 3. Toplam 50 + 33 + 20 − 16 − 10 − 6 + 3 = 74.

Örnek 3. 4 farklı mektup 4 zarfa, hiçbiri kendi zarfına girmeyecek şekilde kaç yolla konur?

Çözüm: D₄ = 4!(1 − 1 + 1/2 − 1/6 + 1/24) = 24 − 24 + 12 − 4 + 1 = 9.

Örnek 4. x + y + z = 7 denkleminin x, y, z ≥ 1 koşuluyla kaç tam sayı çözümü vardır?

Çözüm: Pozitif çözüm sayısı C(7 − 1, 3 − 1) = C(6, 2) = 15. (Alternatif: x = x' + 1 gibi dönüşümle x' + y' + z' = 4, C(6, 2) = 15.)