8.4 GENERATING FUNCTIONS

8.4 GENERATING FUNCTIONS

Fungsi pembangkit Fungsi pembangkit digunakan untuk merepresentasikan barisan secara efisien dengan mengkodekan unsur barisan sebagai koefisien deret pangkat dalam variabel x . Fungsi pembangkit dapat digunakan untuk: – memecahkan berbagai masalah counting, – memecahkan relasi recurrence, dan – membuktikan identitas kombinatorik.

Definisi Definisi. Fungsi pembangkit (generating function) untuk barisan bilangan real: a0, a1, …, ak, … adalah deret pangkat tak hingga: 

G( x)  a0  a1 x  ...  a k x  ...   a k x k . k

k 0

Contoh 1. a. Fungsi pembangkit dari barisan {an} dengan ak = 5  adalah k 5 x  k 0

b. Fungsi pembangkit dari barisan {an} dengan ak = k+3  adalah k ( k  3 ) x  k 0

c. Fungsi pembangkit dari barisan {an} dengan ak = 3k  adalah k k 3  x k 0

Contoh 2 Tentukan fungsi pembangkit dari barisan 1, 1, 1, 1, 1, 1 Solusi. Fungsi pembangkit dari barisan 1,1,1,1,1,1 adalah: 6 x 1 2 3 4 5 1+x+x +x +x +x  x 1

Contoh Contoh 3. Fungsi pembangkit dari barisan 1, 1, 1, 1, … adalah 1 2 3 1+x+x +x +…  , jika | x | 1 1 x Contoh 4. Fungsi pembangkit dari barisan 1 1, a, a2, a3, …  1  ax , jika | ax | 1 adalah 1 + ax + a2x2 + a3x3 + …

Teorema 1 M isal f ( x)  k 0 ak x dan g ( x)  k 0 bk x k . M aka, 



k

f ( x)  g ( x)  k 0 (ak  bk ) x k 

f ( x ) g ( x )  k  0 



k



dan

k a b x . j 0 j k  j

Contoh 5. Misal f(x) = 1/(1-x)2. Tentukan koefisien a0, a1, … dalam ekspansi f(x) =  akxk. Solusi.   k  k  1 1 1 k      1 x  ( k  1 ) x .    2   (1  x) (1  x) (1  x) k 0  j 0  k 0 Jadi, ak = k+1.

Koefisien Binomial Diperluas Misalkan u bilangan real dan k bilangan bulat tak negatif. Maka koefisien binomial diperluas didefinisikan sebagai: u (u  1)...(u  k  1) u    , jika k  0,     k! k   , jika k  0. 1 Contoh 6. Tentukan nilai dari:   2  (2)(3)(4) a.   2      4.   3!  3   3  1/ 2 1 / 2  (1 / 2)(1 / 2  1)(1 / 2  2)(1 / 2  3)(1 / 2  4) b.      . 5   5!  5 

Teorema Binomial Diperluas Teorema 2. Misal x bilangan real dengan |x| < 1 dan u bilangan real.  Maka, u  k u

(1  x)     x . k 0  k 

Catatan. Jika u bilangan bulat positif maka Teorema Binomial Diperluas menjadi Teorema Binomial.

Contoh 7 Tentukan fungsi pembangkit untuk (1+x)-n dan (1-x)-n, dengan n bilangan bulat positif. Solusi.   n k n M enurut Teorema 2, (1  x)     x . k 0  k  

M aka, (1  x)  n   (1) k C (n  k  1, k ) x k k 0

Dengan mengganti x dgn  x : (1  x)

n



  C (n  k  1, k ) x k k 0

Soal 1 Tentukan koefisien x10 dalam deret pangkat fungsi-fungsi berikut ini: a. 1/(1+x)2 b. 1/(1-2x)

c. x4/(1-3x)3

