Soal-soal Latihan: 1.
Misalkan kita akan menyusun kata-kata yang dibentuk dari huruf-huruf dalam kata SIMALAKAMA, jika a. huruf S muncul setelah huruf K (misalnya, ALAMAKSIM). b. huruf A muncul berdekatan. c. tidak memuat pola MASAM atau MAKAM. d. tidak memuat pola MALAS dan SIAL. e. memuat pola KAMIS atau KALAM. f. memuat pola KAMAL tapi tak memuat pola MALAKA.
2.
Dalam kita dapat memilih pengiriman 100 chip komputer, terdapat 8 yang rusak. Ada berapa cara kita dapat memilih, jika kita dapat memilih 4 buah chip yang a. semuanya tidak rusak? b. terdiri atas 2 chip yang rusak dan 2 chip yang baik? c. terdiri atas tepat 2 chip yang rusak?
3.
Misalkan C(i,j) adalah banyaknya himpunan bagian dengan j anggota dari himpunan dengan i anggota. Tunjukkan bahwa C(n,k) = C(n, n-k).
17. Buktikan bahwa berlaku a. C (n, k )
C (n, k 1) jika k
b. C (n, k )
C (n, n k ).
n 1 . 2
n
c.
2n .
C ( n, k ) k 0 n
d.
C (n, k ) 2
C (2n, n) .
k 0
n
e.
C ( n, k )
2n
k 0
18. Misalkan n adalah bilangan genap. Buktikan bahwa n
n
2
C (2n, k )
2
n 1
k 0
2
C (n,2k 1) k 1
19. Dalam berapa cara 20 buku yang berbeda satu sama lain, dapat dibagikan kepada 3 mahasiswa, jika mahasiswa pertama mendapat 8 buku, yang ke-2 mendapat 7 buku, dan yang ke-3 mendapat 5 buku?
20. Dalam sebuah keranjang terdapat beberapa buah bola, masing-masing berwarna merah, biru, dan hijau. Ada berapa cara 10 bola dapat dipilih, a. jika paling sedikit terdapat 1 bola berwarna merah harus terpilih? b. Jika paling sedikit 1 bola merah, paling sedikit 2 bola biru, dan paling sedikit 3 bola hijau mesti terpilih? c. Jika paling banyak 1 bola merah terpilih? d. Jika tepat 1 bola merah dan paling sedikit 1 bola hijau mesti terpilih? 27. Misalkan dalam sebuah grup yang terdiri atas 6 orang, masing-masing pasangan individu terdiri atas 2 teman atau 2 musuh. Perlihatkan bahwa terdapat 3 orang yang saling merupakan teman satu sama lain atau 3 orang yang saling merupakan musuh satu sama lain. 28. Susunlah banyaknya cara 8 buah buku yang berbeda dibagikan kepada 3 orang siswa, jika siswa pertama memperoleh 1 buah buku, siswa ke-dua memperoleh 2 buku, dan siswa ke-tiga memperoleh 2 buku. 29. Ada berapa banyak bilangan bulat antara 1 dan 1.000.000 yang jumlah bilangan dari digit-digitnya sama dengan 15? 30. Tentukan banyaknya penyelesaian bilangan bulat bagi persamaan x1
x2
jika a. 0
x1
4, x 2
b. 0
x1
5, 1
0, x3 x2
0.
8, x3
0.
31. Tentukan banyaknya penyelesaian bilangan bulat bagi persamaan y1
y2
y3
y4
16 ,
yang memenuhi 0
x1
5, 0
x2
6, 0
x3
7, 0
y4
32. Tentukan koefisien suku x 4 y 3 z 2 dari perluasan bentuk ( x
8. y
z) 9 .
33. Tentukan ada berapa suku yang terdapat dalam perluasan bentuk ekspresi a. (x+y+z)12. b. (a+b+c+d)8. c. (x+y+z)10 (a+b+c+d)4. 40. Tentukan koefisien untuk x4y4z2 dari (2x+y+z)10. Relasi Berulang 1. Selesaikan relasi berulang berikut ini: a. an =2an-1 + 2an-2, a0 = a1 = 1.
x3
10 ,
b. an =2nan-1 + 1, a0 = 2. 2. Sebuah robot dapat melangkah dengan jarak 1 atau 2 meter. Jika Cn menyatakan banyaknya cara robot melangkah dalam n meter, susunlah relasi berulang untuk Cn. 5. Seorang pebisnis berinvestasi dengan modal sebesar Rp. 20.000.000,- dan mendapat bunga sebesar 12 persen per tahun. Jika An menyatakan banyaknya uang di akhir dari n tahun, tentukan suatu relasi berulang dan syarat awal bagi barisan A0, A1, A2, ... . Tuliskan pula rumus eksplisit bagi An . 8. Misalkan seorang anak memiliki n rupiah dan setiap harinya dia membeli jus jeruk seharga Rp. 8.000,-, jus tomat seharga Rp. 7.000,-, atau jus alpuket seharga Rp. 10.000,-. Jika Hn menyatakan banyaknya cara anak tersebut membelanjakan uangnya, perlihatkan bahwa Hn
9.
Hn
2H n 2 .
1
Diketahui A0 = 0, dan A1 = 1. Tentukan A5 dan A10 jika
1 ( An 3
An
An 2 ) .
1
10. Sebuah barisan Fibonacci dinyatakan dengan f n . Tunjukkan bahwa f n2 2
fn fn
3
0,1,2, .
f n2 1 , n
11. Jika fn menyatakan barisan Fibonacci untuk n=1,2,3, ...
, tunjukkan bahwa
n
fn
C (n 1 k , k ), n 1, 2,
1 k 0
12. Misalkan Pn Pn menyatakan banyaknya partisi dari suatu himpunan yang memiliki n anggota. Tunjukan bahwa barisan P0 , P1 , P2 , memenuhi relasi berulang n
Pn
C (n 1, i ) Pi i 0
13. Misakan A(n,k) menyatakan banyaknya fungsi onto dari himpunan dengan n anggota ke himpunan dengan k anggota. Tunjukkan bahwa A(n,k) memenuhi relasi berulang k 1
A(n, k )
C (k , i ) A(n, i ) .
kn i 1
20. Tentukan penyelesaian eksplisit bagi persoalan Menara Hanoi untuk 3 n 24. Selesaikanlah relasi berulang berikut sesuai dengan syarat awalnya. d. a n
2a n
2
a n 1 , a0
a1
e. a n
3a n
2
2a n 1 , a 0
1, a1
28. Buktikan bahwa
1. 0.
6.
a. a n
2 n adalah penyelesaian eksplisit bagi relasi berulang an
b. a n
2n
an
2a n
1
2a n
1
2n 9 .
2 adalah penyelesaian eksplisit bagi relasi berulang
n 3( 1) n
an
2
an
2
2n 9 .
29. Tentukan penyelesaian eksplisit bagi relasi berulang berikut dengan teknik pendekatan iteratif. a. a n
n a n 1 , a0
b. a n
3 2n a n 1 , a 0
c. a n
2nan 1 , a 0
d. a n
5a n
1
1. 1.
1.
2, a1 1.
Soal-soal Latihan: 1.
Buktikan bahwa dalam tiap kumpulan 6 mata pelajaran pasti ada dua mata pelajaran yang terjadwal pada hari yang sama, jika tak ada pelajaran yang diselenggarakan di hari Sabtu.
3.
Sebuah laci lemari diisi selusin kaus kaki berwarna biru dan selusin kaus kaki berwarna coklat yang bercampur tidak berpasangan. Seorang anak mengambil beberapa kaus kaki tersebut dalam kegelapan malam. a. Berapa kaus kaki harus diambil agar dia yakin bahwa paling sedikit dia memperoleh dua kaus kaki yang berwarna sama? b. Berapa kaus kaki harus dia ambil agar paling sedikit diperoleh dua kaus kaki
9.
Misalkan dari 8 bilangan bulat positif pertama diambil 4 bilangan. Apakah pasti terdapat sepasang bilangan bulat positif yang jumlahnya 9?
10. Perlihatkan bahwa jika 7 bilangan dipilih dari 10 bilangan asli pertama, maka pasti terdapat paling sedikit dua pasang bilangan yang jumlahnya 11. 11. Misalkan 6 bilangan dipilih dari 10 bilangan asli pertama. Apakah pasti terdapat paling sedikit dua pasang bilangan yang jumlahnya 11?
15.
Di sebuah perkuliahan matematika kombinatorik terdapat sembilan mahasiswa. Perlihatkan bahwa di perkuliahan tersebut paling sedikit terdapat paling sedikit lima mahasiswa pria atau paling sedikit lima mahasiswa wanita. Tunjukkan pula bahwa di perkuliahan tersebut terdapat paling sedikit tiga mahasiswa pria atau paling sedikit tujuh mahasiswa wanita.
16. Misalkan bahwa tiap-tiap mahasiswa yang mengontrak mata kuliah persamaan diferensial yang jumlahnya mencapai dua puluh lima orang adalah mahasiswa asal Pulau Jawa, Pulau Sumatra, atau Pulau Kalimantan. Perlihatkan bahwa terdapat paling sedikit sembilan mahasiswa
asal Pulau Jawa, paling sedikit sembilan
mahasiswa asal Pulau Sumatra, atau paling sedikit sembilan mahasiswa asal Pulau Kalimantan. Tunjukkan pula bahwa terdapat paling sedikit tiga mahasiswa asal Pulau Jawa, paling sedikit sembilan belas mahasiswa asal Pulau Sumatra, atau paling sedikit lima mahasiswa asal Pulau Kalimantan. 18. Perlihatkan bahwa di antara 101 peserta seminar yang tinggi badannya semuanya berbeda, terdapat sebelas orang yang dapat diminta berdiri dalam satu barisan dengan tinggi badan dari terkecil ke terbesar atau sebaliknya. 20. Dalam sebuah kelompok yang terdiri atas 10 orang, di antara dua orang dalam kelompok tersebut saling merupakan teman atau saling merupakan musuh. Perlihatkan bahwa pasti terdapat tiga orang dalam kelompok tersebut yang saling merupakan musuh satu sama lain, atau empat orang yang saling merupakan teman satu sama lain, dan tiga orang yang saling merupakan musuh satu sama lain atau empat orang yang satu sama lainnya merupakan teman. 23. Di tepi sebelah kiri sepanjang jalan raya sebuah kota terdapat 23 rumah. Tiap-tiap rumah mempunyai nomor mulai dari 100 hingga 143. Perlihatkan bahwa ada paling sedikit 2 rumah yang mempunyai nomor berurutan.
