Dahil etme - hariç tutma prensibinin uygulamalarından biri iki küme arasında tanımlanabilecek örten fonksiyon sayısının hesaplanmasıdır.
Fonksiyonlar konusunda örten fonksiyon sayısı formülünü aşağıdaki şekilde tanımlamıştık.
\( f: A \to B \)
\( s(A) = n, \quad s(B) = k \) olmak üzere,
Örten fonksiyon sayısı \( = \begin{cases} 0 & n \lt k \\ k! & n = k \\ \sum_{i = 0}^{k} {(-1)^i \binom{k}{i} (k - i)^n} & n \gt k \end{cases} \)
Bu formüle göre, \( n \lt k \) olduğu durumda \( A \) kümesinde \( B \) kümesinin tüm elemanları ile eşlenecek kadar eleman bulunmadığı için örten fonksiyon yazılamaz. \( n = k \) olduğu durumda iki kümenin elemanlarının birebir eşleştiği fonksiyonlar aynı zamanda örten olur, bu da \( k! \) fonksiyona karşılık gelir. \( n \gt k \) olduğu durumda ise dahil etme - hariç tutma prensibini kullanmamız gerekir.
Bu prensibi örten fonksiyon sayısının hesaplanmasında nasıl kullanabileceğimizi bir örnek üzerinden inceleyelim.
\( A = \{ 1, 2, 3, 4, 5 \} \)
\( B = \{ a, b, c, d \} \)
olmak üzere, \( A \) kümesinden \( B \) kümesine kaç farklı örten fonksiyon tanımlanabilir?
Verilen toplam formülünü bu soruya \( i = 0 \) ile başlayarak \( i = 4 \)'e kadar uygulayalım.
\( s(A) = n = 5, \quad s(B) = k = 4 \) olmak üzere,
\( i = 0 \) için: \( A \)'dan \( B \)'ye tanımlanabilecek tüm fonksiyonların sayısını ekle.
\( (-1)^i \binom{k}{i} (k - i)^n \) \( = (-1)^0 \binom{4}{0} (4 - 0)^5 = (+1) \cdot 1 \cdot 1024 = +1024 \)
Toplam formülünün bu adımını "5 elemanlı \( A \) kümesinden 4 elemanlı \( B \) kümesine \( 4^5 \) farklı fonksiyon tanımlanabilir" şeklinde yorumlayabiliriz.
\( B \)'nin 4 elemanının da hesaplamaya dahil edildiği bu durum, görüntü kümesinde 4'ten az eleman bulunan (dolayısıyla örten olmayan) fonksiyonları da içerir, bu yüzden bu fonksiyonları aşağıdaki adımda toplamdan çıkarmamız gerekir.
\( i = 1 \) için: \( A \)'dan \( B \)'nin 3 elemanlı alt kümelerine tanımlanabilecek fonksiyonların sayısını çıkar.
\( (-1)^i \binom{k}{i} (k - i)^n \) \( = (-1)^1 \binom{4}{1} (4 - 1)^5 = (-1) \cdot 4 \cdot 243 = -972 \)
Toplam formülünün bu adımını "\( B \) kümesinin elemanları içinden 1 eleman \( \binom{4}{1} \) farklı şekilde hariç tutulabilir (ya da 3 eleman \( \binom{4}{3} \) farklı şekilde seçilebilir) ve 5 elemanlı \( A \) kümesinden \( B \)'nin seçilen her 3 elemanlı alt kümesine \( 3^5 \) farklı fonksiyon tanımlanabilir" şeklinde yorumlayabiliriz.
Bu adımda görüntü kümesinde 3 eleman bulunan (dolayısıyla örten olmayan) fonksiyonlar doğru şekilde hesaplanır ve yukarıdaki toplamdan çıkarılır, ancak görüntü kümesinde 3'ten az eleman bulunan fonksiyonlar birden fazla alt kümede tekrarlı şekilde bulunabileceği için bazı fonksiyonları birden fazla kez toplamdan çıkarmış oluruz, bu yüzden bu fonksiyonları aşağıdaki adımda toplama tekrar eklememiz gerekir.
\( i = 2 \) için: \( A \)'dan \( B \)'nin 2 elemanlı alt kümelerine tanımlanabilecek fonksiyonların sayısını ekle.
\( (-1)^i \binom{k}{i} (k - i)^n \) \( = (-1)^2 \binom{4}{2} (4 - 2)^5 = (+1) \cdot 6 \cdot 32 = +192 \)
\( i = 3 \) için: \( A \)'dan \( B \)'nin 1 elemanlı alt kümelerine tanımlanabilecek fonksiyonların sayısını çıkar.
\( (-1)^i \binom{k}{i} (k - i)^n \) \( = (-1)^3 \binom{4}{3} (4 - 3)^5 = (-1) \cdot 4 \cdot 1 = -4 \)
\( i = 4 \) için: \( A \)'dan \( B \)'nin 0 elemanlı alt kümelerine tanımlanabilecek fonksiyonların sayısını ekle.
\( (-1)^i \binom{k}{i} (k - i)^n \) \( = (-1)^4 \binom{4}{4} (4 - 4)^5 = (+1) \cdot 1 \cdot 0 = 0 \)
Yukarıda \( i \)'nin her değeri için hesapladığımız değerleri formülde yerine koyalım.
Örten fonksiyon sayısı \( = 1024 - 972 + 192 - 4 + 0 = 240 \)
Buna göre \( A \) kümesinden \( B \) kümesine tanımlanabilecek örten fonksiyon sayısı 240 olur.