Masalah Counting dan Fungsi Pembangkit Contoh 8. Tentukan banyaknya solusi dari n1 + n2 + n3 = 17, bila n1, n2 dan n3 bilangan bulat taknegatif dengan 2  n1  5, 3  n2  6 dan 4  n3  7. Solusi. Banyaknya solusi dinyatakan oleh koefisien x17 dalam ekspansi: (x2+x3+x4+x5) (x3+x4+x5+x6) (x4+x5+x6+x7). Setiap bentuk x17 dalam perkalian ini didapat dengan mengalikan xn1 pada faktor pertama dengan xn2 pd faktor kedua dan xn3 pada faktor ketiga yang memenuhi: n1 + n2 + n3 = 17. Bila dihitung, didapat koefisien x17 adalah 3. Jadi, ada tepat 3 solusi.

Contoh 9 Ada berapa cara untuk membagikan 8 kue yang identik kepada 3 anak jika setiap anak menerima sedikitnya 2 kue dan tidak lebih dari 4 kue? Solusi. Misalkan cn: banyaknya cara membagikan n kue. Karena setiap anak menerima sedikitnya 2 kue dan tidak lebih dari 4 kue, maka untuk setiap anak ada suatu faktor yang berbentuk: (x2 + x3 + x4) dalam fungsi pembangkit barisan {cn}. Karena ada 3 anak maka fungsi pembangkitnya adalah: (x2 + x3 + x4)3. Cara untuk membagikan 8 kue adalah koefisien dari x8, yakni 6. Jadi, ada 6 cara untuk membagikan 8 kue kepada 3 anak tadi.

Soal 2 Gunakan fungsi pembangkit untuk menentukan banyaknya cara mendistribusikan 25 donat yang identik kepada 4 polisi sehingga setiap polisi mendapatkan sedikitnya 3 dan tidak lebih dari 7 donat.

Contoh 10 Gunakan fungsi pembangkit untuk menentukan banyaknya cara memilih pecahan mata uang bernilai Rp. 100, Rp. 500 dan Rp. 1000 jika kita ingin membayar suatu barang yang bernilai Rp. r, apabila: a. urutan pemilihan diperhatikan atau b. tidak diperhatikan. Contoh. Untuk membayar Rp. 600, ada 2 cara bila urutan tidak diperhatikan, yaitu (Rp. 100, Rp. 100, Rp. 100, Rp. 100, Rp. 100, Rp. 100) atau (Rp. 100, Rp. 500) dan ada 3 cara bila urutan diperhatikan, yaitu (Rp. 100, Rp. 100, Rp. 100, Rp. 100, Rp. 100, Rp. 100), (Rp. 100, Rp. 500), atau (Rp. 500, Rp. 100)

Contoh 10 (2) b. Jika urutan pemilihan tidak diperhatikan. Karena masing-masing pecahan dapat dipergunakan berkalikali, maka • faktor yang merepresentasikan penggunaan Rp. 100 adalah 1 + x + x2 + x3 + …, • faktor yang merepresentasikan penggunaan Rp. 500 adalah 1 + x5 + x10 + …, • faktor yang merepresentasikan penggunaan Rp. 1000 adalah 1 + x10 + x20 + … Jadi, banyaknya cara pemilihan pecahan mata uang untuk membayar seharga Rp. r adalah koefisien dari xr/100 dalam fungsi pembangkit (1 + x + x2 + x3 + …) (1 + x5 + x10 + …) ( 1 + x10 + x20 + …)

Contoh 10 (3) a. Jika urutan pemilihan diperhatikan. Banyaknya cara untuk menggunakan tepat n pecahan untuk membayar seharga Rp. r adalah koefisien xr/100 dalam (x + x5 + x10)n Karena kita dapat menggunakan berapa pun jumlah pecahan, maka banyaknya cara pemilihan pecahan mata uang untuk membayar seharga Rp. r adalah koefisien dari xr/100 dalam 1 + (x + x5 + x10) + (x + x5 + x10)2 + … 1 1   5 10 1  ( x  x  x ) 1  x  x5  x10

