CBR - Yusni Utami - Matematika Diskrit - PSPM C 2018 [PDF]

Citation preview

CRITICAL BOOK REPORT “Analisis Pemecahan Masalah Dunia Nyata Berkaitan



Dengan Kaidah Perhitungan”



Disusun Oleh :



Nama



: Yusni Utami



Nim



: 4183311025



Kelas



: Pendidikan Matematika C 2018



Dosen Pengampu



: Dr. Asrin Lubis, M.Pd.



Kelompok



: 5



JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS NEGERI MEDAN 2021



KATA PENGANTAR Puji dan syukur penulis ucapkan kepada Tuhan Yang Maha Esa, karena atas berkat dan Rahmat-Nya lah tugas laporan CBR ini dapat terselesaikan dengan baik dan sesuai dengan jadwal yang telah ditentukan. Penulis berterima kasih kepada dosen pengampu yang sudah memberikan bimbingan dan arahan kepada penulis sehingga tugas CBR Matematika Dskrit dapat diselesaikan sesuai dengan jadwal yang telah ditetapkan. Harapan penulis semoga laporan CBR Matematika Dskrit ini membantu menambah pengetahuan dan pengalaman bagi para pembaca, sehingga penulis dapat memperbaiki tugas ini sehingga kedepannya dapat lebih baik. Penulis akui masih banyak kekurangan karena pengalaman yang dimiliki sangat kurang. Oleh kerena itu penulis harapkan kepada para pembaca untuk memberikan masukan-masukan yang bersifat membangun untuk kesempurnaan laporan ini.



Medan, 2 April 2021



Yusni Utami



i



DAFTAR ISI KATA PENGANTAR .......................................................................................................................i DAFTAR ISI ..................................................................................................................................... ii BAB I PENGANTAR ...................................................................................................................... 1 1.1



Latar Belakang ................................................................................................................... 1



1.2



Rumusan Masalah ............................................................................................................... 1



1.3



Tujuan ................................................................................................................................ 1



BAB II RINGKASAN ISI BUKU ................................................................................................... 2 BAB III KEUNGGULAN BUKU .................................................................................................. 13 3.1



Kelengkapan sub topik (subbab/sub subbab) .................................................................. 13



3.2



Keterkaitan topik utama (bab/subbab) dengan subtopic (subbab/subsubbab) ................ 13



3.3



Aspek kelayakan isi ......................................................................................................... 13



3.4



Aspek kelayakan bahasa .................................................................................................. 13



3.5



Aspek kelayakan penyajian ............................................................................................. 14



BAB IV KELEMAHAN BUKU .................................................................................................... 15 4.1



Kelengkapan sub topik (subbab/sub subbab) .................................................................. 15



4.2



Keterkaitan topik utama (bab/subbab) dengan subtopic (subbab/subsubbab) ................ 15



4.3



Aspek kelayakan isi ......................................................................................................... 15



4.4



Aspek kelayakan bahasa .................................................................................................. 15



4.5



Aspek kelayakan penyajian ............................................................................................. 15



BAB V IMPLIKASI ...................................................................................................................... 16 5.1



Implikasi terhadap Teori/Konsep ................................................................................... 16



5.2



Program Pembangunan di Indonesia .............................................................................. 16



5.3



Analisis Mahasiswa ........................................................................................................ 16



BAB VI KESIMPULAN DAN SARAN ....................................................................................... 17 DAFTAR PUSTAKA ...................................................................................................................... 18



ii



