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 \\ \displaystyle\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 sayıda 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 prensibi kullanılır.
Bu prensibin örten fonksiyon sayısının hesaplanmasında nasıl kullanılabileceğini bir örnek üzerinden gösterelim.
\( 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ı "5 elemanlı \( A \) kümesinden 4 elemanlı \( B \) kümesine \( 4^5 \) farklı fonksiyon tanımlanabilir" şeklinde yorumlanabilir.
\( 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ın aşağıdaki adımda toplamdan çıkarılması 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ı "\( 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 yorumlanabilir.
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 çıkarılmış olur, bu yüzden bu fonksiyonların aşağıdaki adımda toplama tekrar eklenmesi 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 olarak bulunur.