Lema 7.8.
Untuk setiap himpunan bagian \(S\subseteq [m]\text{,}\) \(N(S)\) hanya bergantung pada \(|S|\text{.}\) Bahkan, jika \(|S|=k\text{,}\) maka
\begin{equation*}
N(S)=(m-k)^n.
\end{equation*}
Subbab 7.3 Enumerasi Fungsi Surjektif
Sebagai contoh pertama kekuatan prinsip inklusi–eksklusi, perhatikan situasi berikut: Seorang kakek memiliki \(15\) lembar tiket lotre yang berbeda dan ingin membagikannya kepada keempat cucunya sedemikian sehingga setiap cucu menerima sedikitnya satu tiket. Ada berapa cara ia dapat melakukan pembagian tersebut? Sekilas, masalah ini sangat mirip dengan masalah menghitung banyaknya solusi bilangan bulat suatu persamaan, hanya saja tiket lotrenya tidak identik! Sebuah tiket bernomor \(1\text{,}\) \(3\text{,}\) \(10\text{,}\) \(23\text{,}\) \(47\text{,}\) dan \(50\) hampir pasti tidak akan memberikan hadiah yang sama besarnya dengan tiket bernomor \(2\text{,}\) \(7\text{,}\) \(10\text{,}\) \(30\text{,}\) \(31\text{,}\) dan \(48\text{,}\) sehingga siapa menerima tiket yang mana memang berpengaruh. Mudah-mudahan Anda sudah menyadari bahwa persoalan tentang tiket lotre dan cucu sebenarnya bukanlah hal yang penting di sini. Fakta yang penting justru bahwa kita ingin membagikan objek-objek yang dapat dibedakan kepada penerima-penerima yang berbeda, sehingga kita perlu menghitung fungsi dari satu himpunan (tiket lotre) ke himpunan lain (cucu). Dalam contoh kita, yang dicari bukan sekadar jumlah seluruh fungsi, melainkan jumlah fungsi surjektif, agar kita dapat memastikan bahwa setiap cucu menerima tiket.
Untuk bilangan bulat positif \(n\) dan \(m\text{,}\) misalkan \(S(n,m)\) menyatakan banyaknya fungsi surjektif dari \([n]\) ke \([m]\text{.}\) Perhatikan bahwa \(S(n,m)=0\) ketika \(n\lt m\text{.}\) Pada bagian ini, kita menerapkan formula Inklusi–Eksklusi untuk menentukan formula bagi \(S(n,m)\text{.}\) Kita mulai dengan menetapkan \(X\) sebagai himpunan semua fungsi dari \([n]\) ke \([m]\text{.}\) Selanjutnya, untuk setiap \(f\in X\) dan setiap \(i=1,2,\dots,m\text{,}\) kita katakan bahwa \(f\) memenuhi sifat \(P_i\) jika \(i\) tidak berada dalam citra \(f\text{.}\)
Bukti.
Misalkan \(|S|=k\text{.}\) Maka, suatu fungsi \(f\) yang memenuhi sifat \(P_i\) untuk setiap \(i\in S\) merupakan string dengan panjang \(n\) atas suatu alfabet yang terdiri atas \(m-k\) huruf. Hal ini menunjukkan bahwa
\begin{equation*}
N(S)=(m-k)^n.
\end{equation*}
Hasil berikut kini langsung diperoleh dari lemma ini dengan menerapkan Prinsip Inklusi–Eksklusi, karena terdapat \(C(m,k)\) himpunan bagian berunsur \(k\) dari \([m]\text{.}\)
Teorema 7.9.
Banyaknya fungsi surjektif \(S(n,m)\) dari \([n]\) ke \([m]\) diberikan oleh:
\begin{equation*}
S(n,m) = \sum_{k=0}^m (-1)^k\binom{m}{k}(m-k)^n.
\end{equation*}
Sebagai contoh,
\begin{align*}
S(5,3) \amp = \binom{3}{0}(3-0)^5-\binom{3}{1}(3-1)^5+\binom{3}{2}(3-2)^5-\binom{3}{3}(3-3)^5\\
\amp = 243 -96+3-0\\
\amp = 150.
\end{align*}
Kembali ke masalah pembagian tiket lotre pada awal bagian ini, kita melihat bahwa terdapat \(S(15,4)=1016542800\) cara bagi sang kakek untuk membagikan \(15\) tiket lotrenya sedemikian sehingga setiap satu dari \(4\) cucunya menerima sedikitnya satu tiket.
