Dahil Etme - Hariç Tutma Prensibi

Dahil etme - hariç tutma prensibi (bir diğer adıyla içerme - dışlama prensibi), \( n \) tane kümenin birleşim kümesinin eleman sayısını bulurken bu kümelerin kesişim kümelerindeki elemanların birden fazla kez sayılmasının önüne geçen bir sayma yöntemidir.

İki Kümeli Durum

Dahil etme-hariç tutma prensibinin nasıl çalıştığını en basit haliyle iki kümenin kesişimi üzerinden anlatabiliriz.

İki kümenin birleşim kümesinin eleman sayısını bulma
İki kümenin birleşim kümesinin eleman sayısını bulma

Yukarıdaki gibi ayrık olmayan iki kümenin birleşim kümesinin eleman sayısını aşağıdaki formülle hesaplayabiliriz.

Formülde kümelerin eleman sayılarının toplamından kesişim kümesinin eleman sayısını çıkarmamızın sebebi, kesişim kümesinin iki kümede ortak olması ve her iki kümenin eleman sayılarının kesişim kümesindeki elemanları içermesidir. Bu yüzden bu çıkarma işlemi kesişim kümesinin iki kez sayılmasının önüne geçmektedir.

Üç Kümeli Durum

Üç kümenin birleşim kümesinin eleman sayısını bulma
Üç kümenin birleşim kümesinin eleman sayısını bulma

Yukarıdaki gibi ayrık olmayan üç kümenin birleşim kümesinin eleman sayısını aşağıdaki formülle hesaplayabiliriz.

Bu formülde de iki kümeli duruma benzer şekilde kümelerin eleman sayılarının toplamından ikili kesişim kümelerinin eleman sayılarını çıkarırız, ancak üçlü kesişim kümesinin eleman sayısını en sonda işleme tekrar ekleriz. Bunun sebebini aşağıdaki gibi açıklayabiliriz.

İşlemin ilk kısmında üç kümenin eleman sayılarını topladığımızda her yeşil bölgeyi toplama ikişer kez, mavi bölgeyi ise üç kez dahil etmiş oluruz. İkili kesişim kümelerini bu toplamdan çıkardığımızda yeşil bölgelerin eleman sayısını formüle doğru yansıtmış oluruz, ancak mavi bölgeyi formülden üç kez çıkarmış oluruz, dolayısıyla mavi bölge toplama hiç yansımamış olur. Bu yüzden işlemin en sonunda mavi bölgeye karşılık gelen üçlü kesişim kümesini formüle tekrar eklememiz gerekir.

n Kümeli Durum

Bu yöntemi \( n \) kümeli duruma aşağıdaki adımları takip ederek uygulayabiliriz.

  • \( (+) \) Kümelerin ayrı ayrı eleman sayılarını topla (dahil et).
  • \( (-) \) İkili kesişim kümelerini çıkar (hariç tut).
  • \( (+) \) Üçlü kesişim kümelerini topla (dahil et).
  • \( (-) \) Dörtlü kesişim kümelerini çıkar (hariç tut).
  • \( (+) \) Beşli kesişim kümelerini topla (dahil et).
  • Bu işlemi \( n \) kümenin kesişimine kadar tekrarla.

Yöntemi özetlemek gerekirse, kümelerin ayrı ayrı eleman sayılarına tek sayıda kümeden oluşan kesişim kümelerinin eleman sayıları eklenir, çift sayıda kümeden oluşan kesişim kümelerinin eleman sayıları çıkarılır.

Bu yöntemin \( n \) küme için genel formülü aşağıdaki gibidir.

Dahil Etme - Hariç Tutma Prensibinin Uygulamaları

Bu bölümde bu prensibin üç uygulamasını birer örnek üzerinden inceleyeceğiz.

Birleşim Kümesinin Eleman Sayısı

Dahil etme - hariç tutma prensibini 2 kümeli duruma uygulayarak soruyu çözebiliriz.

\( I \): İngilizce konuşan öğrencilerin kümesi

\( A \): Almanca konuşan öğrencilerin kümesi