BAB I PENGANTAR 1.1 Latar Belakang Matematika merupakan salah satu disiplin ilmu yang termasuk kedalam salah satu pelajaran yang harus di kuasai oleh pelajar bahkan menjadi kewajiban yang mutlak yang harus di ajarkan kepada peserta didik mulai dari bangku pendidikan dasar hingga perguruan tinggi. Dalam perguruan tinggi khususnya jurusan matematika, disiplin ini memiliki berbagai cabang yang sangat banyak dan seiring dengan semakin tingginya jenjang pendidikan yang di ambil maka semakin kompleks pula pembahasan tentang matematika. Mata kuliah Matematika Diskrit sangat lah penting karena mempunyai tujuan untuk mendidik mahasiswa agar memiliki pengetahuan dasar analisis matematika, misalnya tentang bilangan bulat, himpunan, induksi matematika, relasi dll serta mampu bernalar secara logis dan kritis. Mahasiswa memerlukan buku – buku sebagai sumber dan bahan dalam kegiatan belajar mengajar. Buku yang dimiliki juga harus mudah dipahami dari segala aspeknya. Critical Book Report merupakan salah satu instrument yang dapat mendukung keberhasilan dalam proses pembelajaran di bangku perkuliahan. Indikator keberhasilan critical book report untuk mendukung keberhasilan dalam pembelajaran dapat dilihat dari terciptanya kemampuan mahasiswa untuk mengevaluasi penjelasan, interpretasi serta analisis mengenai kelebihan maupun kelemahan dari buku. Dengan kata lain, melalui critical book report mahasiswa diajak untuk menguji pemikiran dari pengarang maupun penulis berdasarkan sudut pandang yang akan dibangun oleh setiap mahasiswa berdasarkan pengetahuan dan pengalaman yang dimiliki. 1.2 Rumusan Masalah Adapun rumusan masalah dari CBR ini adalah : 1. Bagaimana keunggulan dan kelemahan buku yang di kritisi? 2. Bagaimana implikasi terhadap teori/konsep dari buku atau materi yang dikritisi? 3. Bagaimana analisis mahasiwa mengenai buku atau materi yang dikritisi? 1.3 Tujuan Adapun tujuan dari CBR ini adalah : 1. Untuk mengulas suatu buku dengan cara mengkritisi buku tersebut. 2. Untuk mengetahui implikasi terhadap teori/konsep dari buku yang dikritik 3. Untuk mengetahui keunggulan dan kekurangan buku tersebut 4. Untuk melatih diri untuk berpikir kritis dalam mencari informasi yang diberikan . 1



BAB II RINGKASAN ISI BUKU BUKU UTAMA Judul



:



Introductory Discrete Mathematics



Penulis



:



V.K. Balakhrishnan



Penerbit



:



Dover Publications, inc



Kota Terbit



:



New York



Tahun



:



1991



BAB 1 KOMBINATORIKA 2.1 DUA ATURAN PENGHITUNGAN DASAR Kombinatorika adalah salah satu bidang matematika modern yang tumbuh paling cepat. Memiliki banyak aplikasi untuk beberapa bidang matematika dan yang menjadi perhatian utama dengan studi tentang himpunan hingga atau diskrit (sebanyak himpunan bilangan bulat) dan berbagai struktur pada set ini, seperti pengaturan, kombinasi, penugasan, dan konfigurasi. Secara garis besar, tiga macam masalah muncul saat belaja set dan struktur ini pada mereka: (1) masalah keberadaan, (2) penghitungan masalah, dan (3) masalah pengoptimalan. Masalah keberadaan prihatin dengan pertanyaan berikut: Apakah ada setidaknya satu pengaturan yang diberikan jenis? Masalah penghitungan, di sisi lain, berusaha untuk menemukan jumlah kemungkinan pengaturan atau konfigurasi dari pola tertentu. Masalah menemukan pengaturan yang paling efisien dari pola tertentu adalah pengoptimalan masalah. Dalam bab ini kami mempelajari teknik untuk memecahkan masalah yang terlibat perhitungan. Teknik-teknik ini menjadi dasar untuk studi kombinatorika enumeratif, yang sebenarnya merupakan teori penghitungan dimana hasil yang melibatkan penghitungan diperoleh tanpa melakukan proses penghitungan yang tepat, yang bisa jadi membosankan. Misalkan ada 10 jurusan matematika dan 15 ilmu computer jurusan di kelas 25 dan kami diminta untuk memilih siswa dari kelas untuk mewakili matematika dan siswa lain untuk mewakili ilmu komputer. Sekarang ada 10 cara memilih jurusan matematika dan 15 cara memilih a jurusan ilmu komputer dari kelas. Selanjutnya tindakan memilih seorang siswa dari satu area sama sekali tidak bergantung pada tindakan memilih siswa dari area lain. Jadi secara naluriah jelas bahwa ada 10 x 15 = 150 cara memilih a perwakilan dari matematika dan perwakilan dari ilmu komputer. Di sisi lain, jika kita diminta untuk memilih satu perwakilan dari matematika



