Matematika Diskrit : Prinsip Sarang Merpati, Hukum Sum, Hukum Product, Ekspansi Hukum Sum Dan Product, Dan Pola Soal

Matematika Diskrit : Prinsip Sarang Merpati, Aturan Sum, Aturan Product, Perluasan Aturan Sum dan Product, dan Contoh Soal

Prinsip Sarang Merpati

Jika n+1 atau lebih objek ditempatkan dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi 2 atau lebih objek.

Contoh 1 : 

Dari 27 mahasiswa, paling tidak ada 2 orang yang namanya berawalan aksara yang sama. Hal ini alasannya hanya ada 26 aksara dalam alfabet. 

Andaikan nama-nama mahasiswa yakni merpati dan 26 aksara yakni 26 buah sarang merpati. Kita tempatkan 27 nama-nama mahasiswa di sarang merpati, memasangkan aksara awal nama dengan sarang berhuruf yang sama. 

Maka akan ada sedikitnya 2 nama di sarang merpati yang sama.

Contoh 2 : 

Jika ada 32 mahasiswa, maka setidaknya ada 2 orang yang mempunyai tanggal lahir yang sama. 

Tanggal hanya terdiri atas 1- 31. 32 tanggal lahir mahasiswa sebagai merpati, 31 tanggal sebagai sarang merpati. 

Jika 32 merpati ditempatkan di 31 sarang merpati tersebut, sesuai dengan tanggal lahir, maka akan ada 1 sarang yang berisi lebih dari 1 mahasiswa.

Latihan 1

Jika ada banyak bola di kotak dengan warna merah, kuning, biru, dan hijau. Berapa banyaknya bola yang sedikitnya harus diambil untuk mendapat setidaknya 2 bola dengan warna sama?

Latihan 2

Prinsip Sarang Merpati Dirampatkan

Jika M buah objek ditempatkan di dalam n kotak, maka paling sedikit terdapat satu kotak yang berisi minimal ⌈ M/n ⌉ buah objek. 

Contoh 1

Jika ada 50 mahasiswa, maka setidaknya ada ⌈ 50/12 ⌉  = 5 orang mahasiswa yang berulang tahun pada bulan yang sama. 

Percobaan

Percobaan adalah proses yang dilakukan secara fisik dan sanggup diamati hasilnya.

Contoh 1

Percobaan melempar dadu. 

Hasil yang diamati: mata dadu yang muncul sehabis setiap lemparan

Hasil yang mungkin terjadi: {1,2,3,4,5,6}

Percobaan melempar koin.

Hasil yang diamati: sisi koin yang muncul sehabis setiap lemparan

Hasil yang mungkin terjadi: {tail, head}

Latihan 3

1. Percobaan mengambil kartu dari satu set kartu bridge

Hasil yang diamati?

Hasil yang mungkin terjadi?

2. Dalam pemilihan ketua kelas, ada 5 kandidat perempuan dan 6 kandidat pria. Ada berapa kemungkinan terpilihnya kandidat perempuan atau pria?

3. Dalam pemilihan pengurus kelas, akan dipilih 1 orang pengurus laki-laki dan 1 orang pengurus wanita. Kandidat pengurus laki-laki yakni Adi, Budi, Didi dan kandidat pengurus perempuan yakni Lina, Dina, Rina, Tina. Berapa kemungkinan pasangan yang terpilih? Apa saja kemungkinan tersebut?

Aturan sum

Misalkan

Dilakukan percobaan pertama dengan p hasil yang mungkin

Dilakukan percobaan kedua dengan q hasil yang mungkin

Maka

Kemungkinan hasil percobaan pertama atau percobaan kedua yakni p+q.

Contoh 1 : 

Sebuah restoran menyediakan 3 jenis masakan dan 2 jenis minuman. Makanan yang disediakan yakni nasi goreng, soto, dan mie goreng. Minuman yang disediakan yakni teh anggun dan es jeruk. Jika setiap orang boleh memesan 1 jenis masakan atau 1 jenis minuman, berapa kemungkinan masakan atau minuman yang sanggup dipesan? 

Percobaan 1: percobaan menentukan 1 jenis makanan. 

