Advanced Counting Techniques

İnklüzyon-Eksklüzyon Prensibi ile İleri Sayma Teknikleri

İleri sayma teknikleri içerisinde sıkça kullanılan Inclusion-Exclusion Principle (İnklüzyon-Eksklüzyon Prensibi), birden fazla kümenin birleşiminin eleman sayısını bulmamıza yardımcı olur. Bu prensibi iki veya üç küme için lise yıllarından beri biliyoruz, ancak daha karmaşık durumlarda da uygulanabilir.

İki Kümenin Birleşimi

İki kümenin birleşiminin eleman sayısını bulmak için aşağıdaki formülü kullanırız:

$$|A \cup B| = |A| + |B| - |A \cap B|$$

Bu formül, $A$ ve $B$ kümelerinin toplam eleman sayısından, ortak elemanlarının sayısını çıkararak birleşimin toplam eleman sayısını verir.

Üç Kümenin Birleşimi

Üç küme için prensip biraz daha genişler:

$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$

Burada:

• Tekli kümelerin eleman sayılarını toplarız: $|A|$, $|B|$, $|C|$.
• İkili kesişimlerin eleman sayılarını çıkarırız: $|A \cap B|$, $|A \cap C|$, $|B \cap C|$.
• Üçlü kesişimin eleman sayısını ekleriz: $|A \cap B \cap C|$.

Bu sistematik yaklaşım, daha fazla küme için de genişletilebilir.

Dört Kümenin Birleşimi

Dört küme için genel formül:

$$\begin{align*} |A_1 \cup A_2 \cup A_3 \cup A_4| &= |A_1| + |A_2| + |A_3| + |A_4| \\ &\quad - \sum_{\substack{i, j=1 \\ i < j}}^{4} |A_i \cap A_j| \\ &\quad + \sum_{\substack{i, j, k=1 \\ i < j < k}}^{4} |A_i \cap A_j \cap A_k| \\ &\quad - |A_1 \cap A_2 \cap A_3 \cap A_4| \end{align*}$$

Bu formülde:

• Tekli kümelerin eleman sayılarını toplarız.
• İkili tüm kesişimleri çıkarırız.
• Üçlü tüm kesişimleri ekleriz.
• Dörtlü kesişimi çıkarırız.

Prensibin Mantığı

Bu prensip, ekle-çıkar mantığı üzerine kuruludur:

• Ekleme: Tekli kümelerin eleman sayılarını ekleriz.
• Çıkarma: İkili kesişimlerin eleman sayılarını çıkarırız.
• Ekleme: Üçlü kesişimlerin eleman sayılarını ekleriz.
• Çıkarma: Dörtlü kesişimlerin eleman sayılarını çıkarırız.

Bu döngü, kümelerin sayısına bağlı olarak devam eder.

Örnek Problem: Bit Dizileri

Elimizde uzunluğu $10$ olan bit dizileri var. Bit dizileri, her bir hanesi $0$ veya $1$ olan dizilerdir. Şimdi bu dizilerle ilgili bazı soruları İnklüzyon-Eksklüzyon Prensibi ve sayma teknikleri ile çözelim.

Soru A

Kaç tane bit dizisi $000$ ile başlar?

Çözüm:

• İlk üç hanenin her biri sabit olarak $0$ olmak zorunda. Yani bu hanelerin birer seçeneği var.
• Kalan $7$ hane için her biri $0$ veya $1$ olabilir, yani her biri için $2$ seçenek var.
• Toplam bit dizisi sayısı:

$$2^7 = 128$$

Soru B

Kaç tane bit dizisi $11$ ile biter?

Çözüm:

• Son iki hanenin her biri sabit olarak $1$ olmak zorunda.
• Kalan $8$ hane için her biri $0$ veya $1$ olabilir, yani her biri için $2$ seçenek var.
• Toplam bit dizisi sayısı:

$$2^8 = 256$$

Soru C

Kaç tane bit dizisi ya $000$ ile başlar ya da $11$ ile biter?

Çözüm:

Bu soruda, $A$ kümesini $000$ ile başlayan bit dizileri, $B$ kümesini $11$ ile biten bit dizileri olarak tanımlayalım.

• $|A| = 128$ (Soru A'da bulduk)
• $|B| = 256$ (Soru B'de bulduk)

İnklüzyon-Eksklüzyon Prensibi'ni kullanarak toplam sayıyı bulalım:

$$|A \cup B| = |A| + |B| - |A \cap B|$$

$A \cap B$'yi bulalım:

• Hem $000$ ile başlayan hem de $11$ ile biten bit dizileri.
• İlk $3$ hane sabit $0$, son $2$ hane sabit $1$.
• Kalan $5$ hane için her biri $0$ veya $1$ olabilir, yani her biri için $2$ seçenek var.
• $A \cap B$'nin eleman sayısı:

$$2^5 = 32$$

Şimdi formülde yerine koyalım:

$$|A \cup B| = 128 + 256 - 32 = 352$$

Özet

İnklüzyon-Eksklüzyon Prensibi, birden fazla kümenin birleşiminin eleman sayısını bulmak için etkili bir yöntemdir. Prensip, tekli kümelerin eleman sayılarını ekleyip, kesişimlerin eleman sayılarını uygun şekilde çıkarıp ekleyerek toplamı hesaplar. Bu prensibi kullanarak, karmaşık sayma problemlerini sistematik bir şekilde çözebiliriz.