2



atau dari ilmu komputer, kita hanya memiliki 10 + 15 = 25 cara untuk mencapai hasil ini. Dalam kasus sebelumnya kami menggunakan aturan perkalian menghitung dan dalam terakhir aturan penjumlahan. Kedua aturan tersebut secara formal dapat dinyatakan sebagai berikut. ATURAN MULTIPLIKASI (Aturan Penghitungan Berurutan) Misalkan ada urutan kejadian r E1, E2, ..., Er, sehingga (1) ada n; cara di mana E1; (i = 1, 2, ..., r) dapat terjadi, dan (2) bilangan cara suatu peristiwa dalam urutan dapat terjadi tidak bergantung pada bagaimana peristiwa tersebut dalam urutan sebelum peristiwa itu terjadi. Lalu ada (n1).(n2)…….(nr) cara di mana semua peristiwa dalam urutan dapat terjadi. ATURAN TAMBAHAN (Aturan Penghitungan Disjunctive) Misalkan ada r event E1, E2,…, Er, sehingga (1) ada n1 hasil untuk E1, (i = 1, 2, ..., r), dan (2) tidak ada dua peristiwa yang dapat terjadi secara simulta dengan rapi. Lalu ada (n1) + (n2) +…… + (n1) Cara di mana salah satunya r acara dapat berlangsung. Contoh 1.1.1 Ada lima karakter dua huruf alfabet diikuti oleh tiga digit yang muncul di belakang salah satu rangkaian komputer mikro buatannya oleh perusahaan elektronik. Jumlah kemungkinan pabrikan computer tured dalam seri ini adalah (1) 26 x 26 x 10 x 10 x 10 = 676.000 jika jarak terdapat mengulang, (2) 26 x 25 x 10 x 10 x 10 = 650.000 jika huruf tidak dapat diulang, dan (3) 26 X 25 X 10 X 9 X 8 = 468.000 jika tidak ada karakter yang dapat ulang. Kami menggunakan aturan perkalian di sini.



2.2 PERMUTASI Pertimbangkan koleksi X dari n objek berbeda. Permutasi r dari X adalah susunan dalam satu baris objek r dari X. Tentu saja, r paling banyak n. Jadi jika X adalah kumpulan dari 5 huruf pertama a, b, c, d, dan e, maka edcb, dbea, dan bdca adalah beberapa dari beberapa 4-permutasi X. Jumlah total r-permutasi kumpulan n objek berbeda dilambangkan dengan P (n, r). Apa saja r-permutasi disini dapat dianggap sebagai urutan revents dimana jumlah tersebut Banyak cara suatu peristiwa dapat terjadi tidak tergantung pada bagaimana peristiwa sebelumnya peristiwa itu terjadi. Jadi kami menggunakan aturan perkalian menghitung untuk menyimpulkan itu P (n, r) sama dengan n (n - 1) (n - 2)……. (n - r + 1) karena sembarang objek dari X dapat dipilih dengan n cara dan setelah memilih itu, sewenang-wenang kedua objek dapat dipilih dengan cara (n - 1), dan seterusnya, sampai semua r objek terpilih.



3