Banyaknya hasil yang mungkin : 3 

Kemungkinan hasil : {nasi goreng, soto, mie goreng}

Percobaan 2 : percobaan menentukan 1 jenis minuman.

Banyaknya hasil yang mungkin : 2

Hasil yang mungkin : {teh manis, es jeruk}

Banyaknya hasil yang mungkin pada percobaan 1 atau percobaan 2 yakni 3+2 = 5, yaitu {nasi goreng, soto, mie goreng, teh manis, es jeruk}

Contoh 2 :

Berapa banyak hasil yang mungkin pada percobaan pelemparan dadu atau pelemparan koin ?

Percobaan pelemparan dadu dengan 6 kemungkinan hasil. 

Percobaan pelemparan koin dengan 2 kemungkinan hasil.

Maka kemungkinan hasil pada pelemparan dadu atau pelemparan koin yakni 6+2 = 8.

Aturan product

Misalkan

Dilakukan percobaan pertama dengan p hasil yang mungkin

Dilakukan percobaan kedua dengan q hasil yang mungkin

Maka

Kemungkinan hasil percobaan pertama dan percobaan kedua yakni p x q.

Contoh 1 :

Sebuah restoran menyediakan 3 jenis masakan dan 2 jenis minuman. Makanan yang disediakan yakni nasi goreng, soto, dan mie goreng. Minuman yang disediakan yakni teh anggun dan es jeruk. Jika setia orang boleh memesan 1 jenis masakan dan 1 jenis minuman, berapa kemungkinan masakan dan minuman yang sanggup dipesan?

Kemungkinan masakan dan minuman yang sanggup dipesan yakni 3 x 2 = 6.

Perluasan Aturan sum dan product

Jika ada n percobaan dengan pi yakni banyaknya kemungkinan hasil dari masing-masing percobaan, maka hukum sum dan product menjadi :

Sumber http://wikiwoh.blogspot.com

Kombinatorika - Hukum Perkalian

Sebelum memperkenalkan defenisi hukum perkalian dalam kombinatorika (matematika diskrit) ada baiknya anda perhatikan ilustrasi di bawah ini:
Sebuah event fun-run akan di adakan. Masing masing penerima akan diberikan nomor penerima yang terdiri dari 5 digit. 2 digit terakhir akan di isi oleh abjad alphabet. Sementara 3 digit awal akan diisi oleh angka. Berapa banyak kemungkinan seluruh nomor yang sanggup dibuat?

Dalam penyelesaian kasus menyerupai di atas maka dipakai hukum perkalian. Secara matematis, hukum perkalian tersebut sanggup didefenisikan menjadi:
Jika sebuah mekanisme terdiri dari beberapa insiden dan dimisalkan
$n_1$ insiden 1
$n_2$ insiden 2
$n_3$ insiden 3
....
$n_p$ insiden p
Maka seluruh insiden total dalam mekanisme tersebut sanggup dihitung menjadi
$n_1 \times n_2  \times n_3 \times ... \times n_p$.

Perhatikan beberapa teladan soal di bawah ini:
Soal 1: Penomoran bangku di auditorium berbentuk satu abjad disambung dengan bilangan bundar aktual tidak lebih dari 100. Berapa banyak bangku yang sanggup dilabeli secara berbeda?

Jawab: Kursi pada auditorium akan dilabeli dengan ketentuan berbentuk satu abjad disambung dengan bilangan bundar aktual tidak lebih dari 100. Banyaknya insiden pertama untuk melabeli bangku dengan abjad ada 26 sedangkan pada insiden kedua untuk melabeli bangku dengan angka sebanyak 100 . Sehingga menurut hukum perkalian, banyaknya cara melabeli bangku pada auditorium dengan ketentuan tersebut sanggup dilakukan sebanyak 26 × 100 = 2600 cara. Jadi, banyaknya bangku yang sanggup dilabeli dengan label yang berbeda ada 2600.



Soal 2: Berapa banyak bit string dengan panjang 7 jika
a) tidak ada hukum pada string tersebut
b) bit string diawali oleh substring 1
c) di akhiri oleh substring 11

