MATEMATIKA DISKRIT
KOMBINATORIAL dan PELUANG DISKRIT
Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya. Kombinatorial dapat digunakan untuk menjawab soal semacam ini tanpa kita perlu mengenumerai semua kemungkinan jawabannya. Hal ini dapat dilakukan karena didalam kombinatorial terdapat kaidah dasar menghitung. Dan kombinator digunakan pada teori peluang diskrit untuk menghitung peluang suatu kejadian terjadi.
A. Percobaan
Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan. Percobaan adala proses fisik yang hasilnya dapat diamati
Contoh :
1. Melempar dadu
Enam hasil percobaan yang mungkin untuk pelemparan dadu adalah muka dadu 1,2,3,4,5 atau 6
2. Melempar koin uang Rp 100
Hasil percobaan melempar koin 100 ada dua kemungkinan maka koin bergambar rumah gadang atau muka koin yang bergambar wayang.
B. Kaidah Dasar Menghitung
Dua kaidah dasar yang digunakan sebagai teknik menghitung dalam kombinatrorial adalah kaidah perkalian (rule of product) dan kaidah penjumlahan (rule of sum).
- Kaidah Perkalian (rule of product)
Percobaan 1: p hasil
Percobaan 2: q hasil maka,
Percobaan 1 dan percobaan 2: p q hasil
- Kaidah Penjumlahan (rule of sum)
Percobaan 1: p hasil
Percobaan 2: q hasil maka,
Percobaan 1 atau percobaan 2: p + q hasil
C. Perluasan Kaidah Menghitung
Kaidah perkalian dan penjumlahan diatas dapat diperluas sehingga mengandung lebih dari dua buah percobaan. Jika n buah percobaan masing-masing mempunyai p1, p2, …,pn, hasil percobaan yang mungkin terjadi dalam hal ini setiap p1 tidak bergantung pada pilihan sebelumnya, maka jumlah hasil percobaan yang mungkin terjadi adalah :
a. P1 x p2 x … x pn untuk kaidah perkalian.
b. P1 + p2 + … + pn untuk kaidah penjumlahan.
D. Prinsip Inklusi-Eksklusi
Informasi terkecil yang dapat disimpan di dalam memori computer adalah byte. Setiap byte disusun oleh 8 bit.
Example :
1. Setiap byte disusun oleh 8-bit. Berapa banyak jumlah byte yang dimulai dengan ‘11’ atau berakhir dengan ‘11’?
Answer :
Misalkan
A = himpunan byte yang dimulai dengan ‘11’,
B = himpunan byte yang diakhiri dengan ‘11’
A B = himpunan byte yang berawal dan berakhir dengan ‘11’
maka
A B = himpunan byte yang berawal dengan ‘11’ atau berakhir dengan ‘11’
A = 26 = 64,
B = 26 = 64,
A B = 24 = 16.
maka
A B = A + B – A B
= 26 + 26 – 16 = 64 + 64 – 16 = 112.
E. Permutasi
Permutasi adalah jumlah urutan yang berbeda dari pengaturan objek-objek. Juga merupakan bentuk khusus aplikasi dari n objek, urutan kedua dipilih dari n-1 objek, urutan ketiga dipilih dari n-2 objek, begitu seterusnya, dan urutan terakhir dipilih dari 1 objek yang tersisa. Menurut kaidah perkalian permutasi dari n objek adalah
N(n-1) (n-2) … (2)(1) = n!
Example :
Berapa banyak “kata” yang terbentuk dari kata “HAPUS”?
Answer :
Cara 1: (5)(4)(3)(2)(1) = 120 buah kata
Cara 2: P(5, 5) = 5! = 120 buah kata
Berapa banyak cara mengurutkan nama 25 orang mahasiswa?
Answer : P(25, 25) = 25!
Ada juga yang dikatakan permutasi melingkar. Yaitu penyusunan objek-objek yang megelilingi sebuah lingkaran (atau kurva tertutup sederhana). Jumlah susunan objek yang mengelilingi lingkaran adalah (n-1)!.
F. Kombinasi
Bentuk khusus permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan urutan acb, bca, acb dianggap sama dan dihitung sekali.
Example :
1. Misalkan ada 2 buah bola yang warnanya sama dan ada 3 buah kotak. Setiap kotak hanya boleh berisi paling banyak 1 bola.
Jumlah cara memasukkan bola ke dalam kotak :
2. Bila sekarang jumlah bola 3 dan jumlah kotak 10, maka jumlah cara memasukkan bola ke dalam kotak adalah
karena ada 3! cara memasukkan bola yang warnanya sama.
Kombinasi r elemen dari n elemen, atau C(n, r), adalah jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen.
Example from Interpretasi Kombinasi :
1. C(n, r) = banyaknya himpunan bagian yang terdiri dari r elemen yang dapat dibentuk dari himpunan dengan n elemen.
Misalkan A = {1, 2, 3}
Jumlah Himpunan bagian dengan 2 elemen:
{1, 2} = {2, 1}
{1, 3} = {3, 1} 3 buah atau
{2, 3} = {3, 2}
G. Permutasi dan Kombinasi Bentuk Umum
Misalkan: ada n buah bola yang tidak seluruhnya berbeda warna (jadi, ada beberapa bola yang warnanya sama - indistinguishable). n1 bola diantaranya berwarna 1, n2 bola diantaranya berwarna 2, nk bola diantaranya berwarna k, dan n1 + n2 + … + nk = n.
Berapa jumlah cara pengaturan n buah bola ke dalam kotak-kotak tersebut (tiap kotak maks. 1 buah bola)?
Answer :
Jika n buah bola itu kita anggap berbeda semuanya, maka jumlah cara pengaturan nbuah bola ke dalam n buah kotak adalah
P(n, n) = n!.
Dari pengaturan n buah bola itu,
- ada n1! cara memasukkan bola berwarna 1
- ada n2! cara memasukkan bola berwarna 2
- ada nk! cara memasukkan bola berwarna k
Permutasi n buah bola yang mana n1 diantaranya berwarna 1, n2 bola berwarna 2, …,nk bola berwarna k adalah:
Dengan cara lain :
- Ada C(n, n1) cara untuk menempatkan n1 buah bola yang berwarna 1.
- Ada C(n – n1, n2) cara untuk menempatkan n2 buah bola berwarna 2.
- Ada C(n – n1 – n2, n3) cara untuk menempatkan n3 buah bola berwarna 3.
- Ada C(n – n1 – n2 – … – nk-1, nk ) cara untuk menempatkan nk buah bola berwarna k.
H. Kombinasi dengan Pengulangan.
Tinjau kembali persoalan memasukkan bola ke dalam kotak. Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.
Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.
i. Jika masing-masing kotak hanya boleh diisi paling banyak satu buah bola, maka jumlah cara memasukkannya boal kedalam kotak adalah C(n,r).
ii. Jika masing-masing kotak boleh lebih dari satu buah bola (tidak ada pembatasan jumlah bola), maka jumlah cara memasukkan bola kedalam kotak adalah C(n+r-1,r)
Contoh :
Pada persamaan x1 +x2+x3+x4=12, xi adalah bilangan bulat ≥0 . Berapa jumla kemungkinan solusinya?
Penyelesaian:
Analogikan 12 buah bola akan dimasukkan kedalam 4 kotak, maka:
- Kotak 1 diisi 3 buah bola (x1=3)
- Kotak 2 diisi 5 buah bola (x2=5)
- Kotak 3 diisi 2 buah bola (x3=2)
- Kotak 4 diisi 2 buah bola (x4=2)
sehingga, x1 +x2+x3+x4=3+5+2+2=12
I. Koefisien Binomial
1. x+y0=1
2. x+y1=x+y
3. x+y2=x2+2xy+y2
4. x+y3=x3+3x2y+3xy2+y3
5. x+y4=x3+4x3y+6x2y2+4xy3+y4
6. x+y5=x5+5x4y+10x3y2+10x2y3+5xy4+y5
Aturan untuk menjabarkan bentuk perpangkatan x+yn adalah
• Suku pertama xn, sedangkan suku terakhir adalah yn
• Pada setiap suku berikutnya, pangkat x berkurang satu sedangkan pangkat y bertambah satu. Untuk setiap suku, jumlah pangkat x dan y adalah n.
• Koefisien untuk xn-kyk, yaitu suku ke- (k+1) adalah C(n,k). Bilangan C(n,k) disebut koefisien binomial.
Aturan di atas dapat di simpulkan bahwa:
x+yn=Cn,oxn+Cn,1xn-1y1+…+Cn,kxn-kyk+…+Cn,nyn
= k=0nC(n,k)xn-kyk
J. Prinsip Sarang Merpati
Jika n+1 atau lebih objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi dua atau lebih objek.
Prinsip sarang merpati dikemukakan oleh G.Lejeune Dirichlet,seorang matematikawan Jerman, sehingga kadang-kadang dinamakan juga prinsip kotak Dirichlet, karena Dirichlet sering menggunakan prinsip ini dalam pekerjaannya.
example :
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 kedalam kotak) untuk menjamin bahwa sepasang bola yang berwarna sama terambil?
answer:
Jika setiap warna dianggap sebagai sarang merpati, maka n=3 karena itu orang mengambil paling sedikit n+1=4 bola (merpati),maka dapat dipastikan sepasang bola yang berwarna sama ikut terambil.Jika hanya diambil 3 buah, maka ada kemungkinan ketiga bola itu berbeda warna satu sama lain.jadi, 4 buah bola adalah jumlah minimum yang harus diambil dari dalam kotak untuk menjamin terambil sepasang bola yang berwarna sama.
K. Peluang Diskrit
Peluang diskrit mempunyai sifat sebagai berikut:
a. 0≤p(xi)≤1, yaitu peluang adalah bilangan tidak negatif dan selalu lebih kecil atau sama dengan 1.
b. i=1|S|p(xi)=1 , yaitu jumlah peluang semua titik contoh di dalam ruang contoh S adalah 1.
Contoh:
Pada pelemparan dadu, S={1,2,3,4,5,6}. Peluang munculnya setiap angka adalah sama yaitu 1/6.
Kejadian (event)→ disimbolkan dengan E- adalah himpunan bagian dari ruang. Peluang kejadian E di dalam ruang contoh S adalah P(E)=|E|/|S|. Peluang kejadian E juga diartikan sebagai jumlah peluang semua titik contoh di dalam E. Jadi, kita dapat menuliskan bahwa:
PE=|E||S|=xi∈Ep(xi)
Konsep-konsep pada teori himpunan:
• P A∩B=xi∈A∩Bp(xi)
• P A∪B=xi∈A∪Bp(xi)
• P A-B=xi∈A-Bp(xi)
• P A⨁B=xi∈A⨁Bp(xi)
• P(A)=1-P(A)
Kamis, 12 April 2018
MATEMATIKA DISKRIT
KOMBINATORIAL dan PELUANG DISKRIT
Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya. Kombinatorial dapat digunakan untuk menjawab soal semacam ini tanpa kita perlu mengenumerai semua kemungkinan jawabannya. Hal ini dapat dilakukan karena didalam kombinatorial terdapat kaidah dasar menghitung. Dan kombinator digunakan pada teori peluang diskrit untuk menghitung peluang suatu kejadian terjadi.
A. Percobaan
Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan. Percobaan adala proses fisik yang hasilnya dapat diamati
Contoh :
1. Melempar dadu
Enam hasil percobaan yang mungkin untuk pelemparan dadu adalah muka dadu 1,2,3,4,5 atau 6
2. Melempar koin uang Rp 100
Hasil percobaan melempar koin 100 ada dua kemungkinan maka koin bergambar rumah gadang atau muka koin yang bergambar wayang.
B. Kaidah Dasar Menghitung
Dua kaidah dasar yang digunakan sebagai teknik menghitung dalam kombinatrorial adalah kaidah perkalian (rule of product) dan kaidah penjumlahan (rule of sum).
- Kaidah Perkalian (rule of product)
Percobaan 1: p hasil
Percobaan 2: q hasil maka,
Percobaan 1 dan percobaan 2: p q hasil
- Kaidah Penjumlahan (rule of sum)
Percobaan 1: p hasil
Percobaan 2: q hasil maka,
Percobaan 1 atau percobaan 2: p + q hasil
C. Perluasan Kaidah Menghitung
Kaidah perkalian dan penjumlahan diatas dapat diperluas sehingga mengandung lebih dari dua buah percobaan. Jika n buah percobaan masing-masing mempunyai p1, p2, …,pn, hasil percobaan yang mungkin terjadi dalam hal ini setiap p1 tidak bergantung pada pilihan sebelumnya, maka jumlah hasil percobaan yang mungkin terjadi adalah :
a. P1 x p2 x … x pn untuk kaidah perkalian.
b. P1 + p2 + … + pn untuk kaidah penjumlahan.
D. Prinsip Inklusi-Eksklusi
Informasi terkecil yang dapat disimpan di dalam memori computer adalah byte. Setiap byte disusun oleh 8 bit.
Example :
1. Setiap byte disusun oleh 8-bit. Berapa banyak jumlah byte yang dimulai dengan ‘11’ atau berakhir dengan ‘11’?
Answer :
Misalkan
A = himpunan byte yang dimulai dengan ‘11’,
B = himpunan byte yang diakhiri dengan ‘11’
A B = himpunan byte yang berawal dan berakhir dengan ‘11’
maka
A B = himpunan byte yang berawal dengan ‘11’ atau berakhir dengan ‘11’
A = 26 = 64,
B = 26 = 64,
A B = 24 = 16.
maka
A B = A + B – A B
= 26 + 26 – 16 = 64 + 64 – 16 = 112.
E. Permutasi
Permutasi adalah jumlah urutan yang berbeda dari pengaturan objek-objek. Juga merupakan bentuk khusus aplikasi dari n objek, urutan kedua dipilih dari n-1 objek, urutan ketiga dipilih dari n-2 objek, begitu seterusnya, dan urutan terakhir dipilih dari 1 objek yang tersisa. Menurut kaidah perkalian permutasi dari n objek adalah
N(n-1) (n-2) … (2)(1) = n!
Example :
Berapa banyak “kata” yang terbentuk dari kata “HAPUS”?
Answer :
Cara 1: (5)(4)(3)(2)(1) = 120 buah kata
Cara 2: P(5, 5) = 5! = 120 buah kata
Berapa banyak cara mengurutkan nama 25 orang mahasiswa?
Answer : P(25, 25) = 25!
Ada juga yang dikatakan permutasi melingkar. Yaitu penyusunan objek-objek yang megelilingi sebuah lingkaran (atau kurva tertutup sederhana). Jumlah susunan objek yang mengelilingi lingkaran adalah (n-1)!.
F. Kombinasi
Bentuk khusus permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan urutan acb, bca, acb dianggap sama dan dihitung sekali.
Example :
1. Misalkan ada 2 buah bola yang warnanya sama dan ada 3 buah kotak. Setiap kotak hanya boleh berisi paling banyak 1 bola.
Jumlah cara memasukkan bola ke dalam kotak :
2. Bila sekarang jumlah bola 3 dan jumlah kotak 10, maka jumlah cara memasukkan bola ke dalam kotak adalah
karena ada 3! cara memasukkan bola yang warnanya sama.
Kombinasi r elemen dari n elemen, atau C(n, r), adalah jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen.
Example from Interpretasi Kombinasi :
1. C(n, r) = banyaknya himpunan bagian yang terdiri dari r elemen yang dapat dibentuk dari himpunan dengan n elemen.
Misalkan A = {1, 2, 3}
Jumlah Himpunan bagian dengan 2 elemen:
{1, 2} = {2, 1}
{1, 3} = {3, 1} 3 buah atau
{2, 3} = {3, 2}
G. Permutasi dan Kombinasi Bentuk Umum
Misalkan: ada n buah bola yang tidak seluruhnya berbeda warna (jadi, ada beberapa bola yang warnanya sama - indistinguishable). n1 bola diantaranya berwarna 1, n2 bola diantaranya berwarna 2, nk bola diantaranya berwarna k, dan n1 + n2 + … + nk = n.
Berapa jumlah cara pengaturan n buah bola ke dalam kotak-kotak tersebut (tiap kotak maks. 1 buah bola)?
Answer :
Jika n buah bola itu kita anggap berbeda semuanya, maka jumlah cara pengaturan nbuah bola ke dalam n buah kotak adalah
P(n, n) = n!.
Dari pengaturan n buah bola itu,
- ada n1! cara memasukkan bola berwarna 1
- ada n2! cara memasukkan bola berwarna 2
- ada nk! cara memasukkan bola berwarna k
Permutasi n buah bola yang mana n1 diantaranya berwarna 1, n2 bola berwarna 2, …,nk bola berwarna k adalah:
Dengan cara lain :
- Ada C(n, n1) cara untuk menempatkan n1 buah bola yang berwarna 1.
- Ada C(n – n1, n2) cara untuk menempatkan n2 buah bola berwarna 2.
- Ada C(n – n1 – n2, n3) cara untuk menempatkan n3 buah bola berwarna 3.
- Ada C(n – n1 – n2 – … – nk-1, nk ) cara untuk menempatkan nk buah bola berwarna k.
H. Kombinasi dengan Pengulangan.
Tinjau kembali persoalan memasukkan bola ke dalam kotak. Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.
Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.
i. Jika masing-masing kotak hanya boleh diisi paling banyak satu buah bola, maka jumlah cara memasukkannya boal kedalam kotak adalah C(n,r).
ii. Jika masing-masing kotak boleh lebih dari satu buah bola (tidak ada pembatasan jumlah bola), maka jumlah cara memasukkan bola kedalam kotak adalah C(n+r-1,r)
Contoh :
Pada persamaan x1 +x2+x3+x4=12, xi adalah bilangan bulat ≥0 . Berapa jumla kemungkinan solusinya?
Penyelesaian:
Analogikan 12 buah bola akan dimasukkan kedalam 4 kotak, maka:
- Kotak 1 diisi 3 buah bola (x1=3)
- Kotak 2 diisi 5 buah bola (x2=5)
- Kotak 3 diisi 2 buah bola (x3=2)
- Kotak 4 diisi 2 buah bola (x4=2)
sehingga, x1 +x2+x3+x4=3+5+2+2=12
I. Koefisien Binomial
1. x+y0=1
2. x+y1=x+y
3. x+y2=x2+2xy+y2
4. x+y3=x3+3x2y+3xy2+y3
5. x+y4=x3+4x3y+6x2y2+4xy3+y4
6. x+y5=x5+5x4y+10x3y2+10x2y3+5xy4+y5
Aturan untuk menjabarkan bentuk perpangkatan x+yn adalah
• Suku pertama xn, sedangkan suku terakhir adalah yn
• Pada setiap suku berikutnya, pangkat x berkurang satu sedangkan pangkat y bertambah satu. Untuk setiap suku, jumlah pangkat x dan y adalah n.
• Koefisien untuk xn-kyk, yaitu suku ke- (k+1) adalah C(n,k). Bilangan C(n,k) disebut koefisien binomial.
Aturan di atas dapat di simpulkan bahwa:
x+yn=Cn,oxn+Cn,1xn-1y1+…+Cn,kxn-kyk+…+Cn,nyn
= k=0nC(n,k)xn-kyk
J. Prinsip Sarang Merpati
Jika n+1 atau lebih objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi dua atau lebih objek.
Prinsip sarang merpati dikemukakan oleh G.Lejeune Dirichlet,seorang matematikawan Jerman, sehingga kadang-kadang dinamakan juga prinsip kotak Dirichlet, karena Dirichlet sering menggunakan prinsip ini dalam pekerjaannya.
example :
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 kedalam kotak) untuk menjamin bahwa sepasang bola yang berwarna sama terambil?
answer:
Jika setiap warna dianggap sebagai sarang merpati, maka n=3 karena itu orang mengambil paling sedikit n+1=4 bola (merpati),maka dapat dipastikan sepasang bola yang berwarna sama ikut terambil.Jika hanya diambil 3 buah, maka ada kemungkinan ketiga bola itu berbeda warna satu sama lain.jadi, 4 buah bola adalah jumlah minimum yang harus diambil dari dalam kotak untuk menjamin terambil sepasang bola yang berwarna sama.
K. Peluang Diskrit
Peluang diskrit mempunyai sifat sebagai berikut:
a. 0≤p(xi)≤1, yaitu peluang adalah bilangan tidak negatif dan selalu lebih kecil atau sama dengan 1.
b. i=1|S|p(xi)=1 , yaitu jumlah peluang semua titik contoh di dalam ruang contoh S adalah 1.
Contoh:
Pada pelemparan dadu, S={1,2,3,4,5,6}. Peluang munculnya setiap angka adalah sama yaitu 1/6.
Kejadian (event)→ disimbolkan dengan E- adalah himpunan bagian dari ruang. Peluang kejadian E di dalam ruang contoh S adalah P(E)=|E|/|S|. Peluang kejadian E juga diartikan sebagai jumlah peluang semua titik contoh di dalam E. Jadi, kita dapat menuliskan bahwa:
PE=|E||S|=xi∈Ep(xi)
Konsep-konsep pada teori himpunan:
• P A∩B=xi∈A∩Bp(xi)
• P A∪B=xi∈A∪Bp(xi)
• P A-B=xi∈A-Bp(xi)
• P A⨁B=xi∈A⨁Bp(xi)
• P(A)=1-P(A)
KOMBINATORIAL dan PELUANG DISKRIT
Kombinatorial adalah cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya. Kombinatorial dapat digunakan untuk menjawab soal semacam ini tanpa kita perlu mengenumerai semua kemungkinan jawabannya. Hal ini dapat dilakukan karena didalam kombinatorial terdapat kaidah dasar menghitung. Dan kombinator digunakan pada teori peluang diskrit untuk menghitung peluang suatu kejadian terjadi.
A. Percobaan
Kombinatorial didasarkan pada hasil yang diperoleh dari suatu percobaan. Percobaan adala proses fisik yang hasilnya dapat diamati
Contoh :
1. Melempar dadu
Enam hasil percobaan yang mungkin untuk pelemparan dadu adalah muka dadu 1,2,3,4,5 atau 6
2. Melempar koin uang Rp 100
Hasil percobaan melempar koin 100 ada dua kemungkinan maka koin bergambar rumah gadang atau muka koin yang bergambar wayang.
B. Kaidah Dasar Menghitung
Dua kaidah dasar yang digunakan sebagai teknik menghitung dalam kombinatrorial adalah kaidah perkalian (rule of product) dan kaidah penjumlahan (rule of sum).
- Kaidah Perkalian (rule of product)
Percobaan 1: p hasil
Percobaan 2: q hasil maka,
Percobaan 1 dan percobaan 2: p q hasil
- Kaidah Penjumlahan (rule of sum)
Percobaan 1: p hasil
Percobaan 2: q hasil maka,
Percobaan 1 atau percobaan 2: p + q hasil
C. Perluasan Kaidah Menghitung
Kaidah perkalian dan penjumlahan diatas dapat diperluas sehingga mengandung lebih dari dua buah percobaan. Jika n buah percobaan masing-masing mempunyai p1, p2, …,pn, hasil percobaan yang mungkin terjadi dalam hal ini setiap p1 tidak bergantung pada pilihan sebelumnya, maka jumlah hasil percobaan yang mungkin terjadi adalah :
a. P1 x p2 x … x pn untuk kaidah perkalian.
b. P1 + p2 + … + pn untuk kaidah penjumlahan.
D. Prinsip Inklusi-Eksklusi
Informasi terkecil yang dapat disimpan di dalam memori computer adalah byte. Setiap byte disusun oleh 8 bit.
Example :
1. Setiap byte disusun oleh 8-bit. Berapa banyak jumlah byte yang dimulai dengan ‘11’ atau berakhir dengan ‘11’?
Answer :
Misalkan
A = himpunan byte yang dimulai dengan ‘11’,
B = himpunan byte yang diakhiri dengan ‘11’
A B = himpunan byte yang berawal dan berakhir dengan ‘11’
maka
A B = himpunan byte yang berawal dengan ‘11’ atau berakhir dengan ‘11’
A = 26 = 64,
B = 26 = 64,
A B = 24 = 16.
maka
A B = A + B – A B
= 26 + 26 – 16 = 64 + 64 – 16 = 112.
E. Permutasi
Permutasi adalah jumlah urutan yang berbeda dari pengaturan objek-objek. Juga merupakan bentuk khusus aplikasi dari n objek, urutan kedua dipilih dari n-1 objek, urutan ketiga dipilih dari n-2 objek, begitu seterusnya, dan urutan terakhir dipilih dari 1 objek yang tersisa. Menurut kaidah perkalian permutasi dari n objek adalah
N(n-1) (n-2) … (2)(1) = n!
Example :
Berapa banyak “kata” yang terbentuk dari kata “HAPUS”?
Answer :
Cara 1: (5)(4)(3)(2)(1) = 120 buah kata
Cara 2: P(5, 5) = 5! = 120 buah kata
Berapa banyak cara mengurutkan nama 25 orang mahasiswa?
Answer : P(25, 25) = 25!
Ada juga yang dikatakan permutasi melingkar. Yaitu penyusunan objek-objek yang megelilingi sebuah lingkaran (atau kurva tertutup sederhana). Jumlah susunan objek yang mengelilingi lingkaran adalah (n-1)!.
F. Kombinasi
Bentuk khusus permutasi adalah kombinasi. Jika pada permutasi urutan kemunculan diperhitungkan, maka pada kombinasi, urutan kemunculan diabaikan urutan acb, bca, acb dianggap sama dan dihitung sekali.
Example :
1. Misalkan ada 2 buah bola yang warnanya sama dan ada 3 buah kotak. Setiap kotak hanya boleh berisi paling banyak 1 bola.
Jumlah cara memasukkan bola ke dalam kotak :
2. Bila sekarang jumlah bola 3 dan jumlah kotak 10, maka jumlah cara memasukkan bola ke dalam kotak adalah
karena ada 3! cara memasukkan bola yang warnanya sama.
Kombinasi r elemen dari n elemen, atau C(n, r), adalah jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen.
Example from Interpretasi Kombinasi :
1. C(n, r) = banyaknya himpunan bagian yang terdiri dari r elemen yang dapat dibentuk dari himpunan dengan n elemen.
Misalkan A = {1, 2, 3}
Jumlah Himpunan bagian dengan 2 elemen:
{1, 2} = {2, 1}
{1, 3} = {3, 1} 3 buah atau
{2, 3} = {3, 2}
G. Permutasi dan Kombinasi Bentuk Umum
Misalkan: ada n buah bola yang tidak seluruhnya berbeda warna (jadi, ada beberapa bola yang warnanya sama - indistinguishable). n1 bola diantaranya berwarna 1, n2 bola diantaranya berwarna 2, nk bola diantaranya berwarna k, dan n1 + n2 + … + nk = n.
Berapa jumlah cara pengaturan n buah bola ke dalam kotak-kotak tersebut (tiap kotak maks. 1 buah bola)?
Answer :
Jika n buah bola itu kita anggap berbeda semuanya, maka jumlah cara pengaturan nbuah bola ke dalam n buah kotak adalah
P(n, n) = n!.
Dari pengaturan n buah bola itu,
- ada n1! cara memasukkan bola berwarna 1
- ada n2! cara memasukkan bola berwarna 2
- ada nk! cara memasukkan bola berwarna k
Permutasi n buah bola yang mana n1 diantaranya berwarna 1, n2 bola berwarna 2, …,nk bola berwarna k adalah:
Dengan cara lain :
- Ada C(n, n1) cara untuk menempatkan n1 buah bola yang berwarna 1.
- Ada C(n – n1, n2) cara untuk menempatkan n2 buah bola berwarna 2.
- Ada C(n – n1 – n2, n3) cara untuk menempatkan n3 buah bola berwarna 3.
- Ada C(n – n1 – n2 – … – nk-1, nk ) cara untuk menempatkan nk buah bola berwarna k.
H. Kombinasi dengan Pengulangan.
Tinjau kembali persoalan memasukkan bola ke dalam kotak. Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.
Misalkan terdapat r buah bola yang semua warnanya sama dan n buah kotak.
i. Jika masing-masing kotak hanya boleh diisi paling banyak satu buah bola, maka jumlah cara memasukkannya boal kedalam kotak adalah C(n,r).
ii. Jika masing-masing kotak boleh lebih dari satu buah bola (tidak ada pembatasan jumlah bola), maka jumlah cara memasukkan bola kedalam kotak adalah C(n+r-1,r)
Contoh :
Pada persamaan x1 +x2+x3+x4=12, xi adalah bilangan bulat ≥0 . Berapa jumla kemungkinan solusinya?
Penyelesaian:
Analogikan 12 buah bola akan dimasukkan kedalam 4 kotak, maka:
- Kotak 1 diisi 3 buah bola (x1=3)
- Kotak 2 diisi 5 buah bola (x2=5)
- Kotak 3 diisi 2 buah bola (x3=2)
- Kotak 4 diisi 2 buah bola (x4=2)
sehingga, x1 +x2+x3+x4=3+5+2+2=12
I. Koefisien Binomial
1. x+y0=1
2. x+y1=x+y
3. x+y2=x2+2xy+y2
4. x+y3=x3+3x2y+3xy2+y3
5. x+y4=x3+4x3y+6x2y2+4xy3+y4
6. x+y5=x5+5x4y+10x3y2+10x2y3+5xy4+y5
Aturan untuk menjabarkan bentuk perpangkatan x+yn adalah
• Suku pertama xn, sedangkan suku terakhir adalah yn
• Pada setiap suku berikutnya, pangkat x berkurang satu sedangkan pangkat y bertambah satu. Untuk setiap suku, jumlah pangkat x dan y adalah n.
• Koefisien untuk xn-kyk, yaitu suku ke- (k+1) adalah C(n,k). Bilangan C(n,k) disebut koefisien binomial.
Aturan di atas dapat di simpulkan bahwa:
x+yn=Cn,oxn+Cn,1xn-1y1+…+Cn,kxn-kyk+…+Cn,nyn
= k=0nC(n,k)xn-kyk
J. Prinsip Sarang Merpati
Jika n+1 atau lebih objek ditempatkan di dalam n buah kotak, maka paling sedikit terdapat satu kotak yang berisi dua atau lebih objek.
Prinsip sarang merpati dikemukakan oleh G.Lejeune Dirichlet,seorang matematikawan Jerman, sehingga kadang-kadang dinamakan juga prinsip kotak Dirichlet, karena Dirichlet sering menggunakan prinsip ini dalam pekerjaannya.
example :
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 kedalam kotak) untuk menjamin bahwa sepasang bola yang berwarna sama terambil?
answer:
Jika setiap warna dianggap sebagai sarang merpati, maka n=3 karena itu orang mengambil paling sedikit n+1=4 bola (merpati),maka dapat dipastikan sepasang bola yang berwarna sama ikut terambil.Jika hanya diambil 3 buah, maka ada kemungkinan ketiga bola itu berbeda warna satu sama lain.jadi, 4 buah bola adalah jumlah minimum yang harus diambil dari dalam kotak untuk menjamin terambil sepasang bola yang berwarna sama.
K. Peluang Diskrit
Peluang diskrit mempunyai sifat sebagai berikut:
a. 0≤p(xi)≤1, yaitu peluang adalah bilangan tidak negatif dan selalu lebih kecil atau sama dengan 1.
b. i=1|S|p(xi)=1 , yaitu jumlah peluang semua titik contoh di dalam ruang contoh S adalah 1.
Contoh:
Pada pelemparan dadu, S={1,2,3,4,5,6}. Peluang munculnya setiap angka adalah sama yaitu 1/6.
Kejadian (event)→ disimbolkan dengan E- adalah himpunan bagian dari ruang. Peluang kejadian E di dalam ruang contoh S adalah P(E)=|E|/|S|. Peluang kejadian E juga diartikan sebagai jumlah peluang semua titik contoh di dalam E. Jadi, kita dapat menuliskan bahwa:
PE=|E||S|=xi∈Ep(xi)
Konsep-konsep pada teori himpunan:
• P A∩B=xi∈A∩Bp(xi)
• P A∪B=xi∈A∪Bp(xi)
• P A-B=xi∈A-Bp(xi)
• P A⨁B=xi∈A⨁Bp(xi)
• P(A)=1-P(A)
Kamis, 05 April 2018
Matematika Diskrtit
INDUKSI
Induksi matematika (mathematical induction) adalah metode pembuktian yang sering digunakan untuk menentukan kebenaran dari suatu pernyataan yang diberikan dalam bentuk bilangan asli. Akan tetapi sebelum membahas mengenai induksi matematika, kita akan membahas suatu prinsip yang digunakan untuk membuktikan induksi matematika, yaitu prinsip terurut rapi (well-ordering principle) dari bilangan asli. Seperti kita ketahui, himpunan bilangan asli adalah himpunan yang memiliki anggota 1, 2, 3, … yang dapat dituliskan sebagai berikut.
Setelah mengingat mengenai himpunan bilangan asli, sekarang perhatikan prinsip terurut rapi dari bilangan asli berikut.
Prinsip Terurut Rapi Bilangan Asli
Setiap himpunan bagian yang tidak kosong dari N memiliki anggota terkecil.
Secara lebih formal, prinsip tersebut menyatakan bahwa untuk setiap himpunan tidak kosong V yang merupakan himpunan bagian dari N, maka ada v0 anggota V sedemikian sehingga v0 ≤ v untuk setiap v anggota V.
Berdasarkan prinsip terurut rapi di atas, kita akan menurunkan prinsip induksi matematika yang dinyatakan dalam bentuk himpunan bagian N.
Prinsip Induksi Matematika
Misalkan S adalah himpunan bagian N yang memiliki 2 sifat:
(1) S memiliki anggota bilangan 1; dan
(2) Untuk setiap k anggota N, jika k anggota S, maka k + 1 anggota S.
Maka diperoleh S = N.
Sebelum membuktikan prinsip induksi matematika di atas secara formal, kita akan mencoba memahaminya dengan menggunakan efek domino seperti berikut.
Pada gambar (a) di atas kita melihat sebaris 4 domino pertama yang ditata rapi dengan jarak antara masing-masing domino yang berdekatan kurang dari tinggi domino. Sehingga, jika kita mendorong domino nomor k ke kanan, maka domino tersebut akan merebahkan domino nomor (k + 1). Proses ini ditunjukkan oleh gambar (b). Kita tentu akan berpikir bahwa apabila proses ini berlanjut, maka domino nomor (k + 1) tersebut juga akan merebahkan domino di sebelah kanannya, yaitu domino nomor (k + 2), dan seterusnya. Bagian (c) menggambarkan bahwa dorongan terhadap domino pertama merupakan analogi dari bilangan 1 menjadi anggota himpunan S. Hal ini merupakan langkah dasar dari proses efek domino. Selanjutnya, jika k anggota S akan menyebabkan (k + 1) anggota S, akan memberikan langkah induktif dan melanjutkan proses perebahan domino. Sehingga, pada akhirnya kita akan melihat bahwa semua domino akan rebah. Atau dengan kata lain, domino yang memiliki nomor urut semua bilangan asli akan rebah. Hal ini merupakan analogi dari S = N. Bagaimana dengan bukti formal dari prinsip induksi matematika?
Bukti Andaikan S ≠ N. Maka himpunan N – S bukan merupakan himpunan kosong, sehingga berdasarkan prinsip terurut rapi, himpunan tersebut memiliki anggota terkecil m. Karena 1 anggota S (berdasarkan hipotesis 1), maka m > 1. Tetapi hal ini akan mengakibatkan bahwa m – 1 juga merupakan bilangan asli. Karena m – 1 < m dan madalah anggota terkecil dari N – S, maka m – 1 anggota S.
Sekarang kita akan menggunakan hipotesis 2 bahwa k = m – 1 merupakan anggota S, maka k + 1 = (m – 1) + 1 = m juga anggota S. Akan tetapi pernyataan ini akan kontradiksi bahwa m bukan anggota S. Sehingga N – S adalah himpunan kosong atau dengan kata lain N = S.
Selain diformulasikan seperti di atas, Prinsip Induksi Matematika juga dapat dinyatakan sebagai berikut.
Untuk setiap n anggota N, misalkan P(n) merupakan suatu pernyataan tentang n. Apabila:
1. P(1) benar.
2. Untuk setiap k anggota N, jika P(k) benar, maka P(k + 1) benar.
Maka P(n) benar untuk setiap n anggota N.
Hubungan Prinsip Induksi Matematika tersebut dengan sebelumnya adalah dengan memisalkan S = {n anggota N | P(n) adalah benar}. Sehingga kondisi 1 dan 2 pada Prinsip Induksi Matematika di awal secara berturut-turut berkorespondensi dengan kondisi 1 dan 2 pada Prinsip Induksi Matematika terakhir. Selain itu, kesimpulan S = N juga berkorespondensi dengan kesimpulan P(n) benar untuk setiap n anggota N.
Asumsi bahwa “jika P(k) benar” dinamakan hipotesis induksi. Untuk membangun hipostesis 2, kita tidak perlu menghiraukan kebenaran dari P(k), tetapi yang perlu kita hiraukan adalah validitas dari “jika P(k), maka P(k + 1)”. Misalkan, jika kita akan menguji pernyataan P(n): “n = n + 5”, maka secara logis kondisi (2) adalah benar, dengan menambahkan 1 pada kedua sisi P(k) untuk mendapatkan P(k + 1). Akan tetapi, karena pernyataan P(1): “1 = 6” adalah salah, kita tidak dapat menggunakan Induksi Matematika untuk menyimpulkan bahwa n = n + 5 untuk setiap n anggota N.
Pada beberapa kasus, kadang P(n) bernilai salah untuk beberapa bilangan asli tertentu tetapi bernilai benar untuk n ≥ n0. Prinsip Induksi Matematika dapat dimodifikasi untuk mengatasi kasus seperti itu.
Prinsip Induksi Matematika (versi kedua)
Misalkan n0 anggota N dan misalkan P(n) merupakan pernyataan untuk setiap bilangan asli n ≥ n0. Apabila:
(1) Pernyataan P(n0) benar;
(2) Untuk setiap k ≥ n0, jika P(k) benar mengakibatkan P(k + 1) benar.
Maka P(n) benar untuk semua n ≥ n0.
Berikut ini adalah beberapa contoh yang menunjukkan bagaimana Induksi Matematika dapat digunakan untuk membuktikan pernyataan tentang bilangan asli.
Contoh 1: Pengubinan dengan Tromino
Diberikan suatu papan catur 2n × 2n (n > 0), dengan salah satu persegi di bagian pojok dihilangkan, buktikan bahwa papan catur tersebut dapat ditutup sempurna dengan tromino. (Tromino adalah gambar yang terdiri dari 3 persegi yang sisinya saling bersinggungan, tetapi 3 persegi tersebut tidak dalam satu barisan yang berjajar)
Bukti Pernyataan tersebut benar untuk n = 1 karena secara jelas papan catur 21 × 21 yang salah satu persegi bagian pojok dihilangkan memiliki bentuk yang sama dengan tromino. Andaikan pernyataan tersebut benar untuk k anggota N. Diberikan papan catur dengan ukuran 2k + 1 × 2k + 1 yang salah satu persegi di bagian pojok dihilangkan. Bagilah papan catur tersebut menjadi 4 papan catur 2k × 2k A, B, C, dan D, dengan satu di antaranya, yaitu A, memiliki bagian yang salah satu persegi di pojok hilang. Tempatkan 1 tromino, T, di tengah-tengah papan catur 2k + 1 × 2k + 1 sedemikian sehingga persegi-persegi tromino tersebut berada di bagian B, C, dan D. Kemudian gunakan kasus n = k untuk menutup bagian A, B – T, C – T, dan D – T dengan tromino. Proses tersebut akan menutup papan catur 2k + 1 × 2k + 1 tepat sempurna dengan tromino-tromino. (Gambar di bawah ini mengilustrasikan untuk kasus n = 3).
Contoh 2: Jumlah n Bilangan Asli Pertama
Buktikan untuk setiap n anggota N, jumlah dari n bilangan asli pertama diberikan oleh rumus,
Bukti Kita akan mencoba membuktikan pernyataan di atas dengan Prinsip Induksi Matematika yang dibahas di awal. Misalkan S adalah himpunan yang memuat n anggota Nsedemikian sehingga rumus di atas bernilai benar. Kita harus menguji apakah kondisi (1) dan (2) pada Prinsip Induksi Matematika terpenuhi. Jika n = 1, maka 1 = 1/2 ∙ 1 ∙ (1 + 1) sehingga 1 anggota S, dan (1) terpenuhi. Selanjutnya, andaikan k anggota S maka kita akan menunjukkan k + 1 juga akan menjadi anggota S. Jika k angota S, maka
Jika kita menambahkan k + 1 pada persamaan di atas, maka akan diperoleh
Karena persamaan di atas merupakan pernyataan untuk n = k + 1, maka kita menyimpulkan bahwa k + 1 anggota S. Sehingga, kondisi (2) terpenuhi. Sebagai hasilnya, menurut Prinsi Induksi Matematika kita memperoleh bahwa S = N, atau dengan kata lain persamaan tersebut berlaku untuk semua bilangan asli.
INDUKSI
Induksi matematika (mathematical induction) adalah metode pembuktian yang sering digunakan untuk menentukan kebenaran dari suatu pernyataan yang diberikan dalam bentuk bilangan asli. Akan tetapi sebelum membahas mengenai induksi matematika, kita akan membahas suatu prinsip yang digunakan untuk membuktikan induksi matematika, yaitu prinsip terurut rapi (well-ordering principle) dari bilangan asli. Seperti kita ketahui, himpunan bilangan asli adalah himpunan yang memiliki anggota 1, 2, 3, … yang dapat dituliskan sebagai berikut.
Setelah mengingat mengenai himpunan bilangan asli, sekarang perhatikan prinsip terurut rapi dari bilangan asli berikut.
Prinsip Terurut Rapi Bilangan Asli
Setiap himpunan bagian yang tidak kosong dari N memiliki anggota terkecil.
Secara lebih formal, prinsip tersebut menyatakan bahwa untuk setiap himpunan tidak kosong V yang merupakan himpunan bagian dari N, maka ada v0 anggota V sedemikian sehingga v0 ≤ v untuk setiap v anggota V.
Berdasarkan prinsip terurut rapi di atas, kita akan menurunkan prinsip induksi matematika yang dinyatakan dalam bentuk himpunan bagian N.
Prinsip Induksi Matematika
Misalkan S adalah himpunan bagian N yang memiliki 2 sifat:
(1) S memiliki anggota bilangan 1; dan
(2) Untuk setiap k anggota N, jika k anggota S, maka k + 1 anggota S.
Maka diperoleh S = N.
Sebelum membuktikan prinsip induksi matematika di atas secara formal, kita akan mencoba memahaminya dengan menggunakan efek domino seperti berikut.
Pada gambar (a) di atas kita melihat sebaris 4 domino pertama yang ditata rapi dengan jarak antara masing-masing domino yang berdekatan kurang dari tinggi domino. Sehingga, jika kita mendorong domino nomor k ke kanan, maka domino tersebut akan merebahkan domino nomor (k + 1). Proses ini ditunjukkan oleh gambar (b). Kita tentu akan berpikir bahwa apabila proses ini berlanjut, maka domino nomor (k + 1) tersebut juga akan merebahkan domino di sebelah kanannya, yaitu domino nomor (k + 2), dan seterusnya. Bagian (c) menggambarkan bahwa dorongan terhadap domino pertama merupakan analogi dari bilangan 1 menjadi anggota himpunan S. Hal ini merupakan langkah dasar dari proses efek domino. Selanjutnya, jika k anggota S akan menyebabkan (k + 1) anggota S, akan memberikan langkah induktif dan melanjutkan proses perebahan domino. Sehingga, pada akhirnya kita akan melihat bahwa semua domino akan rebah. Atau dengan kata lain, domino yang memiliki nomor urut semua bilangan asli akan rebah. Hal ini merupakan analogi dari S = N. Bagaimana dengan bukti formal dari prinsip induksi matematika?
Bukti Andaikan S ≠ N. Maka himpunan N – S bukan merupakan himpunan kosong, sehingga berdasarkan prinsip terurut rapi, himpunan tersebut memiliki anggota terkecil m. Karena 1 anggota S (berdasarkan hipotesis 1), maka m > 1. Tetapi hal ini akan mengakibatkan bahwa m – 1 juga merupakan bilangan asli. Karena m – 1 < m dan madalah anggota terkecil dari N – S, maka m – 1 anggota S.
Sekarang kita akan menggunakan hipotesis 2 bahwa k = m – 1 merupakan anggota S, maka k + 1 = (m – 1) + 1 = m juga anggota S. Akan tetapi pernyataan ini akan kontradiksi bahwa m bukan anggota S. Sehingga N – S adalah himpunan kosong atau dengan kata lain N = S.
Selain diformulasikan seperti di atas, Prinsip Induksi Matematika juga dapat dinyatakan sebagai berikut.
Untuk setiap n anggota N, misalkan P(n) merupakan suatu pernyataan tentang n. Apabila:
1. P(1) benar.
2. Untuk setiap k anggota N, jika P(k) benar, maka P(k + 1) benar.
Maka P(n) benar untuk setiap n anggota N.
Hubungan Prinsip Induksi Matematika tersebut dengan sebelumnya adalah dengan memisalkan S = {n anggota N | P(n) adalah benar}. Sehingga kondisi 1 dan 2 pada Prinsip Induksi Matematika di awal secara berturut-turut berkorespondensi dengan kondisi 1 dan 2 pada Prinsip Induksi Matematika terakhir. Selain itu, kesimpulan S = N juga berkorespondensi dengan kesimpulan P(n) benar untuk setiap n anggota N.
Asumsi bahwa “jika P(k) benar” dinamakan hipotesis induksi. Untuk membangun hipostesis 2, kita tidak perlu menghiraukan kebenaran dari P(k), tetapi yang perlu kita hiraukan adalah validitas dari “jika P(k), maka P(k + 1)”. Misalkan, jika kita akan menguji pernyataan P(n): “n = n + 5”, maka secara logis kondisi (2) adalah benar, dengan menambahkan 1 pada kedua sisi P(k) untuk mendapatkan P(k + 1). Akan tetapi, karena pernyataan P(1): “1 = 6” adalah salah, kita tidak dapat menggunakan Induksi Matematika untuk menyimpulkan bahwa n = n + 5 untuk setiap n anggota N.
Pada beberapa kasus, kadang P(n) bernilai salah untuk beberapa bilangan asli tertentu tetapi bernilai benar untuk n ≥ n0. Prinsip Induksi Matematika dapat dimodifikasi untuk mengatasi kasus seperti itu.
Prinsip Induksi Matematika (versi kedua)
Misalkan n0 anggota N dan misalkan P(n) merupakan pernyataan untuk setiap bilangan asli n ≥ n0. Apabila:
(1) Pernyataan P(n0) benar;
(2) Untuk setiap k ≥ n0, jika P(k) benar mengakibatkan P(k + 1) benar.
Maka P(n) benar untuk semua n ≥ n0.
Berikut ini adalah beberapa contoh yang menunjukkan bagaimana Induksi Matematika dapat digunakan untuk membuktikan pernyataan tentang bilangan asli.
Contoh 1: Pengubinan dengan Tromino
Diberikan suatu papan catur 2n × 2n (n > 0), dengan salah satu persegi di bagian pojok dihilangkan, buktikan bahwa papan catur tersebut dapat ditutup sempurna dengan tromino. (Tromino adalah gambar yang terdiri dari 3 persegi yang sisinya saling bersinggungan, tetapi 3 persegi tersebut tidak dalam satu barisan yang berjajar)
Bukti Pernyataan tersebut benar untuk n = 1 karena secara jelas papan catur 21 × 21 yang salah satu persegi bagian pojok dihilangkan memiliki bentuk yang sama dengan tromino. Andaikan pernyataan tersebut benar untuk k anggota N. Diberikan papan catur dengan ukuran 2k + 1 × 2k + 1 yang salah satu persegi di bagian pojok dihilangkan. Bagilah papan catur tersebut menjadi 4 papan catur 2k × 2k A, B, C, dan D, dengan satu di antaranya, yaitu A, memiliki bagian yang salah satu persegi di pojok hilang. Tempatkan 1 tromino, T, di tengah-tengah papan catur 2k + 1 × 2k + 1 sedemikian sehingga persegi-persegi tromino tersebut berada di bagian B, C, dan D. Kemudian gunakan kasus n = k untuk menutup bagian A, B – T, C – T, dan D – T dengan tromino. Proses tersebut akan menutup papan catur 2k + 1 × 2k + 1 tepat sempurna dengan tromino-tromino. (Gambar di bawah ini mengilustrasikan untuk kasus n = 3).
Contoh 2: Jumlah n Bilangan Asli Pertama
Buktikan untuk setiap n anggota N, jumlah dari n bilangan asli pertama diberikan oleh rumus,
Bukti Kita akan mencoba membuktikan pernyataan di atas dengan Prinsip Induksi Matematika yang dibahas di awal. Misalkan S adalah himpunan yang memuat n anggota Nsedemikian sehingga rumus di atas bernilai benar. Kita harus menguji apakah kondisi (1) dan (2) pada Prinsip Induksi Matematika terpenuhi. Jika n = 1, maka 1 = 1/2 ∙ 1 ∙ (1 + 1) sehingga 1 anggota S, dan (1) terpenuhi. Selanjutnya, andaikan k anggota S maka kita akan menunjukkan k + 1 juga akan menjadi anggota S. Jika k angota S, maka
Jika kita menambahkan k + 1 pada persamaan di atas, maka akan diperoleh
Karena persamaan di atas merupakan pernyataan untuk n = k + 1, maka kita menyimpulkan bahwa k + 1 anggota S. Sehingga, kondisi (2) terpenuhi. Sebagai hasilnya, menurut Prinsi Induksi Matematika kita memperoleh bahwa S = N, atau dengan kata lain persamaan tersebut berlaku untuk semua bilangan asli.
Langganan:
Postingan (Atom)