KOMBINATORIK

Hukum Penggandaan
Misalkan suatu percobaan terdiri atas dua operasi atau lebih. Setiap kemungkinan/cara dalam operasi pertama dapat dilanjutkan dengan operasi kedua, dan setiap operasi kedua dapat dilanjutkan dengan operasi ketiga dan seterusnya. Maka banyaknya cara yang dapat dibentuk dalam percobaan tersebut dapat diperoleh berdasarkan hasil kali dari masing-masing kemungkinan tiap-tiap operasi.

Misalkan kita mau pergi dari Jakarta ke Bandung dengan bus umum. Dari Jakarta ke Bogor ada tiga cara, yaitu : lewat parung, lewat Cibinong, dan lewat tol Jagorawi. Sedangkan dari Bogor ke Bandung ada dua cara, yaitu : lewat Puncak dan lewat Sukabumi. Sehingga banyaknya cara untuk pergi dari Jakarta ke Bandung adalah 3 x 2 = 6 cara.

Teorema :
Jika operasi pertama dapat dilakukan dengan n1 cara dan setiap cara ini dilanjutkan dengan operasi kedua yang dapat dilakukan dengan n2 cara, dan setiap cara sebelumnya dilanjutkan lagi dengan operasi ketiga yang dapat dilakukan dengan n3 cara, dan seterusnya sampai sederetan k buah operasi, maka semua operasi tersebut dapat dikerjakan secara bersama-sama dengan = n1 x n2 x n3 x …. x nk cara.

Contoh :
Misalkan dalam suatu ujian soalnya terdiri atas 10 soal pilihan ganda. Setiap soal terdiri atas empat pilihan (A, B, C, D). Dengan berapa cara ke-10 soal tersebut dapat dijawab ?

Jawab : 4 x 4 x 4 x …. x 4 = 410 = 1048576 cara
Soal :
Seseorang akan membuat plat nomor yang masing-masing terdiri atas lima digit. Tiga digit pertama diisi dengan huruf kapital dan dua digit terakhir diisi dengan angka. Huruf O dan I tidak boleh digunakan karena mirip dengan angka 0 dan 1. Huruf pertama harus konsonan, dan digit terakhir harus angka genap. Tentukan berapa banyak plat nomor berbeda yang dapat dibuat ?

Jawab : 21 x 24 x 24 x 10 x 5 = 604800 buah plat nomor

Hukum Penjumlahan
Hukum penjumlahan digunakan untuk menghitung banyaknya cara yang diperoleh dalam suatu percobaan yang mengandung lebih dari satu alternatif/pilihan. Untuk memudahkan pemahaman, kasus ini dapat disetarakan dengan perhitungan anggota gabungan dua buah gugus atau lebih yang saling terpisah, dalam hal ini banyaknya cara yang dapat dilakukan untuk masing-masing alternatif dapat disetarakan dengan jumlah anggota masing-masing gugus.

Misalkan kita mau pergi dari Bogor ke Jakarta. Berdasarkan jenis angkutan umum yang digunakan, ada dua kemungkinan yaitu naik bus atau naik kereta api. Jika naik bus, maka ada tiga cara, yaitu lewat Parung, Cibinong, dan Tol Jagorawi. Sedangkan jika naik kereta api hanya ada satu cara. Jadi banyaknya cara pergi dari Bogor ke Jakarta adalah 3 + 1 = 4 cara.

Teorema :
Jika suatu operasi diselesaikan dengan k alternatif, alternatif pertama dapat dilakukan dengan n1 cara, dan seterusnya sampai alternatif k dengan nk cara, maka operasi tersebut dapat dilakukan dengan (n1 + n2 + …. + nk) cara



PERMUTASI

Definisi : Permutasi adalah susunan yang dapat dibentuk dari sekumpulan obyek yang dipilih sebagian atau seluruhnya dengan memperhatikan urutan.

Teorema 1 : Jika ada n buah benda yang berbeda maka banyaknya permutasi (susunan berbeda) dari n benda tersebut adalah P(n,n) = n !.
Contoh : Misalkan dalam suatu kelas yang terdiri atas 6 mahasiswa dan 4 mahasiswi, semua mahasiswa akan disusun berdasarkan hasil ujiannya. Jika tidak ada dua orang atau lebih yang mendapat nilai yang sama, maka banyaknya urutan yang mungkin adalah
Jawab : banyaknya ada 10 ! = 10 x 9 x 8 x … x 1 = 3628800