Jawab:
Catatan: Bit ialah susunan bilangan dengan angka 0 dan 1 saja.
a) $n_1 =n_2=n_3=n_4=n_5=n_6=n_7=2$ Kenapa dua? Karena setiap posisi bit sanggup di isi angka 0 dan 1. Artinya ada dua kemungkinan insiden di sana. Sehingga sesuai hukum perkalian sanggup dihitung:
$n_1 \times n_2  \times n_3 \times ... \times n_p \\ 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 = 2^7$.

b) bit awal harus di isi angka 1. Jadi, $n_1 = 1$ sementara untuk bit lainnya bebas alias sanggup di isi oleh angka 0 dan 1.
$n_2=n_3=n_4=n_5=n_6=n_7=2$
Total = $1 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 = 2^6$

c) Diakhiri string 11, artinya $n_6 = n_7=1$ Dengan defenisi yang sama akan diperoleh,
$n_1 =n_2=n_3=n_4=n_5=2$
$2 \times 2 \times 2 \times 2 \times 2 \times 1 \times 1 = 2^5$

Soal 3: Berapa banyak fungsi dari himpunan dengan m elemen ke himpunan dengan n elemen?

Jawab:
Sebuah fungsi menghubungkan masing - masing elemen m di domain dengan salah satu n elemen di kodomain. Sehingga berdasarkan
hukum perkalian, ada n×n×…×n sebanyak m kali, sehingga sanggup ditulis $n^m$ fungsi dari himpunan dengan m elemen ke himpunan dengan n elemen. Sampel, banyaknya fungsi dari himpunan dengan 2 elemen ke himpunan dengan 4 elemen ada = 2x2 x2 x2 = $2^4$= 16

Soal 4: Sebuah perusahaan telekomunikasi menyediakan nomor telepon rumah yang terdiri atas 10 digit dengan format YNNN-XXXXXX dimana Y=0, N=2,...,9 dan X=0,...9. Berapakah banyaknya kemungkinan nomor telepon rumah yang tersedia?

Jawab:
$n_Y$ = 1 \\ n_N =8 \\ n_X=10$
Sehingga totalnya,
1x8x8x8x10x10x10x10x10x10 = $8^3 \times 10^6$


Sumber http://www.marthamatika.com/

Kombinatorika - Hukum Penjumlahan

Aturan Penjumlahan dalam kombinatorika, Kapan digunakan? Aturan penjumlahan ini dipakai ketika suatu kejadian sanggup dikerjakan dengan beberapa cara, tetapi cara-cara ini tidak sanggup dikerjakan pada waktu yang sama.
Jika
$n_1$ kejadian 1
$n_2$ kejadian 2
$n_3$ kejadian 3
....
$n_p$ kejadian p
Maka seluruh kejadian total dalam mekanisme tersebut sanggup dihitung menjadi
$n_1 + n_2  + n_3+... + n_p$.

Sebagai pengantar awal, antara kejadian tidak ada korelasi yang terjadi dalam waktu yang bersamaan. Ini anda harus benar pahami untuk membedakannya dengan aturan perkalian kombinatorika, Lebih lanjut perhatikan pola perkara hukum penjumlahan di bawah ini,


Soal 1: Dalam sebuah kepanitiaan, wakil dari sebuah jurusan sanggup dipilih dari dosen, atau mahasiswa. Jika pada jurusan tersebut mempunyai 20 dosen dan 43 mahasiswa, Berapa banyak cara menentukan wakil dari jurusan tersebut?

Jawab: Ada 20 cara untuk menentukan wakil kalau dari dosen. Sementara itu 43 cara menentukan wakil dari  mahasiswa. Sebab tidak ada korelasi dosen dan mahasiswa, maksudnya: TIDAK ADA SATU ORANG YANG MENJADI DOSEN DAN MAHASISWA DALAM WAKTU BERSAMAAN DI UNIVERSITAS TERSEBUT. maka menurut hukum penjumlahan, ada 20+43=63 cara untuk menentukan wakil dari jurusan itu.

Soal 2: Jenni sanggup menentukan sebuah proyek komputer dari salah satu diantara tiga daftar yang tersedia. Tiga daftar tersebut terdiri atas 23, 15, dan 19 kemungkinan proyek. Proyek - proyek komputer yang ada pada ketiga daftar tersebut semuanya berbeda. Berapa banyak kemungkinan Jenni tersebut menentukan proyek komputer?

