Contoh 3.8.9.

  1. Berapa banyak fungsi \(f: \{1,2,3,4,5\} \to \{a,b,c,d\}\) yang surjektif?
  2. Berapa banyak fungsi \(f: \{1,2,3,4,5\} \to \{a,b,c,d,e\}\) yang surjektif?
Penyelesaian.
  1. Terdapat \(4^5\) fungsi seluruhnya; kita akan mengurangkan fungsi yang tidak surjektif. Kita dapat mengecualikan salah satu dari empat anggota kodomain, dan untuk setiap anggota yang dikecualikan tersisa \(3^5\) fungsi. Hal ini mencacah terlalu banyak, sehingga kita mengurangkan fungsi yang mengecualikan dua dari empat anggota kodomain; setiap pasangan menghasilkan \(2^5\) fungsi. Namun, pengurangan ini terlalu banyak, sehingga kita menambahkan kembali fungsi yang mengecualikan tiga dari empat anggota kodomain; setiap rangkap tiga menghasilkan \(1^5\) fungsi. Terdapat \({4 \choose 1}\) kelompok fungsi yang mengecualikan satu anggota, \({4 \choose 2}\) kelompok fungsi yang mengecualikan sepasang anggota, dan \({4 \choose 3}\) kelompok fungsi yang mengecualikan tiga anggota. Jadi, banyaknya fungsi yang tidak surjektif adalah
    \begin{equation*} {4 \choose 1}3^5 - {4 \choose 2}2^5 + {4 \choose 3}1^5 \text{.} \end{equation*}
    Dengan demikian, banyaknya fungsi yang surjektif adalah
    \begin{equation*} 4^5 - \left[{4 \choose 1}3^5 - {4 \choose 2}2^5 + {4 \choose 3}1^5\right] \text{.} \end{equation*}
  2. Banyaknya fungsi surjektif adalah
    \begin{equation*} 5^5 - \left[{5 \choose 1}4^5 - {5 \choose 2}3^5 + {5 \choose 3}2^5 - {5 \choose 4}1^5\right] \text{.} \end{equation*}
    Kita mengambil seluruh \(5^5\) fungsi lalu mengurangkan semua yang tidak surjektif. Terdapat \({5 \choose 1}\) cara memilih satu anggota kodomain untuk dikecualikan dari daerah hasil, dan untuk setiap pilihan terdapat \(4^5\) fungsi. Namun, hal ini mencacah ganda, sehingga dengan prinsip inklusi–eksklusi kita mengurangkan fungsi yang mengecualikan dua anggota dari daerah hasil: terdapat \({5 \choose 2}\) pilihan bagi kedua anggota yang dikecualikan dan, untuk setiap pasangan, terdapat \(3^5\) fungsi. Pengurangan ini menghapus terlalu banyak fungsi, sehingga kita menambahkan kembali fungsi yang mengecualikan 3 anggota dari daerah hasil: terdapat \({5 \choose 3}\) pilihan tiga anggota yang dikecualikan dan \(2^5\) fungsi untuk setiap pilihan. Terakhir, untuk setiap satu dari \({5 \choose 4}\) pilihan 4 anggota, kita mengurangkan kembali 1 fungsi yang mengecualikan keempat anggota tersebut.
    Jika Anda menghitung bilangan ini secara tepat, hasilnya 120 surjeksi. Kebetulan, bilangan ini juga sama dengan \(5!\text{.}\) Hal tersebut mungkin tampak sebagai kebetulan yang luar biasa sampai kita menyadari bahwa setiap fungsi surjektif \(f:X \to Y\) dengan nilai \(\card{X} = \card{Y}\) yang berhingga harus merupakan bijeksi. Dalam kasus ini, banyaknya bijeksi selalu \(\card{X}!\text{.}\) Jadi, kita memperoleh pembuktian kombinatorial bagi identitas berikut:
    \begin{equation*} n^n - \left[{n\choose 1}(n-1)^n - {n \choose 2}(n-2)^n + \cdots + {n \choose n-1}1^n \right] = n! \text{.} \end{equation*}
dalam konteks