Kombinatorik

Sayma İlkeleri

• Toplama ilkesi: Ayrık iki işlemden biri m, diğeri n yolla yapılabiliyorsa bu işlemlerden biri m + n yolla yapılır.
• Çarpma ilkesi: Ardışık iki işlemden ilki m, ikincisi n yolla yapılıyorsa ikisi birlikte m·n yolla yapılır.
• Faktöriyel: n! = n·(n − 1)·…·1; 0! = 1.

Permütasyon (Sıralama)

• n farklı nesnenin r'li sıralamaları: P(n, r) = n!/(n − r)!. Tümünün sıralanışı n!.
• Tekrarlı permütasyon: n nesneden n₁ tanesi aynı, n₂ tanesi aynı… ise n!/(n₁!·n₂!·…). Örnek: "ANKARA" kelimesinin harfleriyle 6!/3! = 120 farklı dizilim.
• Dairesel permütasyon: n farklı nesnenin daire etrafında sıralanışı (n − 1)!; kolye/bilezik gibi ters çevrilebilen dizilimlerde (n − 1)!/2.
• Tekrarlı seçimle sıralama: n elemandan r tanesinin tekrara izin verilerek sıralanışı nʳ.

Kombinasyon (Seçme)

• n farklı nesneden r tanesinin seçimi (sıra önemsiz): 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ⁿ (bir kümenin alt küme sayısı).
• Tekrarlı kombinasyon (yıldızlar ve çubuklar): n türden r nesne tekrarlı seçimi C(n + r − 1, r). x₁ + x₂ + … + xₙ = r denkleminin negatif olmayan tam sayı çözüm sayısı C(r + n − 1, n − 1); pozitif tam sayı çözüm sayısı C(r − 1, n − 1).
• Geometri uygulamaları: n noktadan (üçü doğrusal değil) C(n, 2) doğru ve C(n, 3) üçgen; n kenarlı çokgende köşegen sayısı C(n, 2) − n.

Binom Açılımı

• (a + b)ⁿ = Σ C(n, k)·aⁿ⁻ᵏ·bᵏ (k = 0'dan n'e). Açılımda n + 1 terim vardır; baştan (k + 1). terim C(n, k)aⁿ⁻ᵏbᵏ.
• Katsayılar toplamı: değişkenlere 1 verilerek bulunur. Sabit terim: değişkenin üssünü sıfır yapan terim.
• Pascal üçgeni: Binom katsayılarının üçgensel dizilişi; her sayı üstündeki iki sayının toplamıdır.
• Multinom açılım: (a + b + c)ⁿ'de aᵖbᵠcʳ teriminin katsayısı n!/(p!q!r!), p + q + r = n.

İleri Sayma Teknikleri

• İçerme-dışlama ilkesi: |A ∪ B| = |A| + |B| − |A ∩ B|; |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
• Güvercin yuvası (Dirichlet) ilkesi: n + 1 nesne n kutuya konursa en az bir kutuda en az iki nesne bulunur. Genel hâli: N nesne k kutuya konursa en az bir kutuda ⌈N/k⌉ nesne vardır.
• Dağıtım (düzensizlik / derangement): n nesnenin hiçbiri kendi yerinde olmayacak şekilde dizilişi Dₙ = n!(1 − 1/1! + 1/2! − … + (−1)ⁿ/n!); D₃ = 2, D₄ = 9.
• Özdeş nesnelerin farklı kutulara dağıtımı yıldız-çubuk yöntemiyle; farklı nesnelerin farklı kutulara dağıtımı kⁿ.
• Yineleme bağıntıları: Fibonacci (Fₙ = Fₙ₋₁ + Fₙ₋₂), Hanoi kuleleri (Hₙ = 2Hₙ₋₁ + 1 → 2ⁿ − 1), Catalan sayıları (Cₙ = C(2n, n)/(n + 1); doğru parantezleme, yol sayma).
• Grafik (çizge) teorisi temelleri: Köşe ve kenar; bir çizgede dereceler toplamı kenar sayısının iki katıdır (el sıkışma lemması); Euler yolu (tek dereceli köşe sayısı 0 ya da 2), ağaçlarda kenar sayısı n − 1.