Jawab:
Analisis, Jenni TIDAK AKAN MENGERJAKAN 2 PROYEK DALAM WAKTU BERSAMAAN. Makanya disini dipakai hukum penjumlahan. Sehingga total banyak cara Jenni menentukan proyek tersebut,
23+15+19 = 57.
Sumber http://www.marthamatika.com/

Kombinatorika - Hukum Pengurangan

Melanjutkan aturan perkalian dan aturan penjumlahan dalam kombinatorik, pada halaman ini akan diuraikan ihwal hukum pengurangan. Defenisi ihwal hukum pengurangan sanggup dijelaskan sebagai berikut.

Jika suatu insiden sanggup dikerjakan dengan $n_1$ cara atau $ n_2$ cara maka banyaknya cara yang sanggup terjadi pada insiden tersebut yaitu $n_1 + n_2$ dikurangi banyaknya insiden bersama pada $n_1$ dan $n_2$ cara.

Dalam istilah lain hukum pengurangan ini dikenal juga dengan nama prinsip inklusi-ekslusi. Sebagai materi untuk mempermudah pemahaman anda, anda sanggup perhatikan rujukan soal dan pembahasan ihwal hukum pengurangan di bawah ini.


Soal 1. Sekelompok siswa berjumlah 350 orang. Sejumlah 220 orang suka matematika , 147 orang menyukai kimia, dan 51 orang suka kedua-duanya. Berapa orang  yang tidak suka matematika ataupun kimia

Pembahasan:
Misal A = Himpunan yang suka matematika, |A|=220; B = Himpunan yang suka kimia, |B|=147; A∩B = Himpunan yang suka matematika dan kimia, |A∩B|=51; dan A∪B = Himpunan yang suka matematika atau kimia, maka sanggup dituliskan,
A∪B=A+B−A∩B=220+147−51=316
Karena total 350 orang, yang suka kimia atau matematika 316, maka yang tidak suka matematika atau kimia akan menjadi 350-316 = 34 orang.

Soal 2. Berapa banyak bit string dengan panjang 8 kalau di awali oleh substring 1 atau diakhiri oleh substring 00?

Pembahasan:
Banyaknya bit string dengan panjang 8 yang diawali oleh substring 1 ada $2^7$=128. Lebih membantu baca  aturan perkalian .
Banyaknya bit string dengan panjang 8 yang di akhiri oleh substring 00 ada $2^6$=64.
banyaknya bit string dengan panjang 8 yang diawali oleh substring 1 dan diakhiri oleh substring 00 ada $2^5$=32.
Kaprikornus banyaknya bit string dengan panjang 8 kalau di awali oleh substring 1 atau diakhiri oleh substring 00 yaitu 128+64-32=160 bit string
Sumber http://www.marthamatika.com/

Kombinatorika - Hukum Pembagian

Setelah ada hukum perkalian, hukum penjumlahan dan hukum pengurangan tentu adapula yang disebut dengan hukum pembagian. Defenisi hukum pembagian dalam matematika dijelaskan sebagai berikut.

Ada $ \frac {n}{d}$ cara pada sebuah kejadian kalau kejadian tersebut sanggup dikerjakan memakai sebuah mekanisme yang menghasilkan n cara, dan untuk setiap cara w, tepatnya ada d dari n cara yang berkorespondensi ke cara w

Bentuk pengertian hukum pembagian lain ditinjau dari segi Himpunan,
Jika himpunan berhingga A yaitu adonan dari n pasang subset yang saling lepas yang masing - masing subset terdiri atas d elemen, maka $ n= \frac {|A|}{d}$.

Sementara dari tinjauan fungsi, arti hukum pembagian mempunyai defenisi,
Jika f yaitu fngsi dari A ke B dimana A dan B yaitu hmpunan berhingga, dan untuk setiap nilai y∈B ada tepatnya d nilai x∈A sedemikian sampai f(x)=y (dalam kasus ini f yaitu d ke satu), maka $|B|= \frac {|A|}{d}$