Soal 3 Gunakan fungsi pembangkit untuk menentukan banyaknya cara untuk menukar uang $100 dengan menggunakan pecahan: a) $10, $20 dan $50 b) $5, $10, $20 dan $50 c) $5, $10, $20 dan $50; bila setiap pecahan digunakan sedikitnya sekali. d) $5, $10 dan $20; bila setiap pecahan digunakan sedikitnya sekali tapi tidak lebih dari 4 kali.

Contoh 11 Gunakan fungsi pembangkit untuk menghitung banyaknya cara memilih r obyek dari n jenis benda berbeda jika kita harus memilih sedikitnya satu obyek dari setiap jenisnya. Solusi. Misalkan ar: banyaknya cara memilih r obyek dari n jenis benda bila dari setiap jenis terpilih sedikitnya satu objek. Karena kita perlu memilih sedikitnya satu obyek dari setiap jenis, maka setiap jenis menyumbangkan faktor (x + x2 + x3 + …) pada fungsi pembangkit. Akibatnya, fungsi pembangkit G(x) dari barisan {ar} adalah G(x) = (x+x2 + x3 + …)n = xn(1+x+x2 + x3 + …)n = xn / (1-x)n .

Contoh 11 (2) Dengan menggunakan Teorema Binomial Diperluas:

xn n n G ( x)   x .( 1  x ) (1  x) n   n    x n r 0  ( x) r  x n  (1) r C (n  r  1, r )(1) r x r r 0  r  



  C (n  r  1, r ) x

nr

r 0



  C (t  1, t  n) x t t n



  C (r  1, r  n) x r . r n

Jadi, ada C(r-1,r-n) cara memilih.

Fungsi Pembangkit dan Solusi Relasi Recurrence Contoh 12. Cari solusi relasi recurrence ak = 3ak-1 untuk k = 1, 2, 3, … dengan kondisi awal a0 = 2. Solusi.  Misal G(x): fungsi pembangkit untuk barisan {ak}, G( x)  k 0 ak x k Maka, xG ( x)   a x k 1   a x k .



k 0



k

k 1

k 1

G ( x)  3xG ( x)  k 0 ak x  3k 1 ak 1 x k 

k



 a0  k 1 (ak  3ak 1 ) x k  2. 

Jadi, G ( x) 

2 . 1  3x

2    k 0 a k x k maka G ( x)  2k 0 3k x k . 1  ax Jadi, ak  2  3k . Karena,

Fungsi Pembangkit dan Pembuktian Identitas Contoh 13. Gunakan fungsi pembangkit untuk membuktikan: 2 C ( n , k )  C (2n, n), bila n bulat. k 0 n

Solusi. C(2n,n) adalah koefisien xn dlm ekspansi (1+x)2n. Akan tetapi, (1+x)2n = [(1+x)n]2. = [C(n,0)+C(n,1)x+ … + C(n,n)xn]2. Koefisien dari xn dlm ekspansi ini: C(n,0)C(n,n) + C(n,1)C(n,n-1) + … + C(n,n)C(n,0). Ini sama dgn  C(n,k)2, krn C(n,n-k) = C(n,k). Karena C(2n,n) dan  C(n,k)2 menyatakan koefisien xn dlm (1+x)2n maka haruslah



n

2 C ( n , k )  C (2n, n). k 0

8.5 INCLUSION-EXCLUSION

Prinsip Inklusi-Eksklusi Ada berapa anggota dalam gabungan dua himpunan hingga? |A1  A2| = |A1| + |A2| - |A1  A2|

Contoh 1 Ada berapa bilangan bulat positif lebih kecil atau sama dengan 100 yang habis dibagi 6 atau 9? Solusi. Misalkan A: himpunan bilangan bulat dari 1 sampai 100 yang habis dibagi 6 B: himpunan bilangan bulat dari 1 sampai 100 yang habis dibagi 9. Dengan menggunakan prinsip inklusi-eksklusi, banyaknya bilangan bulat dari 1 sampai 100 yang habis dibagi 6 atau 9 adalah | A B |  | A|  | B |  | A B |  100 / 6  100 / 9  100 / 18  16  11  5  22

