Kombinatorikte Dahil Etme-Hariç Tutma Prensibi: Küme Boyutunun Kolaylıkla Hesaplanması

Dahil etme-dışlama ilkesi, kombinatorikte bir kümenin boyutunu, onu daha küçük alt kümelere bölerek ve bunların kesişimlerini sayarak hesaplamak için kullanılan bir tekniktir. A ve B olmak üzere iki kümemiz varsa ve her iki kümede bulunan elemanları saymak istiyorsak, bunu yalnızca A'da bulunan elemanları A'daki toplam eleman sayısından çıkararak yapabileceğimiz fikrine dayanmaktadır. A'yı seçin ve ardından yalnızca B'de bulunan elemanları geri ekleyin.

Daha resmi olarak, A ve B'nin iki küme olduğunu ve |A| A'daki eleman sayısı olsun. O halde dahil etme-dışlama ilkesi şunu belirtir:

|A ∪ B| = |A| + |B| - |A ∩ B|

nerede |A ∪ B| A ve B'nin birleşimindeki elementlerin sayısıdır ve |A ∩ B| hem A hem de B'de bulunan elementlerin sayısıdır.

Bu formülün arkasındaki fikir, iki kümenin birleşim boyutunu, önce her kümedeki elementlerin sayısını ayrı ayrı sayarak, sonra da bu kümedeki elemanları çıkararak hesaplayabilmemizdir. kümelerden yalnızca birindedir (yani kesişimdeki öğeler). Bu bize birleşimdeki toplam öğe sayısını verir; bu, her kümedeki öğe sayısından yalnızca kümelerden birinde bulunan öğe sayısının çıkarılmasıyla elde edilir.

Örneğin, iki kümemiz olduğunu varsayalım: A = {1, 2, 3} ve B = {4, 5, 6}. Dahil etme-dışlama ilkesini kullanarak birleşimlerinin boyutunu hesaplamak için öncelikle her kümedeki elementlerin sayısını ayrı ayrı sayarız:

|A| = 3
|B| = 3

Sonra, her iki kümede bulunan elemanların sayısını, bunların kesişimlerini sayarak hesaplıyoruz:

|A ∩ B| = 2 (1 ve 2 her iki kümede olduğundan)

Şimdi birleşim boyutunu hesaplamak için dahil etme-dışlama ilkesini kullanabiliriz:

|A ∪ B| = |A| + |B| - |A ∩ B|
= 3 + 3 - 2
= 6

Yani, A ve B'nin birleşiminin boyutu 6'dır.

İçerme-dışlama ilkesinin kombinatorikte permütasyon, kombinasyon ve çözüm sayısını sayma gibi birçok uygulaması vardır. denklemlere. Sayma problemlerini çözmek için güçlü bir araçtır ve karmaşık hesaplamaları basitleştirmek için kullanılabilir.