Sebagai mempermudah pemahaman, anda sanggup perhatikan tumpuan soal dan pembahasan mengenai hukum pembagian di bawah ini,

Soal . Berapa banyak cara empat orang duduk mengelilingi meja lingkaran dimana dua susunan daerah duduk dianggap sama kalau teman duduk disamping kanan dan samping kirinya sama?

Jawab: Misal daerah duduk pada meja lingkaran di labeli dengan label 1,2,3, dan 4, maka

1. ada 4 cara untuk menentukan seseorang duduk pada daerah duduk 1, 
2. ada 3 cara untuk menentukan seseorang duduk pada daerah duduk 2, 
3. ada 2 cara untuk menentukan seseorang duduk pada daerah duduk 3, 
4. ada 1 cara untuk menentukan seseorang duduk pada daerah duduk 4. 

Sehingga semuanya ada 4!= 24 cara. Namun, masing-masing 4 pilihan untuk daerah duduk 1 mempunyai kesamaan susunan.
Contohnya begini,

2 kondisi di atas dianggap sama lantaran di samping kanan dan kiri si '1' ada '2' dan '4' meskipun pada kejadian pertrama '4' di kiri dan '2' di kanan dan pada kejadian kedua '4' dikanan dan '2' di kiri.

Oleh lantaran susunan menyerupai ilustrasi di atas di anggap sama, maka menurut hukum pembagian banyak cara penempatan sesunggguhnya yaitu: 24/4=6 cara.
Sumber http://www.marthamatika.com/

Prinsip Pigeon-Hole (Sarang Merpati) Dalam Matematika

Dalam kombinatorika sebagai salah satu bab ilmu matematika dikenal prinsip sarang/sangkar merpati. Atau secara luas ini dikenal dengan Prinsip Pigeonhole. Sebagai ilustrasi awal paling sederhana mengenai Prinsip Pigeonhole ini sebagai berikut,
Jika seseorang mempunyai 13 merpati dan mempunyai 12 sangkar merpati, maka niscaya akan ada satu minimal sangkar yang akan berisi 2 merpati. 

Selanjutnya, generalisasi dari ilustrasi di atas sanggup kita defenisikan,

Teorema 1 [Prinsip Pigeonhole]

Jika n merpati ditempatkan pada m rumah merpati, dimana n>m, maka terdapat rumah merpati yang memuat paling sedikit dua merpati.

Pembuktian dari teorema 1 ini sebagai berikut, pembuktian secara kontradiktif.
Misal kesimpulan dari pernyataan di atas tidak benar,bisa diasumsikan bahwa 1 rumah merpati memuat paling banyak satu merpati.

Prinsip rumah merpati disebut juga dengan Dirichlet drawer principle. Anda sanggup perhatikan pola aplikasi prinsip pigeon hole di bawah ini,

Kasus 1. Diantara 367 orang, tunjukkan bahwa sedikitnya ada dua orang yang mempunyai hari ulang tahun yang sama.

Jawab: Karena dalam setahun hanya ada 366 kemungkinan hari ulang tahun, maka akan ada sedikitnya dua orang yang punya hari ulang tahun yangsama.

Kasus 2
Pada ketika pembentukan kiprah kelompok yang dibagi menjadi enam kelompok, tujuh mahasiswa tidak masuk kuliah sehingga mereka belum terdaftar dalam kelompok yang sudah dibagi. Tunjukkan bahwa palingsedikit ada dua mahasiswa yang bergabung dalam satu kelompok!

Jawab: Untuk menjawab pertanyaan ini kita sanggup mengunakan Teorema 1. Asumsikan bahwa tujuh mahasiswa yang tidak masuk kuliah sebagai banyaknya merpati dan banyaknya kelompok pada tugas
kuliah tersebut sebagai rumah merpati. Sehingga menurut Teorema 1 akan ada satu kelompok yang memuat paling sedikit dua mahasiswa yang tidak masuk kuliah.

Kasus 3
Berapa banyak pelajar yang harus berada dalam kelas untuk menjamin bahwa sedikitnya ada dua pelajar yang mempunyai nilai ujian yangsama, kalau nilai ujian ini berkisar dari 0 hingga 100?

