matematika_diskrit
DESCRIPTION
Metode Pencacahan FundamentalTRANSCRIPT
1
BAB 1
METODE FUNDAMENTAL PENCACAHAN
Dalam bab ini diperkenalkan konsep dasar dari permutasi dan kombinasi, serta
perhitungan atau numerasi (pencacahan) menyangkut permutasi maupun kombinasi. Diawali
bab ini dengan dua prinsip utama dalam numerasi.
1.1 Prinsip Dasar dan Pencacahan
Terdapat dua prinsip atau aturan utama dalam pencacahan yaitu aturan
perkalian ( Multiplication Rule ) dan aturan penambahan ( Addition Rule )
1.1.1 Aturan Perkalian ( Multiplication Rule )
Bunyi aturan perkalian :
Jika kejadian pertama dapat terjadi dalam n1 cara, dan setiap kejadian pertama
diikuti oleh kejadian kedua dengan n2 cara, dan setiap kejadian kedua diikuti oleh
kejadian ketiga dengan n3 cara, dan seterusnya, dan setiap kejadian
ke-(p-1) diikuti oleh kejadian ke-p yang terjadi dalam np cara, maka kejadian pertama,
kedua, ketiga, β¦ , ke-p.
Secara bersama-sama terjadi dalam n1 x n2 x n3 x β¦ x np cara.
CONTOH :
1. Berapa macam menu makan siang yang terdiri atas sup, sandwich, desert dan
minuman yang dapat dipilih dari 4 macam sup, 3 jenis sandwich , 5 desert dan 4
minuman ?
Penyelesaian :
Banyaknya cara untuk memilih sup ada 4 cara
Banyaknya cara untuk memilih sandwich ada 3 cara
Banyaknya cara untuk memilih desert ada 5 cara, dan
Banyaknya cara untuk memilih minuman ada 4 cara
Jadi banyaknya macam menu makan siang adalah 4 x 3 x 5 x 4 = 240
2
2. Berapa banyak bilangan 4 digit yang tidak mengandung angka yang berulang ?
Penyelesaian :
Digit pertama ada 10 kemungkinan angka
Digit kedua ada 9 kemungkinan angka
Digit ketiga ada 8 kemungkinan angka
Digit keempat ada 7 kemungkinan angka
Jadi banyaknya bilangan 4 digit yang tidak mengandung angka yang berulang
adalah sebanyak 10 x 9 x 8 x 7 = 4536
SOAL LATIHAN 1.1.2
1. Sebuah sandi-lewat (password) panjangnya 6 sampai 8 karakter.
Karakter boleh berupa huruf atau angka. Berapa banyak kemungkinan
sandi-lewat yang dapat dibuat?
2. Bit biner hanya 0 dan 1. Berapa banyak string biner yang dapat dibentuk jika :
a. Panjang string 5 bit
b. Panjang string 8 bit
1.1.2 Aturan Penambahan ( Addition Rule )
Bunyi aturan penambahan :
Jika kejadian pertama dapat terjadi dalam n1 cara, kejadian kedua secara
terpisah dapat terjadi dalam n2 cara, dan seterusnya, kejadian ke-p secara terpisah
terjadi dalam np cara maka kejadian pertama atau kedua, β¦, atau kejadian ke-p.
Dapat terjadi dalam n1 + n2 + β¦ + np cara.
CONTOH :
1. Seseorang mahasiswa ingin memebeli sebuah motor. Ia dihadapkan untuk memilih
pada setu jenis dari tiga merek motor, honda 3 pilihan, susuki 2 pilihan, dan
yamaha 2 pilihan. Berapa cara yang dapat dilakukan ?
Penyelesaian :
Dengan demikian, mahasiswa tersebut mempunyai pilihan sebanyak 3+2+2=7
pilihan
3
2. Seorang Guru SMA di daerah, mengajar murid kelas X, kelas XI, dan kelas XII.
Jika jumlah murid kelas X adalah 25 orang dan jumlah murid kelas XI adalah 27
orang serta jumlah murid kelas XII adalah 20 orang. Berapa banyak jumlah murid
yang diajar guru ?
Penyelesaian :
Maka Guru SMA tersebut adalah mengajar 25+27+20= 72 murid
SOAL LATIHAN 1.1.2
1. Dalam Perpustakaan terdapat 10 buku Matematika, 25 buku Statistik dan 5 buku
social. Berapa cara yang dapat dilakukan untuk mengambil 1 buku ?
2. Sekelompok mahasiswa terdiri dari 4 orang pria dan 3 orang wanita. Berapa cara
memilih 1 orang yang mewakili kelompok tersebut (tidak perduli pria atau wanita)?
1.2 Permutasi
Permutasi adalah penyusunan beberapa objek dari suatu grup dengan
memperhatikan urutan. Didalam permutasi urutan diperhatikan.
Rumus Permutasi : P ( n , r ) = π!
( πβπ )! Syarat : n r atau n = r
Notasi : nPr atau Pππ
atau P (n, r)
CONTOH :
1. Sebuah dalam tim olahraga ada 10 orang siswa yang dicalonkan untuk menjadi
pemain. Namun hanya 5 orang boleh menjadi pemain utama. Tentukan banyak cara
yang bisa dipakai untuk memilih para pemain utama tersebut?
Penyelesaian:
Diketahui n = 10 dan r = 5
P ( n , r ) = π!
( πβπ )!
P ( 10 , 5 ) = 10!
( 10β5 )! =
10!
4! =
10Γ 9 Γ 8 Γ 7Γ 6Γ 5 Γ 4!
4! = 151.200 cara
4
SOAL LATIHAN 1.2
1. Menjelang Pergantian kepengurusan BEM FKIP UHAMKA akan dibentuk panitia
inti sebanyak 2 orang (terdiri dari ketua dan wakil ketua), calon panitia tersebut ada
6 orang yaitu: a, b, c, d, e, dan f. Ada berapa pasang calon yang dapat duduk
sebagai panitia inti tersebut?
2. Sebuah bilangan 5 angka dibentuk dari angka 1,2,3,4,5,6,7 berapakah banyak
bilangan yang mungkin jika angka-angka dalam bilangan tersebut tidak ada yang
sama?
1.2.1 Permutasi Siklik Biasa
Dapat dikatakan permutasi siklik jika beberapa objek yang dijajar melingkar
(pada suatu lingkaran) dengan memperhatikan arah melingkarnya, misalnya searah
putaran jarum jam.
CONTOH :
1. Ada Empat kubus yang diberi label A, B, C, dan D yang akan dijajar melingkar
searah dengan putaran jarum jam ?
Penyelesaian :
Maka dari 4 objek itu akan didapat enam buah permutasi siklik yaitu, (ABCD),
(ABDC), (ACBD), (ACDB), (ADBC), dan (ADCB). Perhatikanlah bahwa dari
setiap permutasi-4 siklik tersebut terdapat 4 permutasi linear. Sehingga seluruhnya
terdapat 6 Γ 4 = 24 permutasi linear.
Jika pengulangan tidak diperkenankan, maka hubungan antara banyaknya
permutasi siklik dan banyaknya permutasi linear disajikan dalam teorema berikut.
Teorema 1.1
π½πππ π πππ π ππ’π ππππππππ ππ’πππ‘ πππ ππ‘ππ, ππππ
π β (π, π) = ππ; dan π(π, π) =π!
πβπ, untuk π β€ π
5
Teorema 1.2
Jika ππ(π, π) menyatakan banyaknya permutasi-k siklik dari n objek berbeda,
maka
ππ(π, π) =π(π, π)
π!=
π!
π(π β π)!
Khususnya,
ππ(π, π) = (π β 1)!
Bukti;
Karena dari setiap permutasi-k siklik terdapat k buah permutasi-k linear, maka
berdasarkan aturan perkalian diperoleh
ππ(π, π) Γ π = π(π, π)
Ekuivalen dengan
ππ(π, π) Γ π =π(π, π)
π
Berdasarkan teorema 1.1
diperoleh, ππ(π, π) =π!
πβπ ; Jika π = π diperoleh
ππ(π, π) =π!
π. 0!=
π(π β 1)!
π= (π β 1)!
Sehingga teorema 1.2 terbukti.
CONTOH :
1. Sekelompok mahasiswa yang terdiri dari 10 orang akan mengadakan rapat dan
duduk mengelilingi sebuah meja, ada berapa carakah kelima mahasiswa tersebut
dapat diatur pada sekeliling meja tersebut ?
Penyelesaian:
ππ(π, π) = (π β 1)!
ππ(10 , 5) = (10 β 1)!
Catatan: Jika arah putaran tidak dibedakan, artinya memutar
searah ataupun berlawanan arah dengan arah putaran jarum jam
tidak dibedakan, maka permutasi siklik (ABCD) ekuivalen
dengan permutasi siklik (ADBC).
6
= 9!
= 9 Γ 8 Γ 7 Γ 6 Γ 5 Γ 4 Γ 3 Γ 2 Γ 1
= 362880 cara
2. Dalam sebuah keluarga yang terdiri dari seorang ayah, seorang ibu, dan 3 orang
anaknya makan bersama dan mengelilingi sebuah meja makan. Berapa banyaknya
cara yang berlainan saat mereka dapat duduk, jika:
a. Mereka berpindah-pindah tempat ?
b. Ayah dan ibu selalu berdekatan ?
Penyelesaian:
a. Banyaknya anggota keluarga adalah 5 orang (seorang ayah, seorang ibu, dan 3
orang anak). Sehingga, banyaknya cara yang berlainan saat mereka duduk
berpindah-pindah tempat adalah (5 β 1)! = 4! = 24 cara. Perhatikan gambar
berikut.
b. Ayah dan ibu selalu berdampingan, sehingga pasangan ini dapat kita anggap
satu. Sehingga terdapat 4 objek yang akan disusun secara siklis. Akan tetapi
pasangan ayah dan ibu dapat disusun kembali menjadi 2P2 cara. Sehingga
banyaknya susunan agar ayah dan ibu selalu berdekatan adalah (4 β 1)! Γ 2P2 =
3! Γ 2! = 12 cara
SOAL LATIHAN 1.2.1
1. Dalam suatu pesta terdapat 7 orang yang duduk mengelilingi sebuah meja makan
berbentuk lingkaran. Maka ada berapa cara yang mungkin dapat dibuat untuk
menempati posisi yang berlainan?
2. 5 orang direktur suatu perusahaan sedang melakukan pertemuan disebuah restoran
dan mereka menempati meja lingkaran yang tidak jauh dari pintu masuk. Maka ada
berapa cara untuk menyusun kursi para direktur tersebut?
7
3. Tentukan banyaknya permutasi siklik dari 4 unsur!
4. Ada berapa cara jika 8 gelas warna yang mengitari meja bundar, dapat menempati
kedelapan tempat dengan urutan yang berlainan?
5. Dengan berapa cara potongan 6 kue yang berbeda dapat disusun melingkar diatas
sebuah meja?
1.2.2 Permutasi Siklik (PS*)
Jika PS* (n,k) menyatakan banyak permutasi-k siklik dari n objek tanpa
memperhatikan arah putaran, maka : ππ β (π, π) =ππ(π,π)
2=
π!
2π(πβπ)!
Jika arah putaran tidak dibedakan, artinya memutar searah ataupun berlawanan arah
dengan arah putara jarum jam tidak dibedakan, maka permutasi siklik (12345)
ekuivalen dengan permutasi siklik (15432), ditulis permutasi siklik (12345), seperti
terlihat pada diagram berikut :
CONTOH :
1. Terdapat 4 orang, ada berapa susunan duduk. Jika, arah putaran tidak dibedakan ?
Penyelesaian :
4!
2(4)(4β4)!=
4Γ3Γ2Γ1
2Γ4= 3
SOAL LATIHAN 1.2.2
1. Empat orang siswa masuk perpustakaan sekolah. Mereka membaca di meja
bundar. Berapa cara agar keempat siswa dapat duduk melingkar dengan urutan
yang sama ?
2. Berapa banyaknya permutasi dari cara duduk dapat terjadi jika 8 orang disediakan
4 kursi pada meja bundar dengan arah tempat duduk tidak dibedakan ?
1
5 2
4 3
12345
1
5 2
4 3
15432
8
3. Dari 50 manik-manik berlabel 1, 2, 3, 4, β¦20 akan dibuat gelang yang terdiri dari
10 manik-manik berbeda. Maka banyaknya gelang yang mungkin terbentuk adalah
β¦
4. Sekelompok mahasiswa yang terdiri dari 10 orang akan mengadakan rapat dan
duduk mengelilingi sebuah meja, ada berapa carakah kelima mahasiswa tersebut
dapat diatur jika arah putaran tidak dibedakan .
5. Jika kita mempunyai 75 permata , berlebel 1,2,3,4, β¦ 30 dan ingin digunakan 25
permata untuk membuat kalung, maka ada berapa kemungkinan gelang yang dapat
dibuat ?
1.3 Kombinasi
Istilah kombinasi dalam matematika yaitu kombinatorik yang berarti himpunan
objek yang tidak mementingkan urutan. Kombinasi berbeda dengan permutasi yang
mementingkan urutan. Sehingga kombinasi r objek yang dipilih dari n objek adalah
susunan r objek tanpa memperhatikan urutan atau posisi.
Kombinasi biasa dirumuskan dengan: Crn =
n!
r!(nβr)!
Contoh :
1. Dari 40 nomor rekening akan diundi untuk memenangkan 3 hadiah yang sama.
Berapa banyaknya susunan pemenang yang mungkin terbentuk ?
Penyelesaian :
C340 =
40!
3!(40β3)!=
40!
3!37!=
40 . 39 . 38 . 37!
3!37!=
40 . 39 . 38
3 . 2 . 1= 9880
2. Saat akan menjamu Bayern Munchen di Allianz arena, Antonio Conte (Pelatih
Juventus) punya 20 pemain yang akan dipilih 11 diantaranya untuk jadi starter.
Berapa banyak cara pemilihan starter tim juventus? (tidak memperhatikan posisi
pemain).
Penyelesaian :
9
C1120 =
20!
11!(20β11)!=
20!
11!9!=
20 . 19 . 18 . 17 . 16 . 15 . 14 . 13 . 12 . 11!
11!9!
=20 . 19 . 18 . 17 . 16 . 15 . 14 . 13 . 12
9 . 8 . 7 . 6 . 5 . 4 . 3 . 2 . 1= 167.960
3. Banyaknya segitiga yang dapat dibuat dari 7 titik tanpa ada tiga titik yang terletak
segaris adalah ?
Penyelesaian :
Membuat segitiga dengan memilih 3 titik dari 7 titik yang tersedia adalah masalah
kombinasi C(7, 3). Jadi, banyaknya segitiga C(7,3) 7!
3!4!=
7. 6 . 5
3 . 2 . 1= 35
SOAL LATIHAN 1.3
1. Tentukan kombinasi 5 dari 8 huruf yang berbeda missalnya ABCDEFGH ?
2. Bayu membawa 16 pemain saat Persita melawan Persija di GBK Stadium. 11
orang diantaranya akan dipilih untuk bermain pada babak pertama. jika kita tidak
memperhatikan posisi pemain, berapakah banyaknya cara yang dapat diambil oleh
pelatih untuk memilih pemain ?
3. Siswa di minta mengerjakan 9 dari 10 soal ulangan, tetapi soal 1-5 harus di
kerjakan. Banyaknya pilihan yang dapat diambil murid adalah ?
4. Dalam suatu pertemuan terdapat 10 orang yang belum saling kenal. Agar mereka
saling kenal maka mereka saling berjabat tangan. Berapa banyaknya jabat tangan
yang terjadi ?
5. Sebuah perusahaan membutuhkan karyawan yg terdiri dari 5 putra dan 3 putri.
Jika terdapat 15 pelamar, 9 diantaranya putra. Tentukan banyaknya cara
menyeleksi karyawan!
6. Sebuah kotak berisikan 5 bola merah dan 10 bola putih. Ada berapa cara
mengambil 6 bola sedemikian hingga dari bola-bola yang terambil tersebut
terdapat :
a. Tepat 2 bola merah
b. Paling banyak 2 bola merah
7. Sebuah kantong berisi 6 kelereng putih dan 4 kelereng merah.Dari kantong itu
diambil 3 kelereng sekaligus secara acak.Ada berapa cara pengambilan,jika
kelereng yang diambil adalah:
10
a. 2 kelereng berwarna putih dan 1 kelereng berwarna merah?
b. Ketiganya bebas warnanya?
8. Dalam sebuah ruangan terdapat 15 orang. Jika mereka saling bersalaman maka
berapa banyak salaman yang akan terjadi?
9. Terdapat 5 mawar merah , 10 mawar putih ditoko bunga. Dipilih 4 mawar secara
acak dari toko. Berapa banyak kemungkinan dari :
a. Tepat 2 mawar merah
b. Paling sedikit 3 mawar putih
10. Seorang penjahit akan membeli 3 benang hitam dan 2 benang biru dari seorang
pedagang yang memiliki 6 benang hitam dan 4 benang biru. Dengan berapa cara
penjahit tersebut dapat memilih benang-benang yang di inginkannya?
1.3.1 Kombinasi dengan Pengulangan
Kombinasi dengan pengulangan berukuran r dari n obyek adalah seleksi (pengambilan)
berukuran r dari kumpulan beranggota n obyek dengan urutan tidak diperhatikan dan
pengulangan (pengembalian) dibolehkan.
Teorema : Banyaknya kombinasi dengan pengulangan berukuran r dari n obyek
adalah (π+πβ1)!
π!(πβ1)!= (
π + π β 1π
) = (π + π β 1
π β 1)
Untuk memperoleh dari mana bilangan dalam teorema tersebut diperoleh,
berikut ini diberikan contoh sebagai ilustrasi untuk menuju ke suatu generalisasi.
CONTOH :
1. Untuk memenuhi syarat kelulusan, 7 orang mahasiwa yang terancam DO (drop out)
diwajibkan mengambil 1 mata kuliah pilihan yang dipilih dari 4 mata kuliah pilihan
yang ditawarkan: Kriptologi, Teori Pengkodean, Matematika Finansial, dan
Optimisasi Kombinatorial. Ada berapa cara pemilihan 4 mata kuliah oleh ketujuh
mahasiswa yang bersangkutan?
Penyelesaian :
Misalkan K, T, M, dan O menyatakan Kriptologi, Teori Pengkodean, Matematika
Finansial, dan Optimisasi Kombinatorial. Sebagai gambaran, suatu contoh cara
11
pemilihan yang mungkin adalah K dipilih oleh 2 mahasiswa, T oleh 2 mahasiswa,
M oleh 2 mahasiswa, dan O oleh 1 mahasiswa, kemudian dinotasikan dengan
K,K,T,T,M,M,O dan ditulis sebagai xx|xx|xx|x.
Agar lebih jelas beberapa cara pemilihan yang mungkin lainnya diberikan dalam tabel berikut
ini.
Cara pemilihan yang mungkin Ditulis sebagai
K,K,K,K,T,M,O xxxx|x|x|x
K,K,K,K,O,O,O xxxx|||xxx
T,T,M,M,M,M,O |xx|xxxx|x
K,T,T,T,T,T,T x|xxxxxx||
O,O,O,O,O,O,O |||xxxxxxx
K,K,K,T,M,O,O xxx|x|x|xx
M,M,M,M,M,M,M ||xxxxxxx|
Beberapa contoh dalam tabel di atas mengarahkan kita pada suatu kesimpulan bahwa
masalah menentukan jumlah semua cara pemilihan yang mungkin dapat dibawa ke masalah
mencari banyaknya permutasi berukuran 10 dengan 2 jenis, yaitu 7 obyek berjenis "x"dan
tiga obyek berjenis "|". Dengan demikian ada 10!
3!7!= (
107
) cara ketujuh mahasiswa tersebut
memilih 4 mata kuliah yang ditawarkan.
2. Ada berapa cara apabila 13 kelereng yang identik didistribusikan ke dalam 5 lubang yang
berbeda?
Penyelesaian :
Dengan argumen yang sama dengan jawaban Contoh 1 diperoleh jawaban
17!
4! 3!= (
1713
)
3. Tentukan banyaknya semua penyelesaian intejer dari persamaan
x1 + x2 + x3 + x4 + x5 + x6 = 20 ; dimana xi β₯ 0 untuk setiap 1 β€ i β€ 6.
Penyelesaian :
Dengan argumen yang sama dengan jawaban Contoh 1 diperoleh jawaban
12
25!
5! 20!= (
2520
)
SOAL LATIHAN 1.3.1
1. Tulislah semua kombinasi-3 dari {a, b, c, d} sedemikian sehingga pengulangan
diperbolehkan.
2. Jika n adalah bilangan bulat positif, berapa banyaknya (i, j, k) yang mungkin
apabila 1 β€ i β€j β€ k β€ n?
Perhatikan kisi-kisi berukuran 3 x 4 berikut:
Catatan
Dari ketiga contoh terakhir di atas, kita sampai pada kesimpulan bahwa ketiga pernyataan berikut
adalah ekuivalen:
1. Banyaknya pemilihan berukuran r dari koleksi beranggota n obyek dengan urutan tidak diperhatikan
dan pengulang dibolehkan.
2. Banyaknya solusi intejer dari persamaan x1 + x2 + β¦ + xn = r, dimana xi β₯ 0 untuk setiap 1 β€ i β€ n.
3. Banyaknya cara pendistribusian apabila r obyek yang identik didistribusikan ke dalam n wadah
yang berbeda.
13
Jika kita ingin melintas dari titik P (pojok kiri bawah) ke titik Q (pojok kanan
atas) dengan syarat hanya boleh bergerak kekanan (K) dan keatas (A). salah satu
lintasan yang mungkin diperlihatkan oleh lintasan-1. Lintasan ini dapat dinyatakan
dengan barisan KKAKKAA (2 langkah kekanan, dilanjutkan 1 langkah keatas,
dilanjutkan 2 langkah ke kanan dan 2 langkah keatas).
Lintasan yang lain Lintasan-2 yang dapat dinyatakan dengan barisan
AAKKKAK. Perhatikan bahwa dalam setiap barisan terdapat empat K dan tiga A. Dai
setiap barisan yang demikian, diperoleh sebuah lintasan dari P dan Q. Jadi, banyak
lintasan yang mungkin sama dengan banyaknya binair 7 huruf yang memuat empat
huruf K dan tiga huruf A.
Barisan yang dimaksud sama dengan banyaknya cara memilih 4 posisi dari 7
posisi yang ada untuk meletakkan huruf K, yaitu C (7, 4) = C (4+3, 4) = 35. Sama saja
dengan banyak cara memilih 3 posisi dari 7 posisi untuk meletakkan huruf A, yaitu C
(7, 3) = C (4+3, 3) = 35. Dengan demikian terdapat 35 lintasan yang mungkin dari
Titik P ke titik Q pada kisi-kisi tersebut.
Theorema : C* (n, k) = C (n+k-1, k) = C (n+k-1, n-1)
CONTOH :
1. S = {a,b,c}
Penyelesaian :
1. {π, π, π, π, π}|{0,0,0,1,0,1,0}
2. {π, π, π, π, π}|{0,0,1,0,0,1,0}
3. {π, π, π, π, π}|{0,1,0,0,0,1,0} ...
πππ
C*(3, 5) = C (7, 5) = C (7, 2)
C* (n, k) = C (n+k-1, k) = C (n+k-1, n-1)
4.
B
A
3X2
14
Penyelesaian :
C (n+m, n) / C (n+m, m)
C (5, 2) = 5!
3! 2!=
5.4
2=
20
2= 10 Cara
1. KKAAA 6. AAKKA
2. KAAAK 7. AAKAK
3. AAAKK 8. AKAKA
4. AKKAA 9. KAAKA
5. AKAAK 10. KAKAA
RUMUS: Lintasan Cantik pada kisi-kisi n x n:
πΆ (π + π, π) β πΆ (2π, π β 1)
πΆ (2π, π) β πΆ (2π, π β 1)
(2π)!
π! π!=
(2π)!
(π β 1)! (π + 1)!
(2π)!
π! π!=
(2π)!
π!π (π + 1)π!
(2π)!
π! π!=
(2π)! π
π! π! (π + 1)
(2π)!
π! π!= (1 β
π
π + 1)
Lintasan Cantik (n x n ) adalah Bilangan Catalan
LINTASAN CANTIK ADALAH SUATU LINTASAN YANG MENYENTUH DAN
DIBAWAH DIAGONAL UTAMA
πππππ ππππππππ ππππππ (π§π±π¦) β π(π§ + π¦, π§ ) ππππ π(π§ + π¦, π§)
15
B
A
A
B
B
A
B
B
Soal Latihan :
1. Berapa banyak lintasan cantik dari A ke B melalui F?
2. Berapakah banyak lintasan cantik dari A ke B melalui C?
Lintasan Tak Cantik
Yang punya lintasan tak cantik hanyalah jika dan hanya jika jumlah baris dan
kolom pada sebuah kotak sama.
ππππ‘ππ ππ π‘ππ ππππ‘ππ = πΆ(2π,πβ1)/πΆ(2π,π+1)
Contoh :
A
1. Berapa banyak lintasan tak cantik dari A ke B
Penyelesaian :
Karena A ke B mempunyai jumlah kolom dan baris sama yaitu 4 maka,
=(2.4)!
4!4!. [1 β
4
5] =
8!
4!4!. [
1
5] =
8.7.6.5
4.3.2.1. [
1
5] = 14 lintasan
Maka lintasan tak cantik dari A ke B adalah sebanyak 14 lintasan
E
F
D C
C
16
D
C
1. Berapa banyak lintasan tak cantik dari C ke D !
Penyelesaian :
Karena lintasan tersebut mempunyai kolom dan baris berbeda maka dari C ke
D tidak mempunyai Lintasan Tak Cantik.
1.4 Koefisien Binominal dan Segitiga Pascal
Pada bagian ini akan diperlihatkan bahwa C(n,k) merupakan koefisien
binomial. Untuk keperluan tersebut, diperlukan teorema berikut, dikenal dengan
formula pascal. Perhatikan bahwa simbol C(n,k) sering di tulis seperti (ππ
).
Teorema 1.4 (Teorema Binomial) Jika x dan y adalah variabel dan n adalah
intejer positif, maka
(π₯ + π¦)π = β (π
π) π₯ππ¦πβπ
π
π=0
Bukti :
(x + y)n dapat di tulis sebagai perkalian dengan n faktor (x + y): (x + y) (x + y) (x
+ y) (x + y) . . . (x + y). Ekspansi dari perkalian tersebut menghasilkan jumlahan
dengan suku suku bertipe xi yn-i untuk i = 1,2,3...n. banyaknya suku xi yn-i dari
ekspansi tersebut merupakan koefisien dari xi yn-i, yaitu (ππ) Bilangan ini diperoleh
dari banyaknya cara memilih i faktor dari n faktor. Akibat dari teorema tersebut
adalah untuk seriap intejer π β₯ 1
1. β (ππ) = 2ππ
π=0
2. β (β1)π(ππ) = 0π
π=0
Catatan : substirusikan teorema tersebut dengan:
1. x = 1 dan y = 1
2. x = β1 dan y = 1
Teorema 1.5 untuk sembarang intejer n, r dengan π β₯ π β₯ 1
(π + 1
π) = (
π
π) + (
π
π β 1)
5.
17
Bukti:
Walaupun teorema ini bisa dibuktikan secara aljabar, yaitu dengan menggunakan
defnisi (ππ) =
π!
π!(πβπ)! namun disini pembuktian akan di lakukan secara
kombinatorik.
Misalkan :
π΄ = {π₯, π1, π2 β¦ ππ}
Banyaknya subhimpunan berkardinal r dari A adalah (π+1π
) Setiap subhimpunan
tersebut hanya ada dua kemungkinan: memuat x atau tidak memuat x. Banyaknya
subhimpunan yang memuat x adalah ( ππβ1
), sedangkan yang tidak memuat x adalah
(ππ). Dengan aturan jumlah, kita dapatkan rumusan yang dimaksud.
CONTOH :
1. Tentukan koefisien dari x5y2 di dalam ekspansi (2x β 3y)7
Penyelesaian :
(75) 25(β3)2
SOAL LATIHAN 1.4
1. Tentukanlah koefisien dari x3y2 dalam ekspansi
a. (x + y)12
b. (x + 2y)12
c. (2x β 3y)12
2. Tentukan koefisien dari x2y7 dalam ekspansi
a. (2x β 2y)4
b. (4x β y )2
1.5 Koefisien Multinomial
Teorema binomial memberi formula untuk (π₯ + π¦)π dengan n merupakan
bilangan bulat positif. Hal ini dapat diperluas ke multinomial (π₯1 + π₯2 + β― + π₯π)π.
Berikut akan ditunjukkan bahwa koefisien suku π₯1π1, π₯2
π2, β¦ , π₯πππ adalah
π!
π1!π2!β¦ππ!
18
Dengan π1, π2, β¦ , ππ adalah bilangan-bilangan bulat non negatif dan π1 +
π2 + β― + ππ = π. Bilangan-bilangan ini disebut multinomial, dan sering
disimbolkan dengan (π
π1 π2 β¦ ππ).
Teorema 1.7 Misalkan n sebuah bilangan positif, maka untuk semua
π₯1, π₯2, β¦ , π₯π berlaku (π₯1 + π₯2 + β― + π₯π)π = β (π
π1, π2, β¦ , ππ) π₯1
π1, π₯2π2, β¦ , π₯π
ππ
, dengan sigma mencakup semua kemungkinan bilangan bulat non negatif
π1, π2, β¦ , ππ yang memenuhi π1 + π2 + β― + ππ = π.
Bukti:
Tulis (π₯1 + π₯2 + β― + π₯π)π sebagai perkalian dari n buah faktor masing-masing
faktor adalah (π₯1 + π₯2 + β― + π₯π). Ekspansi perkalian tersebut ke dalam suku-suku
sehingga tidak ada tanda βkurungβ yang tersisa. Karena dari setiap faktor kita dapat
memilih π₯1, π₯2, β¦ , π₯π, maka banyak sukuyang terbentuk adalah kn dan setiap suku
dapat dijajar dalam bentuk π₯1π1, π₯2
π2, β¦ , π₯πππ dengan π1, π2, β¦ , ππ bilangan bulat
non negatif yang memenuhi π1 + π2 + β― + ππ = π.
Suku-suku berbentuk π₯1π1, π₯2
π2, β¦ , π₯πππ dapat diperoleh dengan: memilih π₯1
sebanyak π1 dari n faktor, memilih π₯2 sebanyak π2 dari π β π1 faktor sisanya,
memilih π₯3 sebanyak π3 dari π β π1 β π2 faktor sisanya,..., memilih π₯π sebanyak
ππ dari π β π1 β π2 β β― β ππβ1 faktor tersisa. Berdasarkan prinsip perkalian,
banyaknya suku berbentuk adalah
(ππ1
) (π β π1
π2) (
π β π1 β π2
π3) β¦ (
π β π1 β π2 β β― β ππβ1
ππ)
=π!
π1!(πβπ1)!Γ
(πβπ1)!
π2!(πβπ1βπ2)!Γ
(πβπ1βπ2)!
π3!(πβπ1βπ2βπ3)!Γ β¦ Γ
(πβπ1βπ2ββ―βππβ1)!
ππ!0!
=π!
π1!π2!β¦ππ!= (
ππ1 π2 β¦ ππ
) Dengan demikian teorema terbukti.
CONTOH :
1. Jika (π₯1 + π₯2 + π₯3 + π₯4)5 dijabarkan, berapakah koefisien dari: (a) π₯13π₯2π₯4? :
(b) π₯1π₯2π₯3π₯42
Penyelesaian:
19
a. (5
3 1 0 1) =
5!
3!1!0!1!= 20
b. (5
1 1 1 2) =
5!
1!1!1!2!= 60
2. Berapakah koefisien dari π₯1π₯23π₯3π₯4
2 dalam (π₯1 β 5π₯2 + π₯3 β 2π₯4)7?
Penyelesaian:
Koefisien π₯1π₯23π₯3π₯4
2 adalah (7
1 3 1 2) (β5)3(β2)2 = β210000
3. Ada berapa cara menempatkan 12 orang mahasiswa ke dalam dua kamar
sedemikian sehingga kamar pertama berisi 4 mahasiswa dan kamar kedua
berisi 8 mahasiswa?
Penyelesaian:
Terdapat C(12:4) cara memilih mahasiswa dari 12 mahasiswa untuk
ditempatkan dalam kamar pertama, dan terdapat C(12-4:8) cara memilih 8
mahasiswa dari 12-4 = 8 mahasiswa yang tersisa. Jadi banyaknya cara yang
dimaksud adalah
C(12;4) Γ C(8;8) = 12!
4!8!Γ
8!
8!0!=
12!
4!8!= 495 cara
4. Ada berapa bilangan 5 angka memuat dua angka β3β, satu angka β2β, dan dua
angka β1β?
Penyelesaian:
Banyak bilangan yang dimaksud adalah (5
2 1 2) =
5!
2!1!2!= 30.
5. Ada berapa kata sandi dengan panjang 9 yang dibentuk dari huruf-huruf A, B,
dan C sedemikian sehingga setiap huruf muncul tiga kali dalam setia kata
sandi?
Penyelesaian:
Banyaknya kata sandi yang dapat terbentuk adalah (9
3 3 3) =
9!
3!3!3!= 1680.
SOAL LATIHAN 1.5
1. Jika (π₯1 + π₯2 + π₯3)4 dijabarkan, berapakah koefisien dari π₯12π₯2π₯3
2 adalah...
2. Berapakah koefisien dari π₯12π₯2π₯3
3π₯4 dalam (2π₯1 + π₯2 β 3π₯3 + π₯4)6?
3. Ada berapa cara menyusun kata MATEMATIKA?
20
4. Panitia membeli 14 macam snack, ada berapa cara menempatkan snack tersebut
ke dalam dua kantong plastik sedemikian sehingga kantong pertama berisi 6
snack dan kantong kedua berisi 8 snack?
5. Ada berapa kata sandi yang terbentuk dari 6 huruf memuat dua huruf βLβ, dua
huruf βRβ, dan dua huruf βAβ?
1.6 The Pigeonhole Principle (Prinsip Sarang Merpati)
Pigeonhole Principle atau Prinsip Rumah Merpati pertama kali dinyatakan
oleh ahli matematika dari Jerman yang bernama Johann Peter Gustav Lejeune
Dirichlet pada tahun 1834, sehingga prinsip ini juga dikenal dengan istilah Prinsip
Laci Dirichlet (Dirichlet drawer principle).
a. Prinsip Pigeonhole Bentuk Pertama
Bukti :
Misal, jika n merpati ditempatkan pada m rumah merpati, dimana n > m, maka
terdapat rumah merpati yang memuat paling sedikit dua merpati. Untuk
membuktikan pernyataan Prinsip Pigeonhole ini, kita gunakan kontradiksi.
Misalkan kesimpulan dari pernyataan tersebut salah, sehingga setiap rumah merpati
memuat paling banyak satu merpati. Karena ada m rumah merpati, maka paling
banyak m merpati yang bisa dimuat. Padahal ada n merpati yang tersedia dan n >
m, sehingga kita dapatkan sebuah kontradiksi.
CONTOH :
1. Jika terdapat 11 pemain dalam sebuah tim sepakbola yang menang dengan
angka 12-0.
Penyelesaian :
Maka haruslah terdapat paling sedikit satu pemain dalam tim yang membuat
gol paling sedikit dua kali.
2. Jika anda menghadiri 6 kuliah dalam selang waktu Senin sampai Jumat.
Jika n merpati ditempatkan pada m rumah merpati, dimana n > m , maka terdapat
rumah merpati yang memuat paling sedikit dua merpati.
21
Penyelesaian :
Maka haruslah terdapat paling sedikit satu hari ketika anda menghadiri paling
sedikit dua kelas.
3. Di antara sedkitinya 8 orang, pasti terdapat dua orang yang lahir pada hari yang
sama. Penyelesaian :
Pada contoh ini orang kita anggap sebagai objek dan banyak hari kita anggap
sebagai kotak. Karena terdapat sedikitnya 8 orang dan hanya ada 7 hari, maka
prinsip sarang merpati menjamin bahwa terdapat sedikitnya dua orang yang
lahir pada hari yang sama.
b. Prinsip Pigeonhole Bentuk Kedua
Bukti :
Untuk membuktikan Prinsip Pigeonhole Bentuk Kedua ini kita bisa
mengasumsikan X sebagai himpunan merpati dan Y sebagai himpunan rumah
merpati. Selanjutkan kita memasangkan merpati x ke rumah merpati f(x). Karena
jumlah merpati lebih banyak dari rumahnya, maka terdapat paling sedikit dua
merpati, x1, x2 β X yang dipasangkan ke rumah merpati yang sama, yaitu f(x1) =
f(x2) untuk beberapa x1, x2 β X, dimana x1 β x2.
CONTOH :
1. Dalam membuat kode matakuliah untuk matakuliah-matakuliah bidang studi
informatika adalah dengan cara menambahkan tiga angka pada huruf TIK.
Terdapat 51 matakuliah yang harus diberi kode dan tiga angka yang harus
ditambahkan pada huruf TIK harus berkisar antara 101 sampai dengan 200.
Tunjukkan bahwa terdapat paling sedikit dua matakuliah yang diberi kode
dengan angka berurutan.
Penyelesaian :
Misalkan angka-angka yang dipilih adalah
a1, a2, β¦, a51
Jika angka-angka diatas digunakan bersama-sama dengan
Jika f merupakan sebuah fungsi dari suatu himpunan terhingga X ke suatu himpunan
terhingga Y dan |X| > |Y |, maka f(x1) = f(x2) untuk beberapa x1, x2 β X, dimana x1 β x2.
22
a1 + 1, a2 + 1, β¦, a51 + 1, maka terdapat 102 nomor yang merentang antara 101
sampai dengan 201. Karena ada 100 nomor yang disediakan (yaitu 101 sampai
dengan 200) dan ada 102 nomor yang akan digunakan, maka menurut Prinsip
Pigeonhole Bentuk Kedua terdapat paling sedikit dua nomor yang sama. Nomor
a1, a2, β¦, a51 dan a1 + 1, a2 + 1, β¦, a51 semuanya berbeda. Sehingga kita
mempunyai
ai = aj + 1. Dengan demikian kode ai berurutan dengan kode aj .
1.6.1 The Generalized Pigeonhole Principle Theorem (Generalisasi Prinsip Sarang
Merpati)
Jumlah dari objek melebihi dari jumlah kotak yang tersedia.
Jika f merupakan sebuah fungsi dari suatu himpunan terhingga X ke suatu
himpunan terhingga Y , dimana |X| = n, |Y | = m dan βn
mβ= k, maka terdapat paling
sedikit k anggota x1, x2, ..., xk β X sedemikian hingga f(x1) = f(x2) = ... = f(xk).
Bukti :
Untuk membuktikan pernyataan Prinsip Pigeonhole bentuk ketiga ini, kita gunakan
kontradiksi. Misalkan Y = {y1, y2, ..., ym}. Andaikan kesimpulan dari pernyataan
tersebut salah, maka terdapat paling banyak k β 1 anggota x β X dengan f(x) = y1;
terdapat paling banyak kβ1 anggota x β X dengan f(x) = y2, dan seterusnya sampai
dengan terdapat paling banyak k β 1 anggota x β X dengan f(x) = ym. Sehingga
terdapat paling banyak m(k β 1) anggota X. Namun demikian m(k β 1) < m . π
π = n
yang merupakan sebuah kontradiksi. Oleh karena itu, terdapat paling sedikit k
anggota x1, x2, ..., xk β X sedemikian hingga f(x1) = f(x2) = ... = f(xk).
CONTOH :
1. Ada berapa cara membagikan 10 buku matematika yang identik kepada tiga
orang mahasiswa ?
Penyelesaian :
Jika N obyek ditempatkan ke dalam k kotak, maka terdapat paling sedikit satu kotak
yang memuat sedikitnya [N/k] obyek.
23
N = 10, k = 3 . βπ
πβ = β
10
3β = β3,333β= 4 (menggunakan pembulatan ke atas).
Jadi, paling banyak seorang siswa akan mendapatkan 4 buah buku.
SOAL LATIHAN 1.6.1
1. Misalkan terdapat banyak bola merah, bola putih, dan bola biru di dalam
sebuah kotak. Berapa paling sedikit jumlah bola yang diambil dari kotak (tanpa
melihat ke dalam kotak) untuk menjamin bahwa sepasang bola yang berwarna
sama terambi.
2. Misalkan sebuah turnamen basket diikuti oleh n buah tim yang dalam hal ini
setiap tim bertanding dengan setiap tim lainnya dan setiap tim menang paling
sedikit satu kali. Tunjukkan bahwa paling sedikit ada 2 tim yang mempunyai
jumlah kemenangan yang sama.
3. Seperti kasus nomor A. Sekarang, di laci ada 12 kaos kaki hitam, 13 kaos kaki
putih, 20 kaos kaki biru, 5 kaos kaki merah, 1 kaos kaki hijau, dan 1 kaos kaki
kuning. Berapa banyak kaos kaki minimal yang harus diambil agar setidaknya:
a. terdapat 2 kaos kaki yang memiliki warna yang sama
b. terdapat 2 kaos kaki yang memiliki warna yang berbeda.
4. Sebanyak 51 bilangan bulat diambil dari bilangan-bilangan bulat 1, 2, 3, 4, β¦.,
100. Tunjukkan bahwa diantara bilangan-bilangan yang terambil, terdapat dua
bilangan sedemikian hingga yang satu pembagi yang lain.
5. Misalkan A = {1, 2, 3, 4, 5, 6, 7, 8}. Jika lima bilangan bulat diambil dari A,
apakah paling sedikit ada sepasang bilangan bulat yang jumlahnya 9?
6. Dalam matakuliah Matematika Diskrit diberikan tugas kelompok yang akan
dibagi menjadi enam kelompok. Jika terdapat 62 mahasiswa yang menempuh
mata kuliah tersebut, tunjukkan bahwa terdapat paling sedikit ada 11
mahasiswa yang menjadi anggota suatu kelompok yang sama!
7. Jika terdapat 20 sarang merpati dan 41 ekor merpati, ada berapa merpati yang
terdapat pada satu buah sarang?
8. Di antara 50 orang mahasiswa, ada berapa mahasiswa yang lahir pada bulan
yang sama?