Teorema 2 : Jika benda sejenis tidak dibedakan, banyaknya permutasi dari n buah benda dengan n1 benda memiliki jenis pertama, n2 benda memiliki jenis kedua dan seterusnya hingga nk benda memiliki jenis ke-k adalah
Contoh : Tentukan banyaknya permutasi (susunan huruf yang berbeda) yang dapat dibuat dengan menggunakan huruf-huruf yang terdapat pada kata “ MATEMATIKA “
Jawab : banyaknya = = 151200 buah

Teorema 3 : Banyaknya permutasi dari n benda yang berbeda jika diambil r benda sekaligus (disebut permutasi tingkat r dari n) adalah
P(n,r) =
Contoh : Suatu panitia yang terdiri atas 3 mahasiswa (ketua, sekretaris, dan bendahara) akan dipilih dari 8 mahasiswa yang ada. Maka banyaknya susunan panitia berbeda yang mungkin adalah
Jawab : P(8,3) = = 336 buah
SOAL-SOAL
1. Misalkan dalam suatu kelas yang terdiri atas 6 mahasiswa dan 4 mahasiswi, semua mahasiswa akan disusun berdasarkan hasil ujiannya. Jika tidak ada dua orang atau lebih yang mendapat nilai yang sama, maka banyaknya urutan yang mungkin jika yang pria diurut sesama pria lalu diikuti oleh yang wanita diurut sesama wanita adalah ?
2. Misalkan kita memiliki 3 buah buku matematika dengan judul yang berbeda, 4 buah buku computer dengan judul yang sama, dan 5 buah buku fisika dimana 2 diantaranya memiliki judul yang sama. Tentukan banyaknya susunan berbeda jika semua buku-buku tersebut akan disusun memanjang dalam suatu rak buku ?
3. Misalkan tersedia 9 buah digit angka yaitu 1 , 2 , 3 , … , 9. Jika akan dibuat suatu nomor yang terdiri atas 4 digit dengan syarat setiap digit hanya boleh digunakan satu kali, maka berapa banyak nomor berbeda ? dan berapa banyak nomor berbeda dengan nomor genap ?



KOMBINASI

Definisi : Kombinasi adalah kelompok yang dapat dibentuk dari sekumpulan obyek yang dipilih sebagian atau seluruhnya dengan tidak memperhatikan urutan.

Teorema 1 : Banyaknya kombinasi dari n benda yang berbeda jika dipilih sebanyak r buah benda adalah
C (n,r) =
Contoh : Misalkan sebuah panitia terdiri atas 3 mahasiswa akan dipilih dari 8 mahasiswa yang ada, maka banyaknya panitia berbeda yang dapat dibentuk adalah
Jawab : C (8,3) = = 56 buah

Teorema 2 : Banyaknya cara membagi n buah benda yang berbeda ke dalam k buah sel, dimana sel pertama berkapasitas n1 benda, sel kedua berkapasitas n2 benda, dan seterusnya sampai sel ke-k berkapasitas nk benda (urutan benda dalam tiap sel tidak diperhatikan) adalah

Contoh : Misalkan ada 15 mahasiswa akan pergi bertamasya dengan menggunakan 3 buah mobil. Mobil pertama berkapasitas 5 orang, mobil kedua berkapasitas 4 orang dan mobil ketiga berkapasitas 6 orang. Maka banyaknya cara berbeda untuk mengalokasikan 15 mahasiswa ke dalam 3 mobil tersebut adalah
Jawab : = 630630 cara

Teorema 3 : Jika ada n buah benda akan disebar ke k buah tempat, maka ada sebanyak kn cara penyebarannya.
Contoh : Misalkan ada 3 buah kelereng akan disebar ke 3 buah kotak, maka banyaknya cara penyebaran adalah
Jawab : banyaknya = 33 = 27 cara

SOAL-SOAL
1. Misalkan sebuah panitia yang terdiri atas 3 orang akan dipilih dari 4 pasang suami istri yang ada, maka banyaknya panitia berbeda yang dapat dibentuk jika panitia yang terbentuk harus terdiri atas 2 pria dan 1 wanita adalah ?
2. Misalkan ada 15 orang terdiri dari 3 orang guru dan 12 orang siswa akan pergi bertamasya dengan menggunakan 3 buah mobil. Mobil pertama berkapasitas 5 orang, mobil kedua berkapasitas 4 orang dan mobil ketiga berkapasitas 6 orang. Maka banyaknya cara berbeda untuk mengalokasikan 15 mahasiswa ke dalam 3 mobil tersebut jika setiap mobil ada seorang guru adalah ?
3. Misalkan ada 3 buah kelereng akan disebar ke 3 buah kotak, maka banyaknya cara penyebaran jika setiap kotak harus berisi paling sedikit sebuah kelereng adalah ?
4. Misalkan ada 3 buah kelereng akan disebar ke 3 buah kotak, maka banyaknya cara penyebaran jika paling sedikit dua buah kotak berisi kelereng adalah ?