Jawab: Karena nilai ujian berkisar dari 0 hingga 100 maka ada 101 kemungkinan nilai pada ujian. Berdasarkan prinsip rumah merpati, maka diantara 102 pelajar seharusnya ada paling sedikit 2 pelajar dengan nilai ujian yang sama.

Teorema 2 Pigeon-Hole 

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.

Bukti: Menggunakan Prinsip Pigeonhole Bentuk Pertama dengan 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 Kasus : Ketua Program Studi Matematika akan menciptakan isyarat matakuliah untuk matakuliah-matakuliah bidang studi  matematika dengan cara menambahkan tiga angka pada abjad KPM. Terdapat 51 matakuliah yang harus diberi isyarat dan tiga angka yang harus ditambahkan pada abjad KPM harus berkisar antara 101 hingga dengan 200. Tunjukkan bahwa terdapat paling sedikit dua matakuliah yang diberi isyarat dengan angka berurutan.

Solusi: Misalkan A ialah himpunan matakuliah yang akan diberi isyarat abjad KPM yang dilanjutkan dengan bilangan antara 101 hingga 200, |A|=51. Misalkan pula B ialah himpunan bilangan antara 101 hingga 200 yang memenuhi, setiap x,y∈B,|x−y|>1. 

Dalam hal ini B ialah himpunan bilangan antara 101 hingga 200 yang tidak berurutan sehingga maksimal |B|=49. Jika setiap elemen di A dipetakan ke B (ini akan sama dengan perjuangan untuk memberi isyarat mata kuliah sedemikian hingga diantara dua mata kuliah tidak ada isyarat yang berurutan) maka menurut Teorema 2 akan ada sedikitnya dua elemen katakanlah x1,x2∈A sedemikian hingga f(x1)=f(x2). 

Jika hasil ini dikaitkan kembali dengan perjuangan untuk memberi isyarat mata kuliah sedemikian hingga diantara dua mata kuliah tidak ada isyarat yang berurutan, maka akan ada mata kuliah yang diberi isyarat yang sama. Padahal dilarang ada dua mata kuliah dengan isyarat yang sama, maka salah satu mata kuliah dengan isyarat yang sama harus diberi isyarat bilangan antara x,y∈B,|x−y|=1. Akibatnya, akan ada sedikit dua matakuliah yang diberi isyarat dengan bilanganberurutan. 

Teorema 3 [Generalisasi Prinsip Pigeonhole]

Jika f merupakan sebuah fungsi dari suatu himpunan terhingga X ke suatu himpunan terhingga Y, dimana |X|=n, |Y|=m dan $ \frac {n}{m}=k$, maka terdapat paling sedikit k anggota x1,x2,...,xk∈X sedemikian hingga

f(x1)=f(x2)=...=f(xk)

Contoh Kasus 1:

Diantara 100 orang sedikitnya ada $\frac {100}{12}$=9 orang yang lahir pada bulan yang sama.

Contoh Kasus 2: 

Berapakah jumlah minimum mahasiswa yang diharapkan dalam kelas matematika diskrit sedemikian hingga sedikitnya ada 6 mahasiswa yang mempunyai nilai grade yang sama kalau ada lima kemungkinan nilai gradematematika diskrit yaitu A,B,C,D, dan E?

Solusi:Jumlah minimum mahasiswa yang diharapkan dalam kelas matematika diskrit yang sedikitnya ada 6 mahasiswa yang mempunyai nilai grade yang sama ialah nilai terkecil n∈Z sedemikian hingga $\frac {n}{5}$=6. Nilai terkecil n∈Z tersebut yaitu n=5.5+1=26. Jika kita hanya mempunyai 25 mahasiswa maka sedikitnya hanya ada 5 mahasiswa yang mempunyai nilai grade yang sama. Oleh karenanya, 26 ialah jumlah minimum mahasiswa sedemikian hingga sedikitnya ada 6 mahasiswa yang mempunyai nilai grade yang sama.

Contoh Kasus 3:

