Dahil Etme - Hariç Tutma Prensibi
Dahil etme - hariç tutma prensibi (bir diğer adıyla içerme - dışlama prensibi); iki ya da daha fazla kümenin birleşim kümesinin eleman sayısını, bu kümelerin kesişim kümelerindeki elemanların birden fazla kez sayılmasının önüne geçerek hesaplayan bir sayma yöntemidir.
İki Kümenin Birleşimi
Ayrık olmayan iki kümenin birleşiminin eleman sayısı, dahil etme - hariç tutma prensibi ile aşağıdaki şekilde hesaplanır.
- Kümelerin eleman sayılarının toplamı alınır (dahil et).
- Kümelerin kesişimi birinci adımda toplama iki kez dahil edildiği için toplamdan çıkarılır (hariç tut).
\( s(A \cup B) = s(A) + s(B) \textcolor{red}{- s(A \cap B)} \)
\( A = \{ 1, 2, 3, 4, 5, 6 \} \)
\( B = \{ 5, 6, 7, 8, 9 \} \)
\( A \cap B = \{ 5, 6 \} \)
\( A \cup B = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9 \} \)
\( s(A) = 6, \quad s(B) = 5 \)
\( s(A \cap B) = 2 \)
\( s(A \cup B) = 6 + 5 \textcolor{red}{- 2} = 9 \)
\( A = \{1, 2, 3 , \ldots, 155\} \) olmak üzere,
\( A \) kümesinin elemanlarından kaçı 2 ve 3 sayılarından hiçbirine tam bölünmez?
\( A \) kümesinin elemanlarından 2'ye tam bölünen sayıların kümesine \( A_2 \) diyelim.
2, 4, 6, ..., 154
\( s(A_2) = \dfrac{154 - 2}{2} + 1 = 77 \)
\( A \) kümesinin elemanlarından 3'e tam bölünen sayıların kümesine \( A_3 \) diyelim.
3, 6, 9, ..., 153
\( s(A_3) = \dfrac{153 - 3}{3} + 1 = 51 \)
Hem 2'ye hem de 3'e bölünen sayılar 6'ya da bölünür.
\( A \) kümesinin elemanlarından 6'ya tam bölünen sayıların kümesi \( A_2 \cap A_3 \) olur (mavi bölge).
6, 12, 18, ..., 150
\( s(A_2 \cap A_3) = \dfrac{150 - 6}{6} + 1 = 25 \)
Soruda istenen \( A_2 \) ve \( A_3 \) kümeleri dışında kalan ve turuncu alana karşılık gelen kümenin eleman sayısıdır. Bu kümeye \( A_x \) diyelim.
\( A_x \) kümesinin eleman sayısını bulmak için \( A \) kümesinin eleman sayısından \( A_2 \cup A_3 \) kümesinin eleman sayısını çıkaralım.
\( s(A_x) = s(A) - s(A_2 \cup A_3) \)
Dahil etme - hariç tutma prensibine göre, \( s(A_2 \cup A_3) \) açılımını yazalım.
\( = s(A) - (s(A_2) + s(A_3) - s(A_2 \cap A_3)) \)
\( = 155 - (77 + 51 - 25) = 52 \) bulunur.
Üç Kümenin Birleşimi
İkişerli ayrık olmayan üç kümenin birleşiminin eleman sayısı, dahil etme - hariç tutma prensibi ile aşağıdaki şekilde hesaplanır.
- Kümelerin eleman sayılarının toplamı alınır (dahil et).
- Kümelerin ikili kesişimleri birinci adımda toplama ikişer kez dahil edildiği için toplamdan birer kez çıkarılır (hariç tut).
- Kümelerin üçlü kesişimi birinci adımda toplama üç kez dahil edilip ikinci adımda toplamdan üç kez çıkarıldığı için toplama tekrar eklenir (dahil et).
\( s(A \cup B \cup C) = s(A) + s(B) + s(C) \)
\( \quad \textcolor{red}{- s(A \cap B) - s(A \cap C) - s(B \cap C)} \)
\( \quad \textcolor{blue}{+ s(A \cap B \cap C)} \)
\( A = \{ 1, 2, 3, 4, 5, 6, 7, 8 \} \)
\( B = \{ 3, 4, 7, 8, 9, 0 \} \)
\( C = \{ 5, 6, 7, 8, 0 \} \)
\( A \cap B = \{ 3, 4, 7, 8 \} \)
\( A \cap C = \{ 5, 6, 7, 8 \} \)
\( B \cap C = \{ 7, 8, 0 \} \)
\( A \cap B \cap C = \{ 7, 8 \} \)
\( A \cup B = \{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \} \)
\( s(A) = 8, \quad s(B) = 6, \quad \) \( s(C) = 5 \)
\( s(A \cap B) = 4, \quad s(A \cap C) = 4, \quad \) \( s(B \cap C) = 3 \)
\( s(A \cap B \cap C) = 2 \)
\( s(A \cup B \cup C) = 8 + 6 + 5 \textcolor{red}{- 4 - 4 - 3} \textcolor{blue}{+ 2} \) \( = 10 \)
Futbol, voleybol ve tenis oyunlarının bulunduğu bir sporcu grubunda futbol oynayan 18, voleybol oynayan 13, tenis oynayan 10 kişi vardır.
Grupta futbol ve voleybol oynayan 7, voleybol ve tenis oynayan 5, futbol ve tenis oynayan 4 ve bu üç sporu da yapan 2 kişi olduğuna göre, bu grup kaç kişiden oluşmaktadır?
\( F \): Futbol oynayanların kümesi
\( V \): Voleybol oynayanların kümesi
\( T \): Tenis oynayanların kümesi
Her küme ve kesişimleri için verilen kişi sayılarını yazalım.
\( s(F) = 18 \)
\( S(V) = 13 \)
\( s(T) = 10 \)
\( s(F \cap V) = 7 \)
\( s(V \cap T) = 5 \)
\( s(F \cap T) = 4 \)
\( s(F \cap V \cap T) = 2 \)
Üç küme için birleşim kümesi eleman sayısı formülünü yazalım.
\( s(F \cup V \cup T) = s(F) + s(V) + s(T) \) \( \color{red}{- s(F \cap V) - s(V \cap T) - s(F \cap T)} \) \( \color{blue}{+ s(F \cap V \cap T)} \)
\( = 18 + 13 + 10 \color{red}{- 7 - 5 - 4} \color{blue}{+ 2} \)
\( = 27 \) bulunur.
Türk alfabesindeki 29 harfin tamamının yan yana yazılmasıyla oluşan tüm dizilişlerde, KALEM, OMUZ, SIR kelimelerinin hiçbirinin bulunmadığı diziliş sayısı kaçtır?
Bir \( A \) kümesinin elemanlarının bir sıra gözetilerek farklı dizilişlerinin her birine \( A \) kümesinin bir permütasyonu denir.
\( n \) elemanlı \( A \) kümesinin permütasyonlarının sayısı \( n! \) formülü ile hesaplanır.
Aşağıdaki dört kümeyi tanımlayalım.
\( E \): 29 harf için tüm dizilişlerin kümesi
\( K \): İçinde KALEM geçen dizilişlerin kümesi
\( O \): İçinde OMUZ geçen dizilişlerin kümesi
\( S \): İçinde SIR geçen dizilişlerin kümesi
Soruda istenen \( E \) kümesinin elemanı olup \( K \), \( O \) veya \( S \) kümelerinin elemanı olmayan dizilişlerin sayısıdır (turuncu taralı alan).
Bu amaçla önce üç kümenin birleşim kümesinin eleman sayısını bulalım.
İçinde KALEM kelimesinin geçtiği diziliş sayısını bulalım.
5 harfli KALEM kelimesini tek bir harf olarak düşünelim. Buna göre geriye kalan 24 harf ve KALEM kelimesi için \( 29 - 5 + 1 = 25! \) farklı diziliş vardır.
\( s(K) = 25! \)
Benzer yaklaşımla 4 harfli OMUZ kelimesi için \( 29 - 4 + 1 = 26! \) ve 3 harfli SIR kelimesi için \( 29 - 3 + 1 = 27! \) farklı diziliş vardır.
\( s(O) = 26! \)
\( s(S) = 27! \)
Yukarıda hesapladığımız dizilişlerin bir kısmı KALEM, OMUZ ve SIR kelimelerini birlikte içerdiği için bazı dizilişleri birden fazla kez saymış olduk.
Şimdi bu kelimelerin ikişerli bulunduğu dizilişlerin sayısını bulalım.
İçinde KALEM ve OMUZ kelimelerinin geçtiği diziliş sayısını bulalım.
Bu iki kelimede "M" harfi ortak olduğu için hiçbir durumda bir dizilişte birlikte yer almazlar.
\( s(K \cap O) = 0 \)
İçinde OMUZ ve SIR kelimelerinin geçtiği diziliş sayısını bulalım.
4 harfli OMUZ ve 3 harfli SIR kelimelerini birer harf olarak düşünelim. Buna göre geriye kalan 22 harf ve bu iki kelime için \( 29 - (4 + 3) + 1 + 1 = 24! \) farklı diziliş vardır.
\( s(O \cap S) = 24! \)
İçinde KALEM ve SIR kelimelerinin geçtiği diziliş sayısını bulalım.
5 harfli KALEM ve 3 harfli SIR kelimelerini birer harf olarak düşünelim. Buna göre geriye kalan 21 harf ve bu iki kelime için \( 29 - (5 + 3) + 1 + 1 = 23! \) farklı diziliş vardır.
\( s(K \cap S) = 23! \)
Şimdi bu kelimelerin üçerli bulunduğu dizilişlerin sayısını bulalım.
KALEM ve OMUZ kelimelerinde "M" harfi ortak olduğu için bu üç kelime hiçbir durumda bir dizilişte birlikte yer almazlar.
\( s(K \cap O \cap S) = 0 \)
KALEM, OMUZ, SIR kelimelerinin en az birinin bulunduğu diziliş sayısını bulmak için dahil etme - hariç bırakma yöntemini kullanarak üç kümenin birleşim kümesinin eleman sayısını bulalım.
\( s(K \cup O \cup S) = s(K) + s(O) + s(S) \) \( \color{red}{- s(K \cap O) - s(O \cap S) - s(K \cap S)} \) \( \color{blue}{+ s(K \cap O \cap S)} \)
\( = 25! + 26! + 27! \color{red}{- 0 - 24! - 23!} \color{blue}{+ 0} \)
\( = 25! + 26! + 27! - 24! - 23! \)
Tüm dizilişlerden bu sayıyı çıkarırsak bu üç kelimenin hiçbirinin bulunmadığı diziliş sayısını buluruz.
29 harfin tamamının yan yana yazılmasıyla oluşan farklı dizilişlerin sayısı \( 29! \) olur.
\( s(E) = 29! \)
KALEM, OMUZ, SIR kelimelerinin hiçbirinin bulunmadığı diziliş sayısı:
\( = s(E) - s(K \cup O \cup S) \)
\( = 29! - (25! + 26! + 27! - 24! - 23!) \) bulunur.
Bir müzik festivalinde A, B, C, D ve E sanatçıları farklı zamanlarda konser verecektir.
Festivalde en az iki konseri izleyen 900 kişi, en az üç konseri izleyen 760 kişi, en az dört konseri izleyen 500 kişi, beş konseri de izleyen 400 kişi vardır. Konserlerin tümü toplamda 4000 kez izlenmiştir.
Festivale katılıp hiçbir konseri izlemeyen 160 kişi olduğuna göre, festivalde kaç kişi vardır?
Her bir konseri izleyen kişilerin kümesine sırasıyla A, B, C, D ve E diyelim.
Kümelerin eleman sayılarının toplamı konserlerin toplam izlenme sayısını verir.
\( S_1 = s(A) + s(B) + \ldots + s(E) = 4000 \)
İkili kesişim kümelerinin eleman sayılarının toplamı en az iki konseri izleyen kişi sayısını verir.
\( S_2 = s(A \cap B) + \ldots + s(D \cap E) = 900 \)
Üçlü kesişim kümelerinin eleman sayılarının toplamı en az üç konseri izleyen kişi sayısını verir.
\( S_3 = s(A \cap B \cap C) + \ldots + s(C \cap D \cap E) = 760 \)
Dörtlü kesişim kümelerinin eleman sayılarının toplamı en az dört konseri izleyen kişi sayısını verir.
\( S_4 = s(A \cap B \cap C \cap D) + \ldots + s(B \cap C \cap D \cap E) = 500 \)
Beşli kesişim kümesinin eleman sayısı beş konseri de izleyen kişi sayısını verir.
\( S_5 = s(A \cap B \cap C \cap D \cap E) = 400 \)
Beş kümenin birleşim kümesinin eleman sayısı en az bir konseri izleyen kişi sayısını verir.
\( S = s(A) + s(B) + s(C) + s(D) + s(E) \)
\( S \) değerini "dahil etme - hariç tutma prensibi" formülü ile bulabiliriz.
\( S = S_1 - S_2 + S_3 - S_4 + S_5 \)
\( S = 4000 - 900 + 760 - 500 + 400 \)
\( = 3760 \)
Bu sayıya festivale katılıp hiçbir konseri izlemeyen kişi sayısını ekleyelim.
\( 3760 + 160 = 3920 \) bulunur.
n Kümenin Birleşimi
\( n \) kümenin birleşiminin eleman sayısı, dahil etme - hariç tutma prensibi ile aşağıdaki şekilde hesaplanır.
- \( (+) \) Kümelerin eleman sayılarının toplamı alınır (dahil et).
- \( (-) \) Kümelerin ikili kesişimleri toplamdan çıkarılır (hariç tut).
- \( (+) \) Kümelerin üçlü kesişimleri toplama eklenir (dahil et).
- \( (-) \) Kümelerin dörtlü kesişimleri toplamdan çıkarılır (hariç tut).
- \( (+) \) Kümelerin beşli kesişimleri toplama eklenir (dahil et).
- \( \vdots \)
- \( (\pm) \) Bu işlem kümelerin \( n \)'li kesişimine kadar tekrarlanır.
Yöntemi özetlemek gerekirse, \( n \) tane kümenin birleşim kümesinin eleman sayısını bulmak için kümelerin eleman sayılarının toplamı alınır, tek sayıda kümeden oluşan kesişim kümelerinin eleman sayıları bu toplama eklenir, çift sayıda kümeden oluşan kesişim kümelerinin eleman sayıları bu toplamdan çıkarılır.
Bu yöntemin \( n \) küme için genel formülü aşağıdaki gibidir.
\( A_1, A_2, \ldots, A_n \) birer küme ve,
\( \emptyset \ne J \subseteq \{ 1, 2, 3, \ldots, n \} \) olmak üzere,
\( s(\displaystyle\bigcup_{i=1}^{n} A_i) \) \( = \displaystyle\sum_{J} (-1)^{s(J) + 1} \) \( \cdot s(\displaystyle\bigcap_{j \in J} A_j) \)
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ı
Her öğrencinin en azından bir yabancı dil konuştuğu bir sınıfta İngilizce bilen öğrencilerin sayısı 25, Almanca bilen öğrencilerin sayısı 16, her iki dili de bilen öğrencilerin sayısı da 9 ise sınıfta öğrenci vardır?
Dahil etme - hariç tutma prensibini iki 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 iki kümeli durum için dahil etme - hariç tutma formülünde yerine koyalım.
\( s(I \cup A) = s(I) + s(A) \) \( - s(I \cap A) \)
\( = 25 + 16 - 9 = 32 \) bulunur.
Bölünebilme Problemleri
1-1000 arasındaki pozitif tam sayılar içinde 2'ye, 3'e veya 5'e tam bölünen kaç sayı vardır?
Dahil etme - hariç tutma prensibini üç kümeli duruma uygulayarak soruyu çözebiliriz.
2'ye, 3'e ve 5'e tam bölünen sayıları birer küme olarak tanımlayalım.
\( E \): 1-1000 arasındaki pozitif tam sayılar (1-1000)
\( A_2 \): 2'ye tam bölünen sayılar kümesi
\( A_3 \): 3'e tam bölünen sayılar kümesi
\( A_5 \): 5'e tam bölünen sayılar kümesi
\( A_2 \cap A_3 \): 2'ye VE 3'e tam bölünen sayılar (5'e bölünebilmesinden bağımsız)
\( A_2 \cap A_5 \): 2'ye VE 5'e tam bölünen sayılar (3'e bölünebilmesinden bağımsız)
\( A_3 \cap A_5 \): 3'e VE 5'e tam bölünen 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ünen sayılar
1-1000 arasında 2'ye bölünen \( \floor{\frac{1000}{2}} = 500 \) sayı vardır.
\( s(A_2) = 500 \)
1-1000 arasında 3'e bölünen \( \floor{\frac{1000}{3}} = 333 \) sayı vardır.
\( s(A_3) = 333 \)
1-1000 arasında 5'e bölünen \( \floor{\frac{1000}{5}} = 200 \) sayı vardır.
\( s(A_5) = 200 \)
2'ye ve 3'e birlikte bölünen sayılar \( \text{EKOK}(2, 3) = 6 \)'ya da bölünür. 1-1000 arasında 6'ya tam bölünen \( \floor{\frac{1000}{6}} = 166 \) sayı vardır.
\( s(A_2 \cap A_3) = 166 \)
2'ye ve 5'e birlikte bölünen sayılar \( \text{EKOK}(2, 5) = 10 \)'a da bölünür. 1-1000 arasında 10'a tam bölünen \( \floor{\frac{1000}{10}} = 100 \) sayı vardır.
\( s(A_2 \cap A_5) = 100 \)
3'e ve 5'e birlikte bölünen sayılar \( \text{EKOK}(3, 5) = 15 \)'e de bölünür. 1-1000 arasında 15'e tam bölünen \( \floor{\frac{1000}{15}} = 66 \) sayı vardır.
\( s(A_3 \cap A_5) = 66 \)
2'ye, 3'e ve 5'e birlikte bölünen sayılar \( \text{EKOK}(2, 3, 5) = 30 \)'a da bölünür. 1-1000 arasında 30'a tam bölünen \( \floor{\frac{1000}{30}} = 33 \) sayı vardır.
\( s(A_2 \cap A_3 \cap A_5) = 33 \)
Bu bilgileri üç kümeli durum için dahil etme - hariç tutma formülünde 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ı
İki küme arasında tanımlanabilecek örten fonksiyon sayısını dahil etme - hariç tutma prensibi ile nasıl hesaplayabileceğimizi önümüzdeki bölümde inceleyeceğiz.
\( x \in \mathbb{Z^+} \) olmak üzere,
0 ile 1 açık aralığında ve en sade hali \( \frac{x}{2023} \) formunda olan kaç farklı kesir vardır?
\( \frac{x}{2023} \) formundaki kesirler iki koşulu sağlamalıdır.
\( 1 \le x \le 2022 \) olmalıdır, aksi takdirde kesir 0 ile 1 açık aralığında olmaz.
\( x \) ve 2023 sayıları aralarında asal sayılar olmalıdır, aksi takdirde kesrin daha sade hali bulunabilir.
Öncelikle 2023 sayısını asal çarpanlarına ayıralım.
\( 2023 = 7 \cdot 17^2 \)
2023 ile aralarında asal sayıları bulmak için \( x \)'in alabileceği 2022 adet değerden 7'nin ve 17'nin katlarını çıkaralım.
\( E \): 1-2022 arasındaki tam sayılar kümesi
\( A_7 \): 7'ye tam bölünen sayılar kümesi
\( A_{17} \): 17'ye tam bölünen sayılar kümesi
\( A_7 \cap A_{17} \): 7'ye VE 17'ye tam bölünen sayılar
1-2022 arasında 7'ye bölünen \( \floor{\frac{2022}{7}} = 288 \) sayı vardır.
\( s(A_7) = 288 \)
1-2022 arasında 17'ye bölünen \( \floor{\frac{2022}{17}} = 118 \) sayı vardır.
\( s(A_{17}) = 118 \)
Hem 7'ye hem de 17'ye bölünen sayılar \( \text{EKOK}(7, 17) = 119 \)'a da bölünür.
1-2022 arasında 119'a bölünen \( \floor{\frac{2022}{119}} = 16 \) sayı vardır.
\( s(A_7 \cap A_{17}) = 16 \)
Bu bilgileri iki kümeli durum için dahil etme - hariç tutma formülünde yerine koyalım.
\( s(A_7 \cup A_{17}) = s(A_7) + s(A_{17}) - s(A_7 \cap A_{17}) \)
\( = 288 + 118 - 16 = 390 \)
Buna göre 1-2022 aralığındaki tam sayılar içinde 7'ye veya 17'ye tam bölünmeyen \( 2022 - 390 = 1632 \) farklı \( x \) tam sayısı vardır, dolayısıyla istenen koşulları sağlayan 1632 farklı kesir yazılabilir.