R E L A S I

Definisi :
(1) Relasi R pada himpunan X disebut relasi keekuivalenan, jika R refleksif, simetris dan transitif
(2) Relasi R pada himpunan X disebut urutan parsial, jika R refleksif, antisimetris dan transitif
Sifat-sifat relasi :
(a) Relasi R pada himpunan X disebut refleksif jika untuk setiap x  X maka (x,x)  R
(b) Relasi R pada himpunan X disebut simetris jika (x,y)  R maka (y,x)  R untuk semua x, y  X
(c) Relasi R pada himpunan X disebut antisimetris jika (x,y)  R dan x ≠ y maka (y,x)  R untuk semua x, y  X
(d) Relasi R pada himpunan X disebut transitif jika (x,y)  R dan (y,z)  R maka (x,z)  R untuk semua x, y, z  X

Contoh :
(1) Misalkan R adalah relasi pada X = { 1 , 2 , 3 , 4 } yang didefinisikan oleh (x,y)  R jika x  y dengan x,y  X
(2) Relasi R pada X = { a , b , c , d } yang didefinsikan oleh R = { (a,a) , (b,c) , (c,b) , (d,d) }
(3) Periksa soal nomor (1) dan (2) apakah R refleksif, simetris, antisimetris, dan transitif !



FUNGSI DAN KOMPOSISI FUNGSI
G R U P

Definisi : Suatu himpunan G yang tidak kosong dan suatu operasi biner “o” yang didefinisikan pada G membentuk suatu grup bila dan hanya bila memenuhi sifat-sifat berikut :
(1) Operasi “o” pada G bersifat assosiatif, yaitu untuk setiap a, b, c  G maka ( a o b ) o c = a o ( b o c )
(2) G terhadap operasi biner “o” mempunyai elemen identitas, yaitu ada I  G sedemikian hingga a o I = I o a = a untuk setiap a  G
(3) Setiap elemen G mempunyai invers terhadap operasi biner “o” dalam G, yaitu untuk setiap a  G ada a-1  G sedemikian hingga a o a-1 = a-1 o a = I, dimana I adalah elemen identitas dari G
Jika himpunan G terhadap operasi biner “o” membentuk suatu grup, maka grup G ini dinyatakan dengan notasi “(G;o)”. Tidak setiap grup memiliki sifat komutatif terhadap operasi binernya. Jika grup (G;o) masih memenuhi sifat bahwa :
(4) Operasi biner “o” pada G bersifat komutatif, yaitu untuk setiap a, b  G maka a o b = b o a. Maka grup (G;o) disebut grup abelian (grup komutatif)
Contoh :
(1) Himpunan bilangan bulat B = { …, -2, -1, 0, 1, 2, … } terhadap operasi biner penjumlahan apakah membentuk suatu grup ?
(2) H = { 0, 1, 2, 3 } yaitu himpunan semua bilangan terkecil modulo 4. Operasi penjumlahan modulo 4 adalah operasi biner pada H. Apakah H membentuk suatu grup ?
(3) Himpunan bilangan asli A = { 1, 2, 3, 4, … } pada operasi biner perkalian apakah membentuk suatu grup ?
(4) Himpunan bilangan Riil (terdiri dari bilangan bulat dan bilangan pecahan) pada operasi biner perkalian apakah membentuk suatu grup ?

SOAL-SOAL GRUP
1. H = { 0 , 1 , 2 , 3 }, yaitu himpunan semua residu terkecil modulo 4. Apakah H pada operasi penjumlahan modulo 4 merupakan suatu grup?
2. G = { 2 , 4 , 8 } adalah himpunan semua residu terkecil modulo 14. Apakah G pada operasi perkalian modulo 14 merupakan suatu grup?
3. S = { 1 , - 1 , i , - i }. Tunjukkan bahwa perkalian himpunan S merupakan suatu grup? Dengan i = √- 1 atau i2 = - 1
4. M = { 1 , 2 , 3 , 4 } adalah himpunan semua residu terkecil modulo 5. Apakah M pada operasi perkalian modulo 5 merupakan suatu grup?
5. Operasi-operasi biner o dan ∆ berturut-turut pada A = { p , q , r , t } didefinisikan seperti pada tabel-tabel berikut :
o p q r t ∆ p q r t
p
q
r
t p q r t
q q r t
r r r t
t t t t p
q
r
t p p p p
p q q q
p q r r
p q r t
Tunjukkan :
(a) Apakah pada A berlaku sifat distributive kanan ∆ terhadap o
(b) Apakah pada A berlaku sifat distributive kiri ∆ terhadap o
(c) Apakah pada A berlaku sifat distributive kanan o terhadap ∆
(d) Apakah pada A berlaku sifat distributive kiri o terhadap ∆