Seorang kyai di sebuah desa yang selalu diminta untuk menawarkan nama bayi yang lahir, menyiapkan nama depan Muhammad, Ahmad, Abdul dan nama belakang Hadi, Akbar, Gofur bagi bayi yang lahir dalam suatu bulan tertentu. Pada bulan tersebut terdapat sebelas bayi yang lahir di desa itu. Tunjukkan bahwa paling sedikit ada dua bayi yang mempunyai nama yang sama dengan perkiraan bahwa kyai tersebut selalu menawarkan nama depan dan belakang!

Solusi:

Nama depan yang disiapkan kyai tersebut ialah Muhammad, Akhmad, dan Abdul sedangkan nama belakangnya ialah Hadi, Akbar, dan Gofur. Berdasarkan prinsip perkalian, kombinasi nama bayi yang dipersiapkan ada 9 nama yaitu Muhammad Hadi, Muhammad Akbar, Muhammad Gofur, Akhmad Hadi, Akhmad Akbar, Akhmad Gofur, Abdul Hadi, Abdul Akbar, dan Abdul Gofur. Jika kita misalkan banyaknya bayi yang lahir bulan itu sebagai banyaknya merpati dan banyaknya kombinasi nama bayi yang disediakan sebagai banyaknya rumah merpati, maka menurut Prinsip Pigeonhole, akan ada sedikitnya dua orang anak yang mempunyai nama yang sama.

Sumber : http://emodul-matematika.fmipa.unej.ac.id

Sumber http://www.marthamatika.com/

Koefisien Binomial (Ekspansi Binomial)

Ekspansi binomial merupakan salah satu bentuk kegunaan aplikasi perhitungan kombinasi. Misalkan anda mempunyai $(x+y)^n$ , maka penggunaan perluasan binomial yakni untuk memilih nilai dari koefisien pembagian terstruktur mengenai perluasan tersebut.

Sebagai  pola sederhana, misalkan
$(x+y)^4 =x^4+4x^3y+6x^2y^2+4xy^3+y4$.
Sangat sederhana, anda sanggup memilih perluasan suku suku pembagian terstruktur mengenai dan koefisiennya. Lantas bagaimana kalau menemukan permasalahan $(x+y)^100$. Bisakah anda memilih koefisien $x^{49}y^{51}$. Inilah bentuk penggunaan kombinasi dalam perluasan binomial. Di sini ada beberapa teorema,

Teorema 1 -Teorema Koefisien Binomial

Misalkan x dan y yakni variabel, dan n yakni bilangan bundar non-negatif, maka

Pembuktian teorema ini sanggup mengunakan kombinatorik. Suku pada penjabara $(x+y)^n$ akan berbentuk $ x^{n−j}y^j$ untuk nilai j =0,1,2,...,n. Perhitungan banyaknya suku
Untuk menghitung banyaknya $ x^{n−j}y^j$, perlu dipilih$ (n−j) x $dari n faktor. Oleh alasannya yakni itu maka koeefisien dari $ x^{n−j}y^j$ yakni $\begin{pmatrix} n \\  n-j \end{pmatrix}$ yang ekivalen dengan $\begin{pmatrix} n \\  j \end{pmatrix}$

Contoh Soal Ekspansi Binomial 1
Berapakah nilai koefisien dari $x^{12}y^{13}$ pada perluasan $(x+y)^{25}$?

Pembahasan:
Berdasarkan teorema binomial maka koefisien dari $x^{12}y^{13}$ adalah,
$\begin{pmatrix} 25 \\  13 \end{pmatrix}=_{25} C _{13}  = \frac {25!}{13!12!}=5.200.300$

Contoh Soal Ekspansi Binomial 2
Berapakah nilai koefisien dari $x^{12}y^{13}$ pada perluasan $ (2x−3y)^{25}$

Pembahasan:
lisan $(2x−3y)^{25}= (2x+(−3y))^{25}$.
Berdasarkan teorema binomial,

maka $x^{12}y^{13}$ di sanggup pada dikala j=13.
$\begin{pmatrix} 25 \\  13 \end{pmatrix} 2^{12}(−3)^{13}= _{25} C_{13}2^{12}(−3)^{13}=− \frac {25!}{13!12!} 2^{12}3^{13}$

Berikutnya lanjutkan membaca: Teorema 2 - Identitas Segitiga Pascal.
Sumber http://www.marthamatika.com/