Banyaknya Fungsi Surjektif yang Mungkin dari A ke B

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{align*} S_1 &= N(c_1)+N(c_2)+ \cdots + N(c_n) \\ &= (n-1)^m + (n-1)^m + \cdots + (n-1)^m \end{align*}

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{align*} 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{align*}

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{align*} \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{align*}

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
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{align*} \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{align*}

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{align*} \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{align*}

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.

Anda bisa menuliskan jawaban pada kolom komentar, atau mengirimkan via email ke [email protected]
Semoga bermanfaat. 🙂

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.