SIFAT-SIFAT SEDERHANA DARI GRUP

1. Sifat Kanselasi (Penghapusan)
( G ; o ) suatu grup, maka untuk setiap a, b, c,  G, berlaku
(a) Jika a o b = a o c maka b = c (Kanselasi kiri)
(b) Jika b o a = c o a maka b = c (Kanselasi kanan)
2. Sifat Penyelesaian Tunggal
( G ; o ) suatu grup dan a, b  G maka persamaan a o x = b dan y o a = b mempunyai penyelesaian tunggal.
3. Sifat Invers dari Invers
Jika ( G ; o ) suatu grup, maka untuk setiap a  G, invers dari invers a adalah a atau ditulis untuk setiap a  G, maka ( a-1 )-1 = a.
4. Sifat Invers
( G ; o ) adalah suatu grup, maka untuk setiap a, b  G berlaku ( a o b )-1 = b-1 o a-1

Contoh soal
1. Jika ( G ; o ) suatu grup sedemikian rupa sehingga untuk setiap a, b  G berlaku ( a o b )2 = a2 o b2 maka buktikan bahwa ( G ; o ) suatu grup abelian (komutatif)
2. Jika ( G ; o ) suatu grup sedemikian rupa sehingga untuk setiap a, b  G berlaku ( a o b )-1 = a-1 o b-1 maka buktikan bahwa ( G ; o ) suatu grup abelian (komutatif)
3. ( G ; o ) suatu grup berorder genap, buktikan bahwa ada elemen a  G dengan a  I dan a2 = I.



TEOREMA GRUP

1. Jika himpunan S terhadap operasi biner o mempunyai elemen identitas maka elemen identitas itu tunggal (satu).
2. Misalkan o adalah suatu operasi biner pada himpunan S. Jika x  S mempunyai invers terhadap operasi o maka invers dari x tersebut adalah tunggal (satu).
3. Misalkan operasi-operasi biner  dan o terdefinisikan pada suatu himpunan S. Jika untuk setiap x, y, z  S berlaku x  ( y o z ) = ( x  y ) o ( x  z ), maka pada S berlaku sifat distributif kiri  terhadap o.
Contoh : Jika a, b, c  S didefinisikan a  b = a2 b tunjukkan berlaku distributif kiri  terhadap penjumlahan.
a  ( b + c ) = a2 ( b + c ) = a2 b + a2 c .... (1)
( a  b ) + ( a  c ) = a2 b + a2 c …. (2)
Dari (1) dan (2) diperoleh a  ( b + c ) = ( a  b ) + ( a  c ) atau berlaku distributif kiri  terhadap penjumlahan.
4. Misalkan operasi-operasi biner  dan o terdefinisikan pada suatu himpunan S. Jika untuk setiap x, y, z  S berlaku ( y o z )  x = ( y  x ) o ( z  x ), maka pada S berlaku sifat distributif kanan  terhadap o.
Contoh : Jika a, b, c  S didefinisikan a  b = a2 b tunjukkan berlaku distributif kanan  terhadap penjumlahan.
( b + c )  a = ( b + c )2 a = (b2 + 2bc + c2 ) a = b2 a + 2abc + c2 a …. (1)
( b  a ) + ( c  a ) = b2 a + c2 a ….. (2)
Dari (1) dan (2) diperoleh ( b + c )  a  ( b  a ) + ( c  a ) atau tidak berlaku distributif kanan  terhadap penjumlahan.



GRUP DARI KLEIN

Perhatikan persegi panjang ABCD pada gambar berikut :
D Y C
0 X

A B



X dan Y adalah sumbu-sumbu simetri persegí panjang ABCD. Persegi panjang ABCD diadakan transformasi sehingga persegi panjang ABCD tetap pada bingkainya. Transformasi-transformasi itu adalah I yaitu persegi panjang tetap seperti semula karena diputar satu putaran (360 derajat) dengan pusat O, H yaitu diputar setengah putaran (180 derajat) dengan pusat O, Rx yaitu refleksi (dicerminkan) terhadap sumbu X, dan Ry yaitu refleksi (dicerminkan) terhadap sumbu Y. Perhatikan sekarang G = { I , H , Rx , Ry }, dan operasi o didefinisikan pada G bahwa Rx o Ry berarti refleksi terhadap sumbu Y dilanjutkan dengan refleksi terhadap sumbu X dan hasilnya sama dengan diputar setengah putaran dengan pusat O, yaitu H, sehingga Rx o Ry = H yang dapat dijelaskan sebagai berikut :





