Contoh 2 Misalkan ada 1467 mahasiswa angkatan 2011 di ITB. 97 orang di antaranya adalah mahasiswa Prodi Informatika, 68 mahasiswa Prodi Matematika, dan 12 orang mahasiswa double degree Informatika dan Matematika. Ada berapa orang yang tidak kuliah di Departemen Matematika atau Informatika?

Solusi. Misalkan

A: himpunan mahasiswa angkatan 2004 di Departemen Informatika B: himpunan mahasiswa angkatan 2004 di Departemen Matematika Maka |A|=97, |B|=68, dan |AB|=12. Banyaknya mahasiswa angkatan 2004 di Departemen Informatika atau Matematika adalah |A  B| = |A| + |B| - |A  B|= 97 + 68 – 12 = 153 Jadi, terdapat 1467 – 153 = 1314 mahasiswa angkatan 2004 yang tidak kuliah di Departemen Matematika atau Informatika.

Perluasan Prinsip Inklusi-Eksklusi untuk tiga himpunan Angka 1 merah menunjukkan daerah yang terlibat ketika |A| dihitung, angka 1 hijau menunjukkan daerah yang terlibat ketika |B| dihitung,dan angka 1 biru menunjukkan daerah yang terlibat ketika |C| dihitung. Terlihat bahwa daerah yang beririsan dihitung berulang-ulang. |A  B| dikurangkan (dua 1 merah diambil),

|A  C| dikurangkan (dua 1 biru diambil), dan |B  C| dikurangkan (dua 1 hijau diambil) Terlihat bahwa penghitungan hampir benar, kecuali pada daerah di mana ketiga himpunan sama-sama beririsan. Maka perlu ditambahkan kembali |A  B  C|.

Perluasan Prinsip Inklusi-Eksklusi untuk tiga himpunan (2) Jadi, |A  B  C| = |A| + |B| + |C| - |A  B| - |A  C| - |B  C| + |A  B  C|

Contoh 3 Sebanyak 115 mahasiswa mengambil mata kuliah Matematika Diskrit, 71 Kalkulus Peubah Banyak, dan 56 Geometri. Di antaranya, 25 mahasiswa mengambil Matematika Diskrit dan Kalkulus Peubah Banyak, 14 Matematika Diskrit dan Geometri, serta 9 orang mengambil Kalkulus Peubah Banyak dan Geometri. Jika terdapat 196 mahasiswa yang mengambil paling sedikit satu dari ketiga mata kuliah tersebut, berapa orang yang mengambil ketiga mata kuliah sekaligus?

Contoh 3 (2) Solusi. Misalkan MD: himpunan mahasiswa yang mengambil mata kuliah Matematika Diskrit, KPB: himpunan mahasiswa yang mengambil mata kuliah Kalkulus Peubah Banyak, dan G: himpunan mahasiswa yang mengambil mata kuliah Geometri. Maka |MD| = 115, |KPB| = 71, |G| = 56, |MD  KPB| = 25, |MD  G| = 14, |KPB  G| = 9, dan |MD  KPB  G| = 196 Dengan mempergunakan prinsip inklusi-eksklusi: |MDKPBG| = |MD| + |KPB| + |G| - |MDKPB| - |MDG| - |KPBG| + |MDKPBG| 196 = 115 + 71 + 56 - 25 - 14 - 9 + |MD  KPB  G| Jadi, |MD  KPB  G| = 2

Soal 1 Carilah banyaknya anggota dari |A  B  C| jika terdapat 100 anggota dalam setiap himpunan dan jika a. ketiga himpunan tersebut tidak ada yang saling beririsan b. terdapat 50 anggota yang sama dalam setiap pasang himpunan dan tidak ada anggota yang sama dalam ketiga himpunan sekaligus c. terdapat 50 anggota yang sama dalam setiap pasang himpunan dan 25 anggota yang sama dalam ketiga himpunan sekaligus d. irisan setiap pasang himpunan dan irisan ketiga himpunan berukuran sama

