ÖABT İlköğretim Mat. Kombinatorik konu anlatımı

Kombinatorik, sonlu kümelerde sayma problemleriyle ilgilenen matematik dalıdır. ÖABT İlköğretim Matematik sınavında toplama ve çarpma ilkeleri, permütasyon, tekrarlı permütasyon, dairesel permütasyon, kombinasyon, binom ve multinom açılımı, özdeş nesnelerin dağıtımı (yıldız-çubuk yöntemi), içerme-dışlama ilkesi, güvercin yuvası ilkesi, düzensizlik (derangement), örten fonksiyon sayısı, Stirling sayıları, Catalan sayıları ve yineleme bağıntıları sorulur.

Kombinatorikte başarının anahtarı, problemi doğru modele oturtmaktır: Sıra önemli mi? Nesneler özdeş mi, farklı mı? Kutular özdeş mi, farklı mı? Boş kutu olabilir mi? Bu dört sorunun cevabı hangi formülün kullanılacağını belirler.

Sayma ilkeleri

Permütasyon ve kombinasyon

• n farklı nesnenin sıralanışı: n!.
• n nesneden r tanesinin sıralı seçimi: P(n, r) = n! / (n − r)!.
• Tekrarlı permütasyon: n₁, n₂, …, nₖ tane özdeş nesne varsa n! / (n₁!·n₂!·…·nₖ!).
• Dairesel permütasyon: n farklı nesne yuvarlak masada (n − 1)! biçimde dizilir; ters yön aynı sayılıyorsa (anahtarlık, kolye) (n − 1)!/2.
• Kombinasyon: C(n, r) = n! / (r!·(n − r)!); C(n, r) = C(n, n − r); Pascal özdeşliği C(n, r) = C(n − 1, r − 1) + C(n − 1, r).

Binom ve multinom

• (a + b)ⁿ = Σ C(n, k)·aⁿ⁻ᵏ·bᵏ (k = 0, …, n).
• Σ C(n, k) = 2ⁿ, Σ k·C(n, k) = n·2ⁿ⁻¹.
• (x₁ + x₂ + … + xₘ)ⁿ açılımında x₁^(a₁)…xₘ^(aₘ) teriminin katsayısı n! / (a₁!·…·aₘ!) olur (a₁ + … + aₘ = n).

Dağıtım problemleri

• n özdeş nesne r farklı kutuya (boş kutu olabilir): C(n + r − 1, r − 1). Bu, x₁ + … + xᵣ = n denkleminin negatif olmayan tam sayı çözüm sayısıdır.
• Her kutuya en az bir nesne: C(n − 1, r − 1) (pozitif tam sayı çözümleri).
• n farklı nesne r farklı kutuya: rⁿ.
• n farklı nesne r farklı kutuya, boş kutu kalmadan (örten fonksiyon sayısı): Σ (−1)ᵏ·C(r, k)·(r − k)ⁿ.
• n farklı nesne r özdeş kutuya, boş kutu kalmadan: Stirling sayısı S(n, r) = (örten fonksiyon sayısı) / r!.

İçerme-dışlama ve güvercin yuvası

• |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
• Düzensizlik: Dₙ = n!·(1 − 1/1! + 1/2! − … + (−1)ⁿ/n!). D₁ = 0, D₂ = 1, D₃ = 2, D₄ = 9, D₅ = 44.
• Güvercin yuvası: n yuvaya kn + 1 nesne konursa en az bir yuvada k + 1 nesne bulunur.

Özel sayılar ve yinelemeler

• Catalan sayısı: Cₙ = C(2n, n)/(n + 1): 1, 1, 2, 5, 14, 42, … Köşegeni aşmayan kafes yolları, geçerli parantezleme sayıları Catalan sayılarıdır.
• Ardışık iki 1 içermeyen n uzunluklu ikili dizilerin sayısı aₙ = aₙ₋₁ + aₙ₋₂ (a₁ = 2, a₂ = 3) yinelemesini sağlar.