Permutasi dan Masalah Alokasi Kita dapat mendekati proses pembuatan pengaturan objek dari yang berbeda sudut pandang. Pertimbangkan satu set n lokasi berbeda yang diatur dalam urutan tertentu dan kami diminta untuk mengalokasikan r objek yang berbeda ke lokasi ini sehingga tidak ada lokasi dapat menerima lebih dari satu objek. Kemudian jumlah cara pengalokasian r objek ini ke lokasi n juga P (n, r) dengan aturan perkalian sejak sembarang objek dapat dikirim ke salah satu lokasi dengan n cara, dan selanjutnya satu lagi bisa dikirim dengan cara (n - 1), dan seterusnya. Contoh 1.2.1 Jika X = {1, 2, 3, 4, 5, 6, 7} dan r = 3, banyaknya permutasi-r dari X adalah 7 x 6 x 5 = 210. Permutasi-n apa pun dari himpunan X dengan n elemen disebut permutasi dari X dan bilangan P (n, n) dari permutasi X adalah n (n - 1) (n - 2) ..... 3.2.1, yang dilambangkan dengan fungsi faktorial n !. Sangat mudah untuk melihatnya P (n, r) = n! / (n - r) !. [Bilangan bulat positif n! bisa menjadi sangat besar bahkan jika n adalah kecil nomor dua digit. Lebih dari 3,6 juta jika n = 10 dan mendekati sama dengan (2.433) (1018) jika n = 20.] Permutasi Melingkar dan Cincin Contoh 2.1.2 Pertimbangkan koleksi 5 batu dengan warna berbeda: biru (B), hijau (G), merah (R), merah muda (P), dan putih (W). (a) Banyaknya cara membuat pengikat di mana 5 batu ini akan ditempatkan secara horizontal, tentu saja, 5 ! (b) Berapa banyak cara kita bisa membuat pengikat di mana batu-batu ini ditempatkan dalam pola melingkar? Jawabannya harus kurang dari 5! Karena beberapa permutasi yang dipertimbangkan dalam (a) sekarang tidak berbeda. Untuk Misalnya jika kita memutar permutasi BGRPW satu kali searah jarum jam arah, kami mendapatkan permutasi GRPWB, dan dua permutasi ini tidak berbeda dalam pengaturan melingkar. Jika kita memperbaiki salah satu warna dan kemudian pertimbangkan permutasi yang dibentuk oleh 4 warna yang tersisa, ini permutasi semuanya berbeda. Misalnya, jika kita memperbaiki B dan mempertimbangkan RGPW dan RGWP, kami mendapatkan dua permutasi, BRGPW dan BRGWP, yaitu berbeda. Jadi hanya ada (4!) Permutasi melingkar seperti itu. (c) Bagaimana cara kita membuat cincin di mana batu-batu ini berada terpasang? Dalam sebuah cincin, tidak ada perbedaan antara permutasi dan permutasi "gambar cermin." Misalnya BGRPW dan BWPRG itu sama. Untuk setiap permutasi di (b), ada bayangan cermin. 4