Prinsip Inklusi-Eksklusi Teorema 1. Misalkan A1, A2, …, An himpunan hingga. Maka | A  A   A |  | A |  | A  A | 1

2

2

1i  n



i

1i  j  n

i

j

n 1 | A  A  A |    (  1 ) | A1  A2   An |  i j k

1i  j  k  n

Contoh 4 Carilah banyaknya anggota dari |A  B  C  D| jika setiap himpunan berukuran 50, setiap irisan dari dua himpunan berukuran 30, setiap irisan dari tiga himpunan berukuran 10, dan irisan dari keempat himpunan berukuran 2.

Solusi. |ABCD|=|A| + |B| + |C| + |D| - |AB|-|AC|-|AD|-|BC| - |BD|- |CD| + |ABC|+ |ABD|+|ACD| + |BCD| - |A  B  C  D| = 4 . 50 – 6 . 30 + 4 . 10 – 2 = 58

Soal Soal 2. Ada berapa banyak permutasi dari ke-26 huruf dalam alfabet yang memuat paling sedikit satu dari kata FIGHT, BALKS, MOWER. Soal 3. Ada berapa banyak permutasi dari ke-26 huruf dalam alfabet yang memuat paling sedikit satu dari kata CAR, CARE, SCARE, SCARED.

Peluang gabungan kejadian Teorema 2. Misalkan E1, E2, E3 tiga kejadian dalam ruang sampel S. Maka p(E1  E2  E3) = p(E1) + p( E2 ) + p( E3 ) - p(E1  E2 ) - p(E1  E3 ) - p( E2  E3 ) + p(E1  E2  E3 )

Teorema 3. Misalkan E1, E2, …, En kejadian-kejadian dalam ruang sampel S. Maka  n  p  Ei   i 1 



 p( E )   p( E  E )

1i  n

i

1i  j  n

i

j

n   n 1   p( Ei  E j  Ek )    (1) p  Ei  1i  j  k  n  i 1 

Soal 4 Berapakah peluang bahwa ketika empat angka dari 1 sampai 100, dipilih secara acak tanpa pengulangan, terjadi salah satu dari kejadian-kejadian berikut: keempatnya angka ganjil, keempatnya habis dibagi tiga, atau keempatnya habis dibagi 5.

8.6 APPLICATIONS OF INCLUSION– EXCLUSION

Beberapa Aplikasi Inklusi-Eksklusi • Banyaknya bilangan prima yang lebih kecil dari suatu bilangan bulat positif • Banyaknya fungsi pada dari suatu himpunan hingga ke himpunan hingga lainnya. • Masalah derangement: penitipan topi (“the hatcheck problem”)

Bentuk Alternatif Inklusi-Eksklusi Misalkan S: himpunan dengan jumlah anggota N. Ai: subhimpunan yang memuat anggota dengan sifat Pi. N Pi Pi  Pi : banyaknya anggota dengan semua sifat Pi , Pi ,, Pi 1 2 k maka N P P  P  | A  A   A | 1

2



k

i1 i2

ik



i1

i2

ik

N P1 ' P2 ' Pn ' :banyaknya anggota yang tidak memiliki sifat P1 , P2 ,, Pn

maka N P ' P ' P '  N  | A  A  A | 1 2 n 1 2 n

Dengan prinsip inklusi-eksklusi, N P1 ' P2 ' Pn '  N   N ( Pi )  1i  n



 N (P P )

1i  j  n

i

j

n N ( P P P )    (  1 ) N ( P1 P2  Pn )  i jk

1i  j  k  n

Contoh 1 Ada berapa solusi yang dimiliki oleh x1 + x2 + x3 = 11 dengan x1, x2, x3 bilangan bulat tak negatif dan x1  3, x2  4, dan x3  6.

Solusi. Misalkan P1: sifat x1 > 3, P2: sifat x2 > 4, dan P3: sifat x3 > 6. Maka banyaknya solusi adalah: N P1 ' P2 ' P3 '  N  N ( P1 )  N ( P2 )  N ( P3 )  N ( P1P2 )  N ( P1P3 )  N ( P2 P3 )  N ( P1 P2 P3 )