\( s(I) = 25 \)

\( s(A) = 16 \)

\( s(I \cap A) = 9 \)

Bu bilgileri 2 kümeli durum için olan formülde yerine koyalım.

\( s(I \cup A) = s(I) + s(A) \) \( - s(I \cap A) \)

\( = 25 + 16 - 9 = 32 \) bulunur.

Bölünebilme Problemleri

Dahil etme - hariç tutma prensibini 3 kümeli duruma uygulayarak soruyu çözebiliriz.

2'ye, 3'e ve 5'e bölünebilen sayıları birer küme olarak tanımlayalım.

2'ye, 3'e ve 5'e tam bölünen sayılar
2'ye, 3'e ve 5'e tam bölünen sayılar

\( E \): 1-1000 arasındaki pozitif tam sayılar (1-1000)

\( A_2 \): 2'ye tam bölünebilen sayılar kümesi

\( A_3 \): 3'e tam bölünebilen sayılar kümesi

\( A_5 \): 5'e tam bölünebilen sayılar kümesi

\( A_2 \cap A_3 \): 2'ye VE 3'e tam bölünebilen sayılar (5'e bölünebilmesinden bağımsız)

\( A_2 \cap A_5 \): 2'ye VE 5'e tam bölünebilen sayılar (3'e bölünebilmesinden bağımsız)

\( A_3 \cap A_5 \): 3'e VE 5'e tam bölünebilen sayılar (2'ye bölünebilmesinden bağımsız)

\( A_2 \cap A_3 \cap A_5 \): 2'ye VE 3'e VE 5'e tam bölünebilen sayılar

1-1000 arasında 2'ye bölünebilen 500 sayı vardır.

\( s(A_2) = 500 \)

1-1000 arasında 3'e bölünebilen 333 sayı vardır.

\( s(A_3) = 333 \)

1-1000 arasında 5'e bölünebilen 200 sayı vardır.

\( s(A_5) = 200 \)

2'ye ve 3'e aynı anda bölünebilen sayılar EKOK'ları olan 6'ya da tam bölünür. 1-1000 arasında 6'ya bölünebilen 166 sayı vardır.

\( s(A_2 \cap A_3) = 166 \)

2'ye ve 5'e aynı anda bölünebilen sayılar EKOK'ları olan 10'a da tam bölünür. 1-1000 arasında 10'a bölünebilen 100 sayı vardır.

\( s(A_2 \cap A_5) = 100 \)

3'e ve 5'e aynı anda bölünebilen sayılar EKOK'ları olan 15'e de tam bölünür. 1-1000 arasında 15'e bölünebilen 66 sayı vardır.

\( s(A_3 \cap A_5) = 66 \)

2'ye, 3'e ve 5'e aynı anda bölünebilen sayılar EKOK'ları olan 30'a da tam bölünür. 1-1000 arasında 30'a bölünebilen 33 sayı vardır.

\( s(A_2 \cap A_3 \cap A_5) = 33 \)

Bu bilgileri 3 kümeli durum için olan formülde yerine koyalım.

\( s(A_2 \cup A_3 \cup A_5) \) \( = s(A_2) + s(A_3) + s(A_5) \) \( - s(A_2 \cap A_3) \) \( - s(A_2 \cap A_5) \) \( - s(A_3 \cap A_5) \) \( + s(A_2 \cap A_3 \cap A_5) \)

\( = 500 + 333 + 200 \) \( - 166 - 100 \) \( - 66 + 33 = 734 \) bulunur.

Örten Fonksiyon Sayısı

Verilen bir tanım ve değer kümesi arasında tanımlanabilecek örten fonksiyon sayısı aşağıdaki şekilde hesaplanır.

\( f: A \to B \)

\( s(A) = m, \quad s(B) = n \) olmak üzere,

Tanımlanabilecek örten fonksiyon sayısı \( = \begin{cases} 0 & m \lt n \\ n! & m = n \\ \sum_{r = 1}^{n} (-1)^{n - r} \cdot C(n, r) \cdot r^m & m \gt n \end{cases} \)

Buna göre dahil etme - hariç tutma prensibi, tanım kümesinin eleman sayısının değer kümesinin eleman sayısından fazla olduğu üçüncü durumda karşımıza çıkmaktadır. Yukarıdaki formülü bu soruya \( r = n \) ile başlayarak \( r = 1 \)'e doğru uygulayalım.

  • \( (+) \) \( A \) kümesinden \( B \) kümesine yazılabilecek tüm fonksiyonların sayısını topla (\( C(n, n) \cdot (n)^m \)).
  • \( (-) \) \( A \) kümesinin elemanlarının \( B \) kümesinin üç elemanı ile eşleştiği fonksiyonları çıkar (\( C(n, n - 1) \cdot (n - 1)^m \)).
  • \( (+) \) \( A \) kümesinin elemanlarının \( B \) kümesinin iki elemanı ile eşleştiği fonksiyonları topla (\( C(n, n - 2) \cdot (n - 2)^m \)).
  • \( (-) \) \( A \) kümesinin elemanlarının \( B \) kümesinin bir elemanı ile eşleştiği fonksiyonları çıkar (\( C(n, n - 3) \cdot (n - 3)^m \)).

Yukarıdaki her durumu hesaplayalım.

\( s(A) = m = 5, \quad s(B) = n = 4 \)

\( C(4, 4) \cdot 4^5 = 1 \cdot 1024 = 1024 \)

Yukarıdaki formülü \( B \) kümesinin elemanları içinden 4 eleman \( C(4, 4) \) farklı şekilde seçilebilir, \( A \) kümesinin 5 elemanından bu 4 elemana \( 4^5 \) farklı fonksiyon tanımlanabilir şeklinde yorumlayabiliriz. Burada dikkat edilmesi gereken husus, bu adımda elde ettiğimiz sonuç aşağıda hesaplayacağımız \( B \) kümesinin görüntü kümesinin 1, 2 ya da 3 elemanlı olduğu fonksiyonları da içermektedir.

\( C(4, 3) \cdot 3^5 = 4 \cdot 243 = 972 \)

Yukarıdaki formülü \( B \) kümesinin elemanları içinden 3 eleman \( C(4, 3) \) farklı şekilde seçilebilir, \( A \) kümesinin 5 elemanından bu 3 elemana \( 3^5 \) farklı fonksiyon tanımlanabilir şeklinde yorumlayabiliriz. Bu adımda elde ettiğimiz sonuç aşağıda hesaplayacağımız \( B \) kümesinin görüntü kümesinin 1 ya da 2 elemanlı olduğu fonksiyonları da içermektedir.

\( C(4, 2) \cdot 2^5 = 6 \cdot 32 = 192 \)

Yukarıdaki formülü \( B \) kümesinin elemanları içinden 2 eleman \( C(4, 2) \) farklı şekilde seçilebilir, \( A \) kümesinin 5 elemanından bu 2 elemana \( 2^5 \) farklı fonksiyon tanımlanabilir şeklinde yorumlayabiliriz. Bu adımda elde ettiğimiz sonuç aşağıda hesaplayacağımız \( B \) kümesinin görüntü kümesinin 1 elemanlı olduğu fonksiyonları da içermektedir.

\( C(4, 1) \cdot 1^5 = 4 \cdot 1 = 4 \)

Yukarıdaki formülü \( B \) kümesinin elemanları içinden 1 eleman \( C(4, 1) \) farklı şekilde seçilebilir, \( A \) kümesinin 5 elemanından bu 1 elemana \( 1^5 \) farklı fonksiyon tanımlanabilir şeklinde yorumlayabiliriz.

Bu değerleri formülde yerine koyalım.

Örten fonksiyon sayısı \( = 1024 - 972 + 192 - 4 = 240 \)

Buna göre \( A \) kümesinden \( B \) kümesine tanımlanabilecek örten fonksiyon sayısı 240 olur.


« Önceki
Güvercin Yuvası Prensibi
Ana Sayfa »
Konu Tamamlandı!


Faydalı buldunuz mu?   Evet   Hayır