Operasikanlah setiap pasang elemen-elemen dari G terhadap operasi o, dan lengkapilah tabel berikut :
o I H Rx Ry
I
H
Rx
Ry I H Rx Ry
H ... ... ...
Rx Ry ... H
Ry ... ... ...
Amatilah tabel di atas apa perbedaan yang ada jika dibandingkan dengan grup yang sudah anda kenal.

Perhatikan himpunan S = { 1 , 2 , 3 , 4 }. Banyaknya permutasi elemen-elemen himpunan S adalah 4! = 4 x 3 x 2 x 1 = 24. Setiap permutasi dapat dipandang sebagai suatu fungsi dari S ke S. Misalnya :
α =
β =
γ =
δ =
Misalkan operasi o didefinisikan operasi dilanjutkan pada himpunan permutasi-permutasi tersebut, misalnya :
β o γ = o = = δ
γ o δ = o = = β
dan seterusnya lengkapi tabel berikut :
o α β γ δ
α
β
γ
δ α β γ δ
β α δ γ
γ β
δ

Notasi lain yang lebih singkat untuk suatu permutasi ditulis dengan notasi sikel sebagai berikut :
θ = ditulis sebagai sikel ( 1 2 3 4 )
Sikel ( 1 2 3 4 ) dimaksudkan 1 → 2, 2 → 3, 3 → 4, 4 → 1.
μ = ditulis sebagai sikel ( 1 2 )
Sikel ( 1 2 ) dimaksudkan 1 → 2, 2 → 1, 3 → 3, 4 → 4. Dihilangkan karena memasangkan ke dirinya sendiri. Karena permutasi hanya dipandang urutannya, maka penulisan permutasi sebagai sikel dapat bermacam-macam asal urutannya tetap. Misalnya ( 1 2 3 4 ) = ( 2 3 4 1 ) = ( 3 4 1 2 ) = ( 4 1 2 3 ) dan ( 1 2 ) = ( 2 1 ).
α = dapat ditulis sebagai sikel ( 1 ) = ( 2 ) = ( 3 ) = ( 4 )
γ = dapat ditulis sebagai sikel ( 1 3 ) ( 2 4 )
Sikel ( 1 3 ) ( 2 4 ) dimaksudkan 1 → 3, 3 → 1, 2 → 4, 4 → 2.
β = dapat ditulis sebagai sikel ( 1 2 ) ( 3 4 )
δ = dapat ditulis sebagai sikel ( 1 4 ) ( 2 3 )
Operasi o pada permutasi tidak bersifat komutatif, seperti berikut :
( 1 2 3 4 ) o ( 2 3 ) = ( 1 3 4 )
( 2 3 ) o ( 1 2 3 4 ) = ( 1 2 4 )
Jadi ( 1 2 3 4 ) o ( 2 3 ) ≠ ( 2 3 ) o ( 1 2 3 4 )

GRAF (GRAPH)


Graf G didefinisikan sebagai pasangan himpunan (V,E) yang dalam hal ini dimaksudkan:
V = Himpunan berhingga dan tidak kosong dari simpul-simpul (vertices atau node) = { v1 , v2 , .... , vn }
E = Himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul = { e1 , e2 , .... , en }
Atau dapat ditulis singkat notasi G = (V,E).
Contoh : Gambar (a) graf sederhana, (b) graf ganda, dan (c) graf semu
(e) V = { 1 , 2 , 3 , 4 }
E = { (1,2) , (1,3) , (2,3) , (2,4) , (3,4) }
(f) V = { 1 , 2 , 3 , 4 }
E = { (1,2) , (1,3) , (1,3) , (2,3) , (2,4) , (3,4) , (3,4) }
= { e1 , e2 , e3 , e4 , e5 , e6 , e7 }
(g) V = { 1 , 2 , 3 , 4 }
E = { (1,2) , (1,3) , (1,3) , (2,3) , (2,4) , (3,4) , (3,4) , (3,3) }
= { e1 , e2 , e3 , e4 , e5 , e6 , e7 , e8 }

Contoh : Graf tak berarah dan graf berarah
Aplikasi graf :
1. Rangkaian listrik
2. Isomer senyawa kimia karbon
3. Basis data
4. Pengujian program
5. Teori Otomata