Contoh 1 (2) • • • • •

N: jumlah solusi total = C(3+11-1,11) = 78 N(P1): jumlah solusi dengan x1  4 = C(3+7-1,7) = 36 N(P2): jumlah solusi dengan x2  5 = C(3+6-1,6) = 28 N(P3): jumlah solusi dengan x3  6 = C(3+5-1,5) = 15 N(P1 P2): jumlah solusi dengan x1  4 dan x2  5 = C(3+2-1,2) =6 • N(P1 P3): jumlah solusi dengan x1  4 dan x3  7 = C(3+0-1,0) =1 • N(P2 P3): jumlah solusi dengan x2  5 dan x3  7 = 0 • N(P1P2P3): jumlah solusi dengan x1  4, x2  5 dan x3  7 = 0 Jadi, N(P1’P2’P3’) =78 - 36 - 28 - 15 + 6 + 1 + 0 - 0 =6

The Sieve of Erotosthenes • Mencari banyaknya bilangan prima yang tidak melebihi suatu bilangan bulat positif tertentu. • Suatu bilangan komposit hanya dapat dibagi oleh bilangan prima yang tidak melebihi akar bilangan tersebut. Contoh 2. Tentukan banyaknya bilangan prima yang tidak melebihi 100. Solusi. Faktor prima dari bilangan yang kurang dari 100 tidak akan melebihi 10. Jadi, bilangan yang kurang dari 100 habis dibagi 2, 3, 5, atau 7.

The Sieve of Erotosthenes (2)

Misalkan P1: sifat bilangan habis dibagi 2, P2: sifat bilangan habis dibagi 3, P3: sifat bilangan habis dibagi 5, dan P4: sifat bilangan habis dibagi 7. Maka banyaknya bilangan prima yang lebih besar 1 dan tidak melebihi 100 adalah: 4 + N(P1’ P2’ P3’ P4’) Jadi, menurut inklusi-eksklusi: N P1 ' P2 ' P3 ' P4 '  99  N ( P1 )  N ( P2 )  N ( P3 )  N ( P4 )  N ( P1 P2 )  N ( P1 P3 )  N ( P1 P4 )  N ( P2 P3 )  N ( P2 P4 )  N ( P3 P4 )  N ( P1 P2 P3 )  N ( P1 P2 P4 )  N ( P1 P3 P4 )  N ( P2 P3 P4 )  N ( P1 P2 P3 P4 ) 100  100  100  100   99          2   3   5   7  100  100   100  100  100  100               2  3  2  5  2  7  3 5  3 7  5  7   100   100   100   100   100        21      2  3  5 2  3  7 2  5  7 3  5  7 2  3  5  7          

The Sieve of Erotosthenes (3) 1 11 21 31 41 51 61 71 81 91

2 12 22 32 42 52 62 72 82 92

3 13 23 33 43 53 63 73 83 93

4 14 24 34 44 54 64 74 84 94

5 15 25 35 45 55 65 75 85 95

6 16 26 36 46 56 66 76 86 96

7 17 27 37 47 57 67 77 87 97

8 18 28 38 48 58 68 78 88 98

9 19 29 39 49 59 69 79 89 99

10 20 30 40 50 60 70 80 90 100

Banyaknya fungsi pada Ada berapa banyak fungsi pada dari himpunan dengan 6 anggota ke himpunan dengan 3 anggota? Solusi. Misalkan anggota-anggota dari kodomain adalah b1, b2, dan b3. Misalkan P1, P2, dan P3 adalah sifat bahwa b1, b2, dan b3 tidak berada dalam range fungsi. Karena fungsi akan pada jhj fungsi tersebut tidak memiliki semua sifat P1, P2, atau P3, maka banyaknya fungsi pada dari himpunan dengan 6 anggota ke himpunan dengan 3 anggota adalah N P1 ' P2 ' P3 '  N  N ( P1 )  N ( P2 )  N ( P3 )  N ( P1P2 )  N ( P1P3 )  N ( P2 P3 )  N ( P1 P2 P3 )

