Dalam tulisan ini, kita akan menentukan banyaknya fungsi surjektif atau fungsi onto yang mungkin dari suatu himpunan A ke himpunan B. Namun, sebelum itu, kita perlu mengetahui definisi fungsi surjektif.

Definisi

Sebuah fungsi $f:A \rightarrow B$ disebut fungsi surjektif, jika untuk setiap $b \in B$ terdapat $a \in A$ sedemikian sehingga $f(a)=b$. Dengan kata lain, $f$ disebut fungsi surjektif, jika daerah hasil (range) $f$ sama dengan kodomainnya, yaitu himpunan $B$.

Selain itu, kita perlu tahu bagaimana menentukan banyaknya fungsi yang mungkin dari suatu himpunan ke himpunan lain. Misalkan $A$ dan $B$ adalah dua himpunan berhingga dengan $A=\{ x_1,x_2, \cdots ,x_m \}$ dan $B=\{ y_1,y_2, \cdots ,y_n \}$. Misalkan pula $f$ adalah suatu fungsi dari himpunan A ke himpunan B. $f$ memetakan setiap anggota himpunan A ke tepat satu anggota himpunan $B$. Dalam bahasa yang lebih sederhana, setiap anggota $A$ dipasangkan dengan tepat satu anggota $B$ oleh fungsi $f$.

$x_1 \in A$ dapat dipasangkan dengan satu anggota himpunan B, dari n anggota yang ada. $x_2 \in A$ dapat dipasangkan dengan satu dari n anggota himpunan B, termasuk anggota yang telah dipasangkan dengan $x_1$ (Pada sebuah fungsi, anggota kodomain dapat berpasangan dengan lebih dari satu anggota domain). Begitu seterusnya sampai pada $x_m \in A$. Berdasarkan aturan perkalian, banyaknya fungsi yang mungkin adalah$$\underbrace{n \times n \times \cdots \times n}_{\text{sebanyak m}} = n^m$$

Banyaknya Fungsi Surjektif yang Mungkin dari A ke B

Kita akan menggunakan prinsip inklusi-eksklusi untuk menentukan banyaknya fungsi surjektif yang mungkin. Untuk $1 \leq i \leq n$, misalkan $c_i$ menyatakan kondisi dimana daerah hasil fungsi tidak memuat $x_i$. $N(c_i)$ menyatakan banyaknya fungsi yang tidak memuat $x_i$ pada daerah hasilnya. Fungsi surjektif adalah fungsi yang memuat $x_1$, $x_2$, $\cdots$, dan $x_n$ pada daerah hasilnya, sehingga banyaknya fungsi surjektif dinyatakan dengan $N(\bar{c}_1,\bar{c}_2,\bar{c}_3,\cdots,\bar{c}_n)$.

Banyaknya fungsi dari A ke B adalah $n^m$, sehingga $N=S_0=n^m$. Selanjutnya, kita akan menentukan banyaknya fungsi yang tidak memuat $x_1$ pada daerah hasilnya, yaitu $N(c_1)$. Ini sama saja dengan banyaknya fungsi yang mungkin dari $A$ ke $B-\{x_1\}$, yang beranggotakan $n-1$ objek. Banyaknya fungsi adalah $(n-1)^m$, sehingga $N(c_1)=(n-1)^m$. Dengan cara yang sama, kita peroleh $N(c_1)=N(c_2)= \cdots =N(c_n)=(n-1)^m$. Akibatnya$$\begin{aligned}S_1 &= N(c_1)+N(c_2)+ \cdots + N(c_n) \\&= (n-1)^m + (n-1)^m + \cdots + (n-1)^m\end{aligned}$$

Terlihat jelas, bahwa banyaknya suku pada ruas kanan adalah $n$. Namun, $n$ dapat dipandang sebagai banyaknya cara memilih satu anggota dari himpunan B, yaitu ${n \choose 1}$. Sehingga$$S_1 = n(n-1)^m = {n \choose 1} (n-1)^m$$

Selanjutnya, kita menentukan banyaknya fungsi yang tidak memuat dua objek tertentu pada daerah hasilnya, misalnya $x_1$ dan $x_2$. $N(c_1c_2)$ sama dengan banyaknya fungsi yang mungkin dari himpunan $A$ ke $B-\{x_1,x_2\}$, yaitu $(n-2)^m$. Secara umum, kita peroleh $N(c_pc_q)=(n-2)^m$, untuk $1 \leq p \leq n$, $1 \leq q \leq n$, dan $p \neq q$.

Akibatnya $S_2=(n-2)^m+(n-2)^m+ \cdots +(n-2)^m$. Banyak suku sama dengan banyaknya cara memilih dua objek untuk dikeluarkan dari daerah hasil $f$, yaitu ${n \choose 2}$. Sehingga$$S_2 = {n \choose 2} (n-2)^m$$Secara umum, untuk $1 \leq k \leq n$, berlaku$$S_k = {n \choose k} (n-k)^m$$

