Prinsip Injeksi dan Bijeksi
Prinsip injeksi dan bijeksi dibahas dalam mareri kombinatorik dimana kombinatorik merupakan bidang yang ikut diujikan pada matematika olimpiade. Sebelum membahas prinsip injeksi dan bijeksi, marilah kita mengingat kembali apa yang dimaksud dengan fungsi injektif dan bijektif. Masih ingatkah Anda apa yang dimaksud fungsi injektif dan bijektif? Definisi secara formal, telah kita bahas pada tulisan Definisi Fungsi dan Fungsi-fungsi Khusus. Untuk memahami prinsip injeksi dan bijeksi bacalah contoh masalah berikut ini.
Pada suatu pertemuan diketahui bahwa setiap pria datang harus dengan istrinya, sedangkan suami dapat datang sendiri. Kemudian, diketahui bahwa jumlah laki-laki yang datang adalah 100 orang. Tanpa menghitung lagi, kita tahu bahwa jumlah wanita $\le 100$. Tetapi, jika diketahui bahwa semua laki-laki juga datang dengan pasangannya, maka kita tahu bahwa jumlah laki-laki dan wanita sama banyak. Ini adalah prinsip injeksi dan bijeksi dimana kita anggap A himpunan wanita yang datang dan B himpunan laki-laki yang datang, sehingga:
- Jika tidak semua laki-laki datang dengan pasangannya maka $n(A) < n(B) $
- Jika semua laki-laki datang dengan pasangannya maka $n(A)=n(B) $.
Prinsip Injeksi dan Bijeksi:Misalkan A dan B dua himpunan berhingga dan ada fungsi $f: \ A \rightarrow B $.
- Jika f bersifat injektif maka $n(A) \le n(B) $.
- Jika f bersifat bijektif maka $n (A)=n (B)$
Contoh. Misalkan X={1, 2, 3, 4, 5, 6, 7}
- Tuliskan semua kombinasi yang terdiri dari 3 unsur di X tetapi tidak saling berurutan.
- Tuliskan banyaknya kombinasi 3 unsur tersebut.
1. Kita mulai dengan angka 1, maka pilihan berikutnya adalah 3, 4, 5, 6, atau 7. Kemudian pilih angka ke-tiganya. Sebagaimana tampak pada gambar berikut ini.
Hasilnya adalah {1, 3, 5}, {1, 3, 6}, {1, 3, 7}, {1, 4, 6}, {1, 4, 7}, dan {1, 5, 7}. Kemudian mulai dengan angka 2, yaitu {2, 4, 6}, {2, 4, 7}, {2, 5, 7} dan mulai dengan angka 3 adalah {3, 5, 7}. Sehingga jumlah totalnya adalah 10.
2. Kita akan menghitung hasil di atas dengan lebih cerdik. Misalkan A adalah himpunan semua kombinasi tiga unsur dengan unsur tidak ada yang berurutan. Misalkan $A=\{a_1, a_2, a_3\}$ adalah satu unsur di A. Kita tahu bahwa $a_1, \ a_2 \ a_3 \in X $ dan $1 \le a_1 < a_2 < a_3$. Kemudian kita bentuk himpunan $\{a_1,a_2,a_3-2 \}$. Unsur ini semua berbeda dan berada di Y={1, 2, 3, 4, 5}. Jika B adalah kombinasi tiga unsur dari elemen di Y, mudah dibuktikan bahwa $n (A)=n (B) $. Dalam hal ini $n (B)= C_3^5$.
Cukup sampai di sini pembahasan singkat kita mengenai Prinsip Injeksi dan Bijeksi yang nantinya kita gunakan untuk menyelesaikan masalah-masalah banyaknya kombinasi. Semoga bermanfaat.
Referensi: Langkah Awal Menuju Olimpiade Matematika SMA, Wono Setya Budhi.
Hasilnya adalah {1, 3, 5}, {1, 3, 6}, {1, 3, 7}, {1, 4, 6}, {1, 4, 7}, dan {1, 5, 7}. Kemudian mulai dengan angka 2, yaitu {2, 4, 6}, {2, 4, 7}, {2, 5, 7} dan mulai dengan angka 3 adalah {3, 5, 7}. Sehingga jumlah totalnya adalah 10.
2. Kita akan menghitung hasil di atas dengan lebih cerdik. Misalkan A adalah himpunan semua kombinasi tiga unsur dengan unsur tidak ada yang berurutan. Misalkan $A=\{a_1, a_2, a_3\}$ adalah satu unsur di A. Kita tahu bahwa $a_1, \ a_2 \ a_3 \in X $ dan $1 \le a_1 < a_2 < a_3$. Kemudian kita bentuk himpunan $\{a_1,a_2,a_3-2 \}$. Unsur ini semua berbeda dan berada di Y={1, 2, 3, 4, 5}. Jika B adalah kombinasi tiga unsur dari elemen di Y, mudah dibuktikan bahwa $n (A)=n (B) $. Dalam hal ini $n (B)= C_3^5$.
Cukup sampai di sini pembahasan singkat kita mengenai Prinsip Injeksi dan Bijeksi yang nantinya kita gunakan untuk menyelesaikan masalah-masalah banyaknya kombinasi. Semoga bermanfaat.
Referensi: Langkah Awal Menuju Olimpiade Matematika SMA, Wono Setya Budhi.