Banyaknya fungsi pada (2) • N: banyaknya fungsi dari himpunan dengan 6 anggota ke himpunan dengan 3 anggota = 36. • N(Pi): banyaknya fungsi yang tidak mempunyai bi dalam range = 26. • N(Pi Pj): banyaknya fungsi yang tidak mempunyai bi dan bj dalam range = 16 = 1. • N(P1 P2 P3): banyaknya fungsi yang tidak mempunyai b1, b2, dan b3 dalam range = 0. Jadi, banyaknya fungsi pada dari himpunan dengan 6 anggota ke himpunan dengan 3 anggota adalah 36 - C(3,1) 26 + C(3,2) 1 – 0 = 540

Banyaknya fungsi pada & aplikasinya Teorema 1 Misalkan m dan n bilangan bulat positif dengan m  n. Maka, terdapat nm - C(n,1) (n-1)m + C(n,2) (n-2)m – … + (-1)n-1 C(n,2) 1m fungsi pada dari himpunan dengan m anggota ke himpunan dengan n anggota. Soal 1. Terdapat berapa cara untuk mendelegasikan lima pekerjaan yang berbeda pada empat karyawan yang berbeda jika setiap karyawan ditugasi minimal satu pekerjaan? Soal 2. Ada berapa cara untuk mendistribusikan enam mainan yang berbeda pada tiga anak jika setiap anak mendapatkan minimal satu mainan?

Derangements Derangement adalah permutasi objek sehingga tidak ada objek yang menempati tempat aslinya. Contoh 3. Permutasi 654123 adalah derangement dari 123456. Permutasi 653124 bukanlah derangement dari 123456. Dn menyatakan banyaknya derangement dari n obyek. Contoh 4. D3 = 2

Banyaknya derangement dari n objek Suatu permutasi dikatakan memiliki sifat Pi jika permutasi tersebut mengakibatkan anggota i tetap pada tempatnya. Jelas derangement dalam himpunan dengan n anggota adalah permutasi yang tidak memiliki sifat Pi, i=1,2,…,n. Jadi, Dn  N P1 ' P2 ' Pn '  N  

 N (P )   N (P P )

1i  n

i

1i  j  n

i

j

 N ( P P P )    (1) N ( P P  P ) n

1i  j  k  n

i

j k

1 2

n

o N: banyaknya permutasi dengan n anggota = n! o N(Pi): banyaknya permutasi yang menetapkan satu anggota = (n-1)! o N(Pi Pj): banyaknya permutasi yang menetapkan dua anggota = (n-2)! o N(Pi1 Pj2 …Pjm): banyaknya permutasi yang menetapkan m anggota = (n-m)!

Banyaknya derangement dari n objek (2) Karena terdapat C(n,m) cara untuk memilih m dari n anggota, maka o  N(Pi) = C(n,1) (n-1)! o  N(Pi Pj) = C(n,2) (n-2)! o Dan secara umum,  N(Pi1 Pj2 …Pjm) = C(n,m) (n-m)! Sehingga, Teorema 2. Banyaknya derangement dalam himpunan dengan n anggota adalah  1 1 1 n 1 Dn  n! 1       (1)  n!  1! 2! 3!

The Hatcheck Problem Seorang pegawai baru di tempat penitipan topi suatu rumah makan menerima titipan topi dari n pengunjung, tetapi ia lupa untuk menomori topitopi tersebut. Ketika para pengunjung hendak mengambil kembali topi mereka, pegawai ini memilih secara acak dari topi yang tersisa. Berapakah peluangnya bahwa tidak ada seorang pun yang menerima topinya kembali.

The Hatcheck Problem (2) Solusi. Peluang bahwa tidak ada seorang pun yang menerima topinya kembali adalah Dn 1 1 n 1  1      (1) n! 1! 2! n!

Jika n membesar tanpa batas.  Dn 1 1 lim   (1) n   0,368 n  n! n! e n 1