Permutasi Umum Sekarang mari kita pertimbangkan koleksi X dari n objek (tidak harus berbeda) milik ke k grup tidak kosong yang berbeda sehingga (1) semua objek dalam grup identik, dan (2) objek dalam grup tidak identik dengan objek di grup lain. (Untuk Misalnya huruf dalam kumpulan a, b, a, b, b, d, e, e, d dapat dibentuk menjadi empat kelompok: satu untuk a, satu untuk b, satu untuk d, dan satu untuk e.) Asumsikan bahwa ada adalah objek në dalam kelompok i di mana i = 1, 2, ..., k. Pengaturan apa pun dalam deretan objek n ini disebut permutasi umum dari X. (Misalnya, LIN ISOIL adalah permutasi umum dari huruf yang muncul di kata ILLI-NOIS.) Jumlah permutasi umum tersebut dilambangkan dengan P (n; n, na,…..n), yang akan menjadi n! jika semua objek di X berbeda. Teorema 1.2.1 Jika koleksi X dari n objek terdiri dari k grup tidak kosong yang berbeda tersebut grup itu saya punya n ; benda identik (di mana i = 1, 2, ..., k), kemudian bilangan permutasi umum dari X adalah (n!) / (n1! (n2!) ... (nk!). Bukti Jika objek yang termasuk dalam grup i semuanya berbeda, pasti ada n! permutasi untuk elemen dalam grup ini. Jadi setiap permutasi umum menimbulkan permutasi N = (n1! (n2!) ... (nk!) dari X jika X memiliki objek yang berbeda. Jika t adalah jumlah total permutasi umum, kita memiliki (t) (N) = n !, dari yang diikuti oleh kesimpulan teorema. (Perhatikan bahwa jika k = n, setiap kelompok. Teorema 1.2.2 Jika ada ni objek identik dalam kelompok i (i = 1, 2, ..., k) dan jika r adalah jumlah total objek dalam kelompok k ini, objek r ini dapat ditempatkan di n lokasi berbeda, sehingga setiap lokasi menerima paling banyak satu objek, di cara, di mana t = P (n; n1, n2, ..., nk). Secara khusus, jika masing-masing kelompok memiliki persis satu objek, maka t = P (n, r), yang merupakan jumlah permutasi-r dari suatu himpunan dengan n elemen.



2.3 KOMBINASI Seperti pada bagian 1.2, misalkan X adalah kumpulan dari n objek berbeda. Koleksi apa pun dari r objek yang berbeda dari X disebut r-kombinasi dari X. Dengan kata lain, jika X adalah himpunan dengan n elemen, setiap subset dari X dengan r elemen adalah kombinasi-r dari X. Dalam kombinasi-r, urutan pemilihan elemen-elemen tidak penting, tidak seperti dalam kasus 5



permutasi-r. Jumlah kombinasi-r dari himpunan dengan n elemen dilambangkan dengan C (n, r), yang merupakan nomor tersebut dari himpunan bagian dari kardinalitas r. Jadi ada pasangan terurut P (n, 2) dan C (n. 2) pasangan tak berurutan dari dua elemen dalam satu set n elemen. Tentu saja, C (n, 0) = C (n, n) = 1. Apa hubungan antara C (n, r) dan P (n, r)? Pertimbangkan setiap subset A dari X dengan elemen r. Elemen berbeda r ini dapat diatur dengan cara (r!). Jadi ada permutasi (r!) Yang terkait dengan setiap subset elemen-r dari X. Tentu saja, menurut definisi, jumlah himpunan bagian elemen r dari X adalah C (n, r). Jadi jumlah permutasi-r adalah hasil kali dari (r!) dan C (n, r) oleh aturan perkalian. Jadi kami memiliki teorema penting berikut.



TEOREMA 1.3.1 C (n. r) • (r!) = P (n, r) KOROLAR C (n, r) = C (n, n - r) Kombinasi dan Masalah Alokasi dalam kasus permutasi, kita dapat menafsirkan kombinasi dari sudut pandang yang berbeda, sebagai masalah alokasi. Seperti sebelumnya, misalkan X adalah himpunan lokasi berbeda yang diatur dalam urutan tertentu dan pertimbangkan kumpulan r objek yang identik. Objek-objek ini akan dialokasikan ke lokasi n ini sehingga tidak ada lokasi yang menerima lebih dari satu subjek. Biarkan i menjadi jumlah total cara mengalokasikan objek r ini. Jika semua objek berbeda, setiap alokasi tersebut akan menimbulkan alokasi (r!). Dalam hal ini jumlah alokasi akan menjadi (t) (r!). Tetapi jumlah total alokasi jika objeknya berbeda adalah P (n, r). Jadi i = P (n, r)/(r!) = C (n, r).



TEOREMA 1.3.2 (Rumus Pascal) C (n, r) = C (n - 1, r) + C (n - 1, r - 1) Bukti: Misalkan X adalah himpunan dengan n elemen dan Y setiap himpunan bagian dari X dengan (n1) elemen. Misalkan i adalah elemen X yang tidak ada di Y. Setiap subset relement dari X adalah subset elemen-r dari Y atau gabungan dari subset Y dengan elemen (r - 1) dan himpunan singleton yang terdiri dari t. Dalam kategori sebelumnya ada himpunan C (n - 1, r) dan yang terakhir ada himpunan C (n - 1, r - 1). Dengan kata lain, banyaknya himpunan bagian X dengan r elemen adalah penjumlahan dari C (n - 1, r) dan C (n -1, r - 1). Rumus Pascal merupakan salah satu contoh 6



identitas kombinatorial yang dibuktikan dengan menggunakan argumen kombinatorial. Identitas ini juga dapat dibuktikan secara aljabar. TEOREMA 1.3.3 P(n;n1,n2…..., nk) = C (n; n1,n2,…………..,nk)



Teorema Multinomial TEOREMA 1.3.4 (Teorema Multinomial) Dalam istilah khas dalam perluasan (x1 + x2…… + xk)n, variable x1(i = 1, 2,. .., k) muncul n, kali (di mana n1, + n2 +:…+ nk = n) dan koefisien suku tipikal ini adalah C (n1, + n2 +:…+ nk) "variabel., n). Bukti: Bagian pertama dari pernyataan tersebut jelas karena ekspansi adalah hasil kali dari n ekspresi di mana setiap ekspresi adalah jumlah dari variabel k. Istilah tipikal di sini adalah tidak ada tetapi permutasi umum dari n objek dalam kumpulan X yang terdiri dari kelompok k, dan oleh karena itu koefisien dari suku tipikal ini adalah jumlah permutasi umum tersebut.



Partisi dari Himpunan Hingga Diberikan himpunan A dari kardinalitas n, masalah kombinatorial yang menarik adalah untuk menemukan banyaknya cara A dapat dipartisi menjadi k himpunan bagian sehingga himpunan bagian A, (i = 1, 2 ..... k) memiliki tepat n, clements. Misalnya, jika A = (1, 2, 3, 4, 5, 6), masalahnya adalah menemukan jumlah cara untuk membagi A menjadi (1) sehingga satu memiliki 2 elemen dan yang lainnya memiliki 3 klemen atau (3) tiga himpunan bagian sehingga masing-masing memiliki 2 unsur, menjadi 4 unsur atau (2) himpunan bagian dua memiliki dan seterusnya. Masalah ini setara dengan masalah alokasi untuk mengalokasikan n objek berbeda ke k lokasi yang dibahas sebelumnya ketika kardinalitas setiap himpunan dalam partisi berbeda seperti pada 6 elemen dari A ke dua lokasi sehingga lokasi I mendapat 2 elemen dan lokasi 2 mendapat 4 elemen. Banyaknya cara untuk membagi A menjadi dua himpunan, satu himpunan memiliki 2 elemen dan himpunan lainnya memiliki 4 juga C (6; 2, 4). Tetapi ketika himpunan bagian dalam partisi memiliki kardinalitas yang sama, kita harus menangani situasi di mana pengulangan terjadi. Misalnya, jika P = {I, 2, 3} dan Q = (4, 5, 6), maka partisi (P. Q) dan partisi (Q, P) adalah sama. Tetapi mengalokasikan P ke lokasi I dan Q ke lokasi 2 tidak sama dengan mengalokasikan Q ke lokasi (1). Ada C (6; 2, 4) cara mengalokasikan anggaran yang www.EngineeringEBooksPdf.com 48 Bab. 1 Kombinatorika I dan P ke lokasi 2. Jumlah partisi A menjadi dua himpunan bagian yang 7



sama kardinalitasnya adalah C (6; 3, 3) / 2. Secara lebih umum, kita mendapatkan hasil sebagai berikut, yang merupakan perpanjangan dari teorema alokasi dan aturan perkalian.



TEOREMA 1.3.5 Banyaknya cara untuk membagi himpunan kardinalitas n menjadi kelas yang terdiri dari p, himpunan bagian masing-masing dari kardinalitas n, (i = 1, 2, ... k) di mana tidak ada dua bilangan n yang sama adalah



2.4 LEBIH LANJUT PADA PERMUTASI DAN KOMBINASI Jika X adalah himpunan dengan n elemen, kita tahu bahwa permutasi-r dari X adalah susunan elemen dari X di mana tidak ada elemen yang berulang. Demikian pula, kombinasi-r adalah pemilihan elemen dari X di mana tidak ada elemen yang berulang. . Dalam kedua kasus r tidak boleh melebihi n. Jika kita mengizinkan pengulangan, tidak ada batasan pada r. (Karena X adalah himpunan, n elemen di dalamnya semuanya berbeda.). Urutan-r X adalah susunan r dari X di mana elemen-elemen tersebut dapat berulang, tetapi urutan kemunculan elemen-elemen ini adalah penting. Misalnya, aabdac dan aadbac adalah dua urutan 6 yang berbeda dari himpunan X = {a, b, c, d}. Setiap permutasi-r jelas merupakan urutan-r. Di sisi lain, setiap urutan-r dengan elemen yang berbeda disebut permutasi-r. Penerapan sederhana dari aturan perkalian menunjukkan bahwa banyaknya urutan-r dalam himpunan dengan n elemen adalah n'. Kumpulan objek r (tidak harus berbeda) yang dipilih dari himpunan X dari n elemen disebut koleksi-r dari X. Tidak seperti pemilihan-r, urutan pemilihan elemen tidak penting dalam koleksi-r. 4-koleksi [a, a, b, c] tidak berbeda dari 4-koleksi [a, b. c, a]. Keduanya mewakili 4 koleksi yang sama. Kombinasi-r apa pun adalah koleksi-r. Jika elemen dalam kumpulan-r berbeda, maka itu adalah kombinasi-r. Misalnya, jika X = {a, b, c, d} dan jika r = 3, himpunan dari semua 3 pilihan dari X akan menyertakan setiap subset dari X dengan 3 elemen dan pilihan seperti {a, a, a}, {a, b, b}, {d, a, d}dan seterusnya. Sebaliknya, jika r = 5, koleksi {a, b, b, b, d} cara memilih 5 elemen dari X, dan tidak ada subset dari X yang dapat menjadi dari satu 5 koleksi. TEOREMA 1.4.1 Jika X adalah himpunan kardinalitas n, maka banyaknya koleksi-r dari X adalah C (r + n - 1, n - 1), di mana r adalah bilangan bulat positif. 8



Bukti: Misalkan X = {1, 2, 3, ..., n}. Misalkan u adalah kumpulan-r dari X di mana 1 pengulangan x1 kali, 2 pengulangan x2 kali, ... dan n pengulangan xn, kali. Koleksi-r ini dapat direpresentasikan sebagai u = [⏟



⏟



⏟



⏟



]



di mana notasi i……..i berarti simbol i mengulangi x, kali. Demikian pula. Misalkan v adalah koleksi-r lain di mana 1 mengulangi y1 kali , 2 pengulangan y2 kali,….. dan n pengulangan yn, kali. Kemudian v = [⏟



⏟



⏟



⏟



]



di mana notasi i……i berarti simbol i mengulangi y, kali. Perhatikan bahwa dalam representasi u sebagai begitu juga pada representasi v, terdapat gap antara I dan 2, gap antara 2 dan 3. .... gap antara (n – 1). dan (n - 1) celah. Jadi setiap representasi dapat dianggap sebagai himpunan dari r + n - 1 lokasi berbeda. Semua



n -1 kosong identik. Alokasi (n - 1) kosong ini ke (r + n- 1) 1) Lokasi



kombinatorik menentukan koleksi-r. Jadi jumlah berbeda r-collections sama dengan jumlah cara mengalokasikan (n - 1) objek identik ke (r + n - 1) lokasi berbeda sehingga setiap lokasi menerima paling banyak satu objek. Angka ini adalah C (r + n - 1, n - 1), seperti yang kita lihat di Bagian 1.3. TEOREMA 1.4.2 (a) Banyaknya solusi berbeda dalam bilangan bulat nonnegatif dari persamaan linier (dalam n variabel)



adalah



(b) Jumlah solusi distinet dalam bilangan bulat nonnegatif dari pertidaksamaan linier (dalam n variabel)



adalah



(c) Banyaknya suku dalam muai banyak suku



adalah



Bukti: (a) Setiap solusi



dalam bilangan bulat nonnegatif sesuai dengan kumpulan



elemen r (dari himpunan X yang terdiri dari n variabel) di mana x, ulangan s, waktu, di mana s, sr, dan wakil sebaliknya Jumlah koleksi tersebut adalah



menurut Teorema



1.4.1. (b) Misalkan y adalah variabel nonnegatif sehingga



disebut variabel slack.)



Sekarang kita memiliki persamaan linier dalam variabel y = (n + 1). Solusi dalam bilangan bulat non-negatif dari persamaan ini dalam variabel (n + 1) adalah solusi dalam bilangan bulat 9



non-negatif dari pertidaksamaan dalam n variabel



, dan sebaliknya, Jadi bilangan yang



dibutuhkan adalah C (r + n, n). (c) Setiap suku dalam ekspansi dapat dianggap sebagai hasil kali dari n variabel yang jumlah eksponen variabelnya adalah r. Oleh karena itu, jumlah suku dalam pemuaian sama dengan jumlah kumpulan elemen r dari himpunan



X terdiri dari variabel di mana pengulangan



diperbolehkan. Masalah Alokasi dalam Pengaturan Umum Kita sekarang mempertimbangkan masalah alokasi r objek identik ke n lokasi berbeda sehingga setiap lokasi dapat menampung objek sebanyak yang diperlukan. Dalam berapa banyak cara kita dapat mencapai ini? Jika jumlah objek yang ditempatkan di lokasi i adalah x, (di mana i = 1, 2, ..., n), solusi apa pun dari persamaan



dalam bilangan bulat non-negatif



sesuai dengan cara mengalokasikan objek r ini ke lokasi n, dan sebaliknya. Jadi ada cara untuk menempatkan r obyek identik di lokasi yang berbeda. Kami menggabungkan observasi ini dengan Teorema 1.4.1 dan 1.4.2 untuk membuat pernyataan berikut: TEOREMA 1.4.3 L = banyaknya cara memilih r elemen (dengan pengulangan) dari himpunan yang memiliki n elemen M = bilangan cara mengalokasikan r objek identik ke n lokasi berbeda N = jumlah solusi dalam bilangan bulat nonnegatif dari persamaan Kemudian Maka



Kami



sekarang meringkas empat kasus permutasi dan kombinasi (tanpa atau dengan



pengulangan) relemen dari satu set n elemen yang berbeda dan menafsirkan hasil ini sebagai dua model penghitungan sebagai berikut.



Model pemilihan Jumlah cara pemilihan elemen r dari himpunan n elemen adalah: 1. P (n, r) jika elemen yang dipilih berbeda dan urutan pemilihannya penting. 2. C (n, r) jika elemen yang dipilih berbeda dan urutan pemilihannya tidak penting. 3. N 'jika elemen yang dipilih belum tentu berbeda dan urutannya penting. 4. C (r + n - 1, n - 1) jika elemen yang dipilih belum tentu berbeda dan urutannya tidak penting. 10



Model Alokasi Jumlah cara untuk mengalokasikan r objek ke n lokasi berbeda adalah: 1. P (n, r) jika objek berbeda dan tidak ada lokasi yang dapat mengambil lebih dari satu objek. 2. C (n, r) jika objek identik dan tidak ada lokasi yang dapat mengambil lebih dari satu objek. 3. N jika objeknya berbeda dan tidak ada batasan jumlah objek di suatu lokasi. 4. C (r + n - 1, n - 1) jika objek identik dan tidak ada batasan jumlah objek di suatu lokasi.



2.5 PRINSIP PIGEONHOLE Ini adalah prinsip yang sangat jelas dan terlihat sangat sederhana, seolah-olah tidak memiliki arti penting. Namun, dalam praktiknya ini sangat penting dan berkuasa karena generalisasinya melibatkan beberapa hasil yang mendalam dan mendalam dalam kombinasi teori kombinatorika dan dalam teori bilangan. Kami menggunakan prinsip pigeonhole ketika kami mengatakan bahwa dalam kelompok mana pun yang terdiri dari tiga orang, setidaknya dua orang berjenis kelamin sama. Misalkan jurusan ilmu komputer yang baru dibentuk di sebuah perguruan tinggi memiliki 10 anggota fakultas dan hanya 9 kantor yang menampung mereka. Kemudian ide yang mendasari di balik pernyataan yang jelas bahwa setidaknya satu kantor akan memiliki lebih dari satu penghuni lagi-lagi adalah prinsip lubang persembunyian. Jika ada 19 anggota fakultas, bukan 10, setidaknya satu kantor akan memiliki lebih dari dua penghuni. Demikian pula. jika ada setidaknya 367 siswa di aula tempat tinggal, sama jelasnya bahwa setidaknya dua dari mereka akan berulang tahun yang sama. Dilaporkan bahwa kulit kepala manusia paling banyak memiliki 99.999 rambut. Jadi di kota mana pun yang populasinya melebihi 4 juta akan ada setidaknya 41l orang (kulit kepala botak tidak berambut) dengan jumlah rambut yang sama! Kami dapat mengutip beberapa contoh seperti ini.



THEOREMA 1.5.1 (a) Jika m merpati dialokasikan untuk n merpati, maka setidaknya satu lubang memiliki lebih dari k merpati, di mana k adalah lantai (m - 1) / n. (b) Jika m = P1 + P2 +….+ Pn - n + 1 merpati (setiap p, adalah bilangan bulat positif) dialokasikan ke n lubang merpati, maka lubang merpati pertama memiliki setidaknya p, merpati, atau lubang merpati kedua memiliki setidaknya P2, ..., atau setidaknya memiliki p, pigeon. Bukti: (a) Sekarang (n) · (k)