Berdasarkan prinsip inklusi-eksklusi, diperoleh$$\begin{aligned}N(\bar{c}_1,\bar{c}_2,\bar{c}_3,\cdots,\bar{c}_n) &= S_0-S_1+S_2-\cdots+(-1)^nS_n \\&= n^m-{n \choose 1} (n-1)^m+{n \choose 2} (n-2)^m-\cdots+(-1)^n{n \choose n} (n-n)^m \\&= {n \choose 0}n^m-{n \choose 1} (n-1)^m+{n \choose 2} (n-2)^m-\cdots+(-1)^n{n \choose n} (n-n)^m \\&= \sum^n_{i=0} (-1)^i{n \choose i} (n-i)^m\end{aligned}$$

Agar lebih mudah diingat, kita dapat menuliskan dalam bentuk$$N(\bar{c}_1,\bar{c}_2,\bar{c}_3,\cdots,\bar{c}_n) = \sum^n_{i=0} (-1)^i {n \choose n-i} (n-i)^m$$Hal ini dibolehkan, mengingat adanya identitas ${n \choose i}={n \choose n-i}$. Jadi, banyaknya fungsi surjektif dari $A$ ke $B$ adalah $\sum^n_{i=0} (-1)^i {n \choose n-i} (n-i)^m$.

CATATAN

Jika $|A|=m \leq n=|B|$, maka tidak ada fungsi surjektif dari $A$ ke $B$ (Tahu alasannya?). Meskipun hal ini terjadi, ternyata rumus di atas masih tetap berlaku. Untuk $m \leq n$, kita akan memperoleh $N(\bar{c}_1,\bar{c}_2,\bar{c}_3,\cdots,\bar{c}_n)=0$.

Contoh 1

Tentukan banyaknya fungsi surjektif dari himpunan $A$ ke himpunan $B$, jika diketahui $|A|=5$ dan $|B|=3$.

Pembahasan

Banyaknya fungsi surjektif $f: \: A \rightarrow B$, dengan $|A|=5$ dan $|B|=3$ adalah$$\begin{aligned}\sum^3_{i=0} (-1)^i{3 \choose 3-i} (3-i)^5 &= {3 \choose 3} 3^5 - {3 \choose 2} 2^5 + {3 \choose 1} 1^5 - {3 \choose 0} 0^5 \\&= 1 \cdot 243 - 3 \cdot 32 + 3 \cdot 1 - 1 \cdot 0 \\&= 243 - 96 + 3 - 0 \\&= 150\end{aligned}$$

Contoh 2

Tentukan banyaknya fungsi surjektif $f$ dari $X$ ke $Y$, jika $X=\{a,b,c,d,e,f\}$, $Y=\{1,2,3,4\}$, dan $f(a)=1$.

Pembahasan

Fungsi $f$ harus memetakan $a \in X$ ke $1 \in Y$. $f$ adalah fungsi, sehingga a tidak boleh lagi dipetakan ke anggota $Y$ yang lain. Namun kita boleh memetakan anggota $X$ selain $a$ pada $1 \in Y$. Kita bagi menjadi dua kasus.

Kasus 1: Tidak ada anggota $X$ selain $a$ yang dipetakan ke $1 \in Y$

Banyaknya fungsi yang mungkin sama dengan banyaknya fungsi surjektif dari $X-\{a\}=\{b,c,d,e,f\}$ ke $Y-\{1\}=\{2,3,4\}$, yaitu$$\begin{aligned}\sum^3_{i=0} (-1)^i {3 \choose 3-i} (3-i)^5 &= {3 \choose 3} 3^5 - {3 \choose 2} 2^5 + {3 \choose 1} 1^5 - {3 \choose 0} 0^5 \\&= 1 \cdot 243 - 3 \cdot 32 + 3 \cdot 1 - 1 \cdot 0 \\&= 243 - 96 + 3 - 0 \\&= 150\end{aligned}$$

KASUS 2: Ada anggota $X$ selain $a$ yang dipetakan ke $1 \in Y$

Banyaknya fungsi yang mungkin sama dengan banyaknya fungsi surjektif dari $X-\{a\}=\{b,c,d,e,f\}$ ke $Y=\{1,2,3,4\}$, yaitu$$\begin{aligned}\sum^4_{i=0} (-1)^i {4 \choose 4-i} (4-i)^5 &= {4 \choose 4} 4^5 - {4 \choose 3} 3^5 + {4 \choose 2} 2^5 - {4 \choose 1} 1^5 + {4 \choose 0} 0^5 \\&= 1 \cdot 1024 - 4 \cdot 243 + 6 \cdot 32 - 4 \cdot 1 + 1 \cdot 0 \\&= 1024 - 972 + 192 - 4 + 0 \\&= 240\end{aligned}$$Jadi, banyaknya fungsi surjektif $f:X \rightarrow Y$ dengan $f(a)=1$ adalah $150+240=390$.

Sebagai penutup, saya akan memberikan soal latihan untuk pembaca.

Latihan

Diberikan himpunan $X=\{a,b,c,d,e,f\}$ dan $Y=\{1,2,3,4\}$. Tentukan banyaknya fungsi surjektif $f:X \rightarrow Y$, jika diketahui $f(a)=1$ dan $f(b)=2$.