Contoh 3.8.8.
Berapa banyak fungsi \(f: \{1,2,3,4,5\} \to \{a,b,c\}\) yang surjektif?
Penyelesaian.
Sekali lagi, mulailah dari seluruh fungsi, yaitu \(3^5\text{,}\) karena setiap satu dari lima anggota domain dapat dipetakan ke salah satu dari tiga anggota kodomain. Sekarang kita mencacah fungsi yang tidak surjektif.
Mulailah dengan mengecualikan \(a\) dari daerah hasil. Kemudian tersedia dua pilihan, \(b\) atau \(c\text{,}\) sebagai citra setiap satu dari lima anggota domain. Jadi, terdapat \(2^5\) fungsi yang mengecualikan \(a\) dari daerah hasil. Demikian pula, terdapat \(2^5\) fungsi yang mengecualikan \(b\) dan \(2^5\) fungsi lain yang mengecualikan \(c\text{.}\) Apakah kita sekarang telah mencacah semua fungsi yang tidak surjektif? Ya, tetapi sebenarnya beberapa di antaranya telah dicacah berkali-kali. Sebagai contoh, fungsi yang memetakan semuanya ke \(c\) termasuk salah satu dari \(2^5\) fungsi yang kita cacah ketika mengecualikan \(a\text{,}\) sekaligus salah satu dari \(2^5\) fungsi yang kita cacah ketika mengecualikan \(b\text{.}\) Kita harus mengurangkan semua fungsi yang secara khusus mengecualikan dua anggota dari daerah hasil. Terdapat 1 fungsi ketika kita mengecualikan \(a\) dan \(b\) (semuanya dipetakan ke \(c\)), satu fungsi ketika kita mengecualikan \(a\) dan \(c\text{,}\) serta satu fungsi ketika kita mengecualikan \(b\) dan \(c\text{.}\)
Kita sedang menggunakan prinsip inklusi–eksklusi. Untuk mencacah fungsi yang tidak surjektif, kita menjumlahkan secara terpisah fungsi yang mengecualikan \(a\text{,}\) \(b\text{,}\) dan \(c\text{,}\) lalu mengurangkan fungsi yang mengecualikan pasangan anggota. Berikutnya, kita seharusnya menambahkan kembali fungsi yang mengecualikan kelompok tiga anggota, tetapi tidak ada fungsi semacam itu. Jadi, banyaknya fungsi yang tidak surjektif adalah
\begin{equation*}
2^5 + 2^5 + 2^5 - 1 - 1 - 1 + 0 \text{.}
\end{equation*}
Cara yang mungkin lebih deskriptif untuk menuliskannya adalah
\begin{equation*}
{3 \choose 1}2^5 - {3 \choose 2}1^5 + {3 \choose 3}0^5 \text{,}
\end{equation*}
karena setiap suku \(2^5\) diperoleh dengan memilih 1 dari 3 anggota kodomain untuk dikecualikan dari daerah hasil, sedangkan setiap satu dari tiga suku \(1^5\) diperoleh dengan memilih 2 dari 3 anggota kodomain untuk dikecualikan. Menulis \(1^5\) alih-alih 1 juga masuk akal: kita mempunyai 1 pilihan citra bagi setiap satu dari 5 anggota domain.
Sekarang kita akhirnya dapat mencacah banyaknya fungsi surjektif:
\begin{equation*}
3^5 - \left[{3 \choose 1}2^5 - {3 \choose 2}1^5\right] = 150 \text{.}
\end{equation*}