kelompok 7

Views:
 
Category: Education
     
 

Presentation Description

matematika diskrit

Comments

Presentation Transcript

PowerPoint Presentation:

KELOMPOK VII SYAMSIR SAINUDDIN, S.Pd MUHAMMAD ZAINAL ABIDIN, S.Pd FIRDA RAZAK, S.Pd DERANGEMENT, SISTEM RELASI REKURSIF, DAN RELASI REKURSIF MELIBATKAN KONVOLUSI

PowerPoint Presentation:

DERANGEMENT (PENGACAKAN) Derangement adalah permutasi objek-objek , di mana tidak ada objek yang menempati tempat aslinya . Contoh : 3142 atau 4321 adalah Derangement dari 1234, akan tetapi 3124 bukan derangement dari 1234, sebab dalam 3124, elemen 4 menempati posisinya semula ( posisi ke 4)

PowerPoint Presentation:

DERANGEMENT (PENGACAKAN) Sifat-sifat Derangement Dn = (n – 1)(Dn-1 + Dn-2) untuk n ≥ 2 Dn = nDn-1 + (-1)n untuk n ≥ 1 A. Relasi Rekursif Untuk Dn Karena hanya ada satu permutasi tanpa elemen maka D0 = 1. Untuk n = 1, D1 = 0, sebab tidak ada permutasi dengan satu elemen dimana elemen itu tidak menempati tempatnya semula . Untuk n = 2 diperoleh D2 = 1, sebab hanya ada satu permutasi dua elemen di mana setiap elemen tidak menempati tempatnya semula (21 adalah satu-satunya derangement dari 12).

PowerPoint Presentation:

DERANGEMENT (PENGACAKAN) Untuk n ≥ 2, kita peroleh relasi rekursif untuk Dn sebagai berikut : Pandang sebuah elemen sebarang dari n elemen yang ada . Tanpa menghilangkan keumuman , misal elemen itu adalah elemen n ( elemen dengan label n). Karena elemen n tidak boleh menempati posisi ke n; maka terdapat n – 1 kemungkinan posisi dari elemen ini , yaitu mungkin pada posisi ke-1 atau ke-2 atau ke-3 , atau ke -(n – 1) Tanpa menghilangkan keumuman , misal elemen n ini menempati posisi ke 1. Sekarang ada dua kemungkinan posisi dari elemen 1. Elemen 1 mungkin menempati posisi ke n atau mungkin tidak .

PowerPoint Presentation:

Elemen n . . . … . 1 Posisi ke- 1 2 3 4 n-1 n Kasus 1. Elemen 1 menempati posisi ke n Sekarang kita mempunyai n – 2 elemen yaitu elemen : 2, 3, …, n – 1 yang harus dijajar sedemikian hingga setiap elemen ini tidak boleh menempati tempatnya semula , artinya elemen i tidak boleh pada posisi ke - i untuk 2 ≤ i ≤ n – 1. Ini bisa dilakukan dengan Dn-2 cara . Sekarang kita mempunyai n – 2 elemen yaitu elemen : 2, 3, …, n – 1 yang harus dijajar sedemikian hingga setiap elemen ini tidak boleh menempati tempatnya semula , artinya elemen i tidak boleh pada posisi ke - i untuk 2 ≤ i ≤ n – 1. Ini bisa dilakukan dengan Dn-2 cara DERANGEMENT (PENGACAKAN)

PowerPoint Presentation:

DERANGEMENT (PENGACAKAN) Elemen n . . . … . (tidak 1) Posisi ke- 1 2 3 4 n-1 n Kasus 2. Elemen 1 tidak menempati posisi ke n Dalam kasus ini , kita mempunyai n – 1 elemen yaitu elemen-elemen 1, 2, 3, …, n -1 yang harus dijajar demikian hingga elemen 1 tidak pada posisi ke -n, elemen 2 tidak ada posisi ke-2, elemen 3 tidak pada posisi ke-3 dan seterusnya , elemen n – 1 tidak pada posisi ke -(n – 1). Ini dapat dilakukan dengan Dn-1 cara . Jadi banyaknya derangement dari n elemen dengan syarat elemen n menempati posisi ke-1 adalah Dn-2 + Dn-1. Telah disebut pada bagian (a) bahwa ada n – 1 kemungkinan posisi dari elemen n. sehingga , untuk n ≥ 2 diperoleh hubungan , Dn = (n – 1) (Dn-1 + Dn-2)

PowerPoint Presentation:

DERANGEMENT (PENGACAKAN) Persamaan Dn = (n – 1) (Dn-1 + Dn-2) dapat ditulis sebagai berikut , D­n = nDn-1 – Dn-1 + (n-1)Dn-2 Ekuivalen dengan D­n - nDn-1 = - (Dn-1 - (n-1)Dn-2) (a.1) Misalkan an = Dn – nDn-1, maka persamaan diatas menjadi an = -an-1, (n ≥ 2) karena a1 = D1 – D0 = 0 – 1 = -1 maka a2 = -a1 = 1 a3 = -a2 = -1 … an = (-1)n, n ≥ 1 dengan demikian , relasi rekursif untuk Dn adalah sebagai berikut . D0 = 1; Dn = nDn-1 + (-1)n, n ≥ 1

PowerPoint Presentation:

DERANGEMENT (PENGACAKAN) B. Mencari Formula untuk Dn Telah ditunjukkan bahwa , untuk n ≥ 1, berlaku hubungan Dn = nDn-1 + (-1)n (a.2) Kita akan selesaikan relasi rekursif ini dengan fungsi pembangkit eksponensial . Untuk itu kita misalkan , Kalikan kedua ruas dari persamaan Dn = nDn-1 + (-1)n dengan dan “ diambil sigmanya ” untuk n ≥ 1, diperoleh Ruas kiri dari persamaan diatas dapat dituliskan sebagai berikut .

PowerPoint Presentation:

DERANGEMENT (PENGACAKAN) = P(x) – 1 Suku kedua ruas kanan persamaan tersebut adalah , S uku pertama ruas kanan persamaan , Sehingga persamaanya dapat dituliskan sebagai berikut : P(x) -1 = x P(x) + e -x – 1

PowerPoint Presentation:

DERANGEMENT (PENGACAKAN) Ekuivalen dengan , Karena , Maka , Dengan demikian

PowerPoint Presentation:

B. Sistem Relasi Rekursif Misal a n menyatakan banyaknya barisan binair n- angka yang memuat “0” sebanyak genap dan “1” sebanyak genap; b n menyatakan banyaknya barisan binair n- angka yang memuat “0” sebanyak genap dan “1” sebanyak ganjil ; c n adalah banyaknya barisan binair n- angka yang memuat “0” sebanyak ganjil dan “1” sebanyak genap : dan d n adalah banyaknya barisan binair n- angka yang memuat “0” sebanyak ganjil dan “1” sebanyak ganjil .

PowerPoint Presentation:

Sistem Relasi Rekursif jelas bahwa a 0 = 1 dan b 0 = c 0 = d 0 = 0. Jadi relasi rekursif untuk a n , b n , c n dan d n diberikan oleh system rekursif berikut a n = b n-1 +c n-1 , n ≥ 1 b n = a n-1 +d n-1 , n ≥1 c n = a n-1 +d n-1 , n ≥1 d n = b n-1 +c n-1 , n ≥1 dengan kondisi awal a 0 = 1 dan b 0 = c 0 = d 0 = 0.

PowerPoint Presentation:

Sistem Relasi Rekursif Selanjutnya digunakan fungsi pembangkit untuk menyelesaikan system rekursif tersebut . Misalkan A(x), B(x), C(x) dan D(x) berturut-turut adalah fungsi pembangkit biasa dari a n , b n , c n , dan d n . Diperoleh , A(x) = a 0 + a 1 x + a 2 x 2 + … = a 0 + (b 0 + c 0 )x + (b 1 + c 1 )x 2 + … = a 0 + x(b 0 + b 1 x + b 2 x 2 + … ) + x(c 0 + c 1 x + c 2 x 2 + … ) = 1 + x B(x) + xC (x); B(x) = b 0 + b 1 x + b 2 x 2 + … = b 0 + (a 0 + d 0 )x + (a 1 + d 1 )x 2 + … = 0 + x(a 0 + a 1 x + a 2 x 2 + … ) + x(d 0 + d 1 x + d 2 x 2 + … ) = x A(x) + xD (x); C(x) = c 0 + c 1 x + c 2 x 2 + … = c 0 + (a 0 + d 0 )x + (a 1 + d 1 )x 2 + … = 0 + x(a 0 + a 1 x + a 2 x 2 + … ) + x(d 0 + d 1 x + d 2 x 2 + … ) = x A(x) + xD (x); D(x) = d 0 + d 1 x +d + … = d 0 + (b 0 + c 0 )x + (b 1 + c 1 )x 2 + … = 0 + x(b 0 + b 1 x + b 2 x 2 + … ) + x(c 0 + c 1 x + c 2 x 2 + … ) = x B(x) + xC (x);

PowerPoint Presentation:

Sistem Relasi Rekursif Dengan demikian , kita peroleh sistem persamaan dalam A(x), B(x), C(x), dan D(x) seperti berikut ini . A(x) = 1 + x B(x) + xC (x) Shg B(x) = x A(x) + xD (x); Shg C(x) = x A(x) + xD (x); Shg D(x) = x B(x) + xC (x ); Shg

PowerPoint Presentation:

Sistem Relasi Rekursif Selanjutnya kita cari koefisien x n dalam A(x), B(x), C(x), dan D(x). Karena ,

PowerPoint Presentation:

Sistem Relasi Rekursif Maka a 0 = 1 dan untuk n ≥ 1, diperoleh Atau ,

PowerPoint Presentation:

Sistem Relasi Rekursif Selanjutnya , karena Maka Perhatikan bahwa C(x) = B(x), sehingga jelas c n = b­n.

PowerPoint Presentation:

Sistem Relasi Rekursif Dengan demikian , Akhirnya ,

PowerPoint Presentation:

C. Relasi Rekursif Melibatkan Konvolusi Misalkan diberi sebaris n bilangan , x 1 ,x 2 , … , x n . kita perintahkan “ komputer ” untuk mencari hasil kalinya . Terdapat banyak cara untuk mendapatkan hasil kali tersebut Contoh: Misalkan untuk n = 2 dapat dituliskan (x 1 x 2 ) Jadi untuk n = 2 terdapat 1 cara n = 3 dapat dituliskan ((x 1 x 2 )x 3 ) dan (x 1 (x 2 x 3 )) Jadi untuk n = 3 terdapat 2 cara n = 4 dapat dituliskan (((x 1 x 2 )x 3 )x 4 ), ((x 1 (x 2 x 3 )) x 4 ), (x 1 ((x 2 x 3 )x 4 )), (x 1 (x 2 (x 3 x 4 ))), ((x 1 x 2 (x 3 x 4 )) Jadi untuk n = 4 terdapat 5 cara

PowerPoint Presentation:

Relasi Rekursif Melibatkan Konvolusi Misal K n menyatakan banyak cara untuk mendapatkan hasil kali ( dengan aturan di atas ) dan barisan n bilangan . Jelas bahwa K 1 = 1; K 2 = 1; K 3 = 2 dan K 4 = 5. Selanjutnya untuk n ≥ 2, relasi rekursif untuk K n dapat diperoleh dengan cara berikut : Perhatikan “ perkalian terakhir ” yang dilakukan untuk menentukan hasil kali dari n bilangan x 1 , x 2 , … , x n . Ini melibatkan hasil kali dua subperkalian x 1 , … , x r dan x r+1 , x r+2 , … , x n : dimana 1 ≤ r ≤ n-1: yaitu ((x 1 … x r )(x r+1 … x n )

PowerPoint Presentation:

Relasi Rekursif Melibatkan Konvolusi Di sini kita definisikan , untuk r = 1, (x 1 … x n-1 )( x n )) ≡ (x 1 (x 2 … x n )) dan , untuk r = n-1 ((x 1 … x n-1 )( x n )) ≡ ((x 1 … x n-1 ) x n ) Karena ada K r cara untuk mendapatkan hasil kali dari sub perkalian x 1 … x r dan K n -r cara untuk mendapatkan hasil kali sub perkalian x r-1 … x n serta 1 ≤ r ≤ n-1, maka

PowerPoint Presentation:

Relasi Rekursif Melibatkan Konvolusi Jika kita definisikan K 0 = 0 maka persamaan (c.1) menjadi , Selanjutnya , kita selesaikan rekursif persamaan (c.2) dengan fungsi pembangkit . Untuk itu , misalkan Kalikan kedua ruas persamaan (c.2) dengan x n dan " diambil sigmanya ” untuk n ≥ 2, diperoleh ,

PowerPoint Presentation:

Relasi Rekursif Melibatkan Konvolusi Perhatikan bahwa = P(x) – x Dan = {P(x)} 2 Sehingga (c.3) menjadi P(x) – x = [P(x)] 2 [P(x)] 2 – P(x) + x = 0

PowerPoint Presentation:

Relasi Rekursif Melibatkan Konvolusi Selanjutnya , kita ekspansi bentuk Dari Teorema Binomial Umum , diperoleh Untuk n ≥ 1, didapat

PowerPoint Presentation:

Relasi Rekursif Melibatkan Konvolusi Sehingga ,

PowerPoint Presentation:

Relasi Rekursif Melibatkan Konvolusi Dengan demikian dari (c.4) dengan memilih “ tanda negatif ” diperoleh Ini berarti , untuk n ≥ 1,

PowerPoint Presentation:

SEKIAN dan TERIMA KASIH