PERMUTASI DAN KOMBINASI

1.      PERMUTASI

	TIK:  Setelah mempelajari sub bab ini mahasiswa dapat menghitung permutasi

 

Permutasi dari suatu himpunan adalah urutan dari elemen-elemen himpunan   tersebut dalam sebuah baris

Contoh:   {a,b,c} mempunyai 6 permutasi yaitu :

     abc         acb            cba       cab       bac       bca

Jumlah permutasi dari suatu himpunan dengan n elemen adalah n! dengan n adalah bilangan bulat dan n  ≥ 1.

Contoh

1.      Berapa banyak cara yang bisa dilakukan untuk menyusun huruf-huruf dari kata COMPUTER?

2.      Berapa banyak cara yang bisa dilakukan untuk menyusun huruf-huruf dari kata COMPUTER jika huruf CO dianggap sebagai satu kesatuan?

Jawab:

1. Kedelapan huruf dalam kata COMPUTER semuanya berbeda, sehingga banyaknya cara untuk menyusun huruf-huruf sama dengan jumlah permutasi dari suatu himpunan dengan 8 elemen. Ini sama dengan 8! = 40.320.
2. Jika CO dianggap sebagai satu kesatuan, maka secara efektif hanya ada 7 elemen yang dapat disusun.

 

Sehingga banyaknya cara untuk menyusun huruf-huruf sama dengan jumlah permutasi dari suatu himpunan dengan 7 elemen. Ini sama dengan 7! = 5.040

Permutasi dari elemen terpilih

Diberikan {a,b,c}. Ada 6 cara untuk memilih 2 huruf dari himpunan tersebut dan menuliskannya dalam urutan yaitu:        ab            ac         ba        bc        ca         cb

Definisi 1.1.1.

r-permutasi dari suatu himpunan dengan n elemen adalah pengambilan r elemen yang terpilih secara terurut dari suatu himpunan dengan n elemen. Jumlah r-permutasi dari suatu himpunan dengan n elemen dinotasikan dengan P(n,r)

Teorema 1.1.2.

Misalkan n dan r adalah bilangan bulat dan 1 ≤ r ≤ n. Jumlah r-permutasi dari suatu himpunan dengan n elemen diberikan dengan rumus

P(n,r) = n (n – 1) (n – 2).... (n – r + 1)                        (versi pertama)

Atau, ekivalen dengan

P(n,r) =                                                          (versi kedua)

Contoh

1. Hitung P(5,2)
2. Berapa jumlah 4-permutasi dari suatu himpunan dengan 7 elemen ?
3. Berapa jumlah 5-permutasi dari suatu himpunan dengan 5 elemen ?
4. Berapa cara yang berbeda  bisa dilakukan jika 3 huruf dari kata BYTES dipilih?
5. Berapa cara yang berbeda  bisa dilakukan pada soal nomor 4 jika huruf pertama harus B.

Jawab

1. P(5,2) = = 20
2. P(7,4) = = 840
3. P(5,5) = = 120
4. Penyelesaiannya adalah sama dengan 3-permutasi dari suatu himpunan dengan 5 elemen, yaitu

P(5,3) = = 60

5. P(4,2) = = 12

2.KOMBINASI

TIK : Setelah mempelajari sub bab ini mahasiswa dapat menghitung kombinasi

 

Definisi 1.2.1.

Misalkan n dan r adalah bilangan bulat nonnegativ dengan r ≤ n. r-kombinasi dari suatu himpunan dengan n elemen adalah himpunan bagian berukuran r dari himpunan dengan n elemen. Notasi , dibaca “n dipilih r” adalah jumlah himpunan bagian berukuran r (r-kombinasi) yang dapat dipilih dari suatu himpunan dengan n elemen.

Notasi lain yang terkadang digunakan selain  adalah C(n,r),  , , atau .

Contoh

1.        Diketahui S = {Ani, Bobi, Cici, Dani}

Dibentuk komite yang terdiri dari 3 orang dari 4 orang dalam S.

a.       Dapatkan semua 3-kombinasi dari himpunan S.

b.      Hitunglah

2.        Berapa banyak susunan tak terurut yang dapat dibuat dari 2 elemen yang diambil dari himpunan {0,1,2,3}?

Jawab

1.      a.   3-kombinasi dari himpunan S adalah himpunan bagian S berukuran 3, yaitu :

{Bobi, Cici, Dani}

{Ani, Cici, Dani}

{Ani, Bobi, Dani}

{Ani, Bobi, Cici}

      b.   = 4.

2.      Susunan tak terurut yang dapat dibuat dari 2 elemen yang diambil dari himpunan {0,1,2,3} sama dengan 2-kombinasi, yaitu :

{0,1}, {0,2}, {0,3}, {1,2}, {1,3}, {2,3}

      Terlihat ada = 6 susunan.

Teorema 1.2.2.

Jumlah himpunan bagian beukuran r (r-kombinasi) yang dapat dipilih dari suatu himpunan dengan n elemen,  , diberikan dengan rumus

=                                                             (versi pertama)

Atau, ekivalen dengan

=                                              (versi kedua)

dengan n dan r adalah bilangan bulat nonnegativ dengan r ≤ n.

Contoh

1.  Hitung

2.   Dipilih 5 orang dari 12 orang yang ada yang akan bekerja dalam sebuah tim untuk mengerjakan proyek khusus. Berapa banyak tim yang berbeda dengan jumlah anggota 5 orang yang dapat dibentuk?

Jawab

1.         == 56

2.         == 792.

Permutasi himpunan dengan elemen yang berulang

Pertimbangkan variasi susunan huruf-huruf dari kata MISSISSIPPI berikut :

            IIMSSPISSIP,             ISSSPMIIPIS,             PIMISSSSIIP,  dst

Berapa banyak susunan yang berbeda yang bisa dibuat?

Jawab

Kita bayangkan menempatkan 11 huruf dari kata MISSISSIPPI satu setelah yang lain ke dalam  11 posisi.

Banyaknya susunan huruf-huruf tersebut =

                                                                  =

                                                                  =  = 34.650

Teorema 1.2.3.

Diketahui suatu himpunan terdiri dari n elemen dengan

n₁ elemen tipe 1

n₂ elemen tipe 2

           

n_k elemen tipe k

dan n₁ + n₂ + ... + n_k = n.

Jumlah permutasi yang berbeda dari n elemen adalah

......=

Pertanyaan yang muncul :

Berapa banyak cara yang berbeda untuk memilih r elemen dari suatu himpunan dengan n elemen jika dibolehkan adanya elemen yang sama?

Misalnya :

3 elemen yang dipilih dari {1,2,3,4} ada kemungkinan

-  dipilih 3, 3, dan 1

-  dipilih 2, 2, dan 2

-  dipilih 1, 2, dan 4 dst

Kita notasikan masing-masing pilihan ini dengan [3,3,1], [2,2,2], dan [1,2,4] dst.

Ingat bahwa karena urutan tidak diperhatikan maka [3,3,1] = [3,1,3] = [1,3,3].

Definisi 1.2.4.

r-kombinasi dengan kebolehan adanya pengulangan (elemen) (r-combination with repetition allowed) atau multiset berukuran r, dipilih dari suatu himpunan X dengan n elemen adalah pemilihan elemen tak terurut yang diambil dari himpunan X  dengan kebolehan adanya pengulangan (elemen). Jika X = {x₁, x₂, …x_n}, kita tulis r-kombinasi dengan kebolehan adanya pengulangan (elemen) (r-combination with repetition allowed), atau multiset berukuran r sebagai  dimana merupakan elemen X dan beberapa mungkin sama satu sama lain

Contoh

Tuliskan secara lengkap 3-kombinasi dengan kebolehan adanya pengulangan (elemen)  atau multiset berukuran 3, yang dapat dipilih dari {1,2,3,4}.

Jawab

Daftar tersebut adalah

[1,1,1]; [1,1,2]; [1,1,3]; [1,1,4]

[1,2,2]; [1,2,3]; [1,2,4]

[1,3,3]; [1,3,4]; [1,4,4]

[2,2,2]; [2,2,3]; [2,2,4]

[2,3,3]; [2,3,4]; [2,4,4]

[3,3,3]; [3,3,4]; [3,4,4]

[4,4,4]

Jadi terdapat 20 cara

Teorema 1.2.5.

Jumlah r-kombinasi dengan kebolehan adanya pengulangan (elemen) (r-combination with repetition allowed) atau multiset berukuran r, yang dapat dipilih dari suatu himpunan dengan n elemen  adalah

Contoh

Dengan menggunakan teorema di atas, maka 3-kombinasi dengan kebolehan adanya pengulangan (elemen)  atau multiset berukuran 3, yang dapat dipilih dari {1,2,3,4}sama dengan = = =  = 20.

3.      TEOREMA BINOMIAL

	TIK  :  Setelah mempelajari sub bab ini mahasiswa  dapat  menggunakan teorema binomial

 

Dalam aljabar, jumlahan 2 suku, misalnya a + b disebut sebuah binomial. Teorema binomial memberikan sebuah ekspresi derajat binomial (a + b)ⁿ, untuk setiap bilangan bulat positif n dan semua bilangan real a dan b.

Perhatikan

(a + b)² = (a + b) (a + b) = aa + ab + ba + bb

(a + b)³ = (a + b) (a + b) (a + b) = aaa + aab + aba + abb +baa +bab +bba + bbb

(a + b)⁴ = (a + b) (a + b) (a + b) (a + b)

 =  aaaa + aaab + aaba + aabb + abaa + abab + abba + abbb + baaa +baab +  baba + babb + bbaa + bbab + bbab +bbba +bbbb

=   a⁴ + 4 a³ b + 6 a² b² + 4 a b³ + b⁴.

=   a⁴ +  a³ b +  a² b² +  a b³ + b⁴.

Teorema 1.1.3 (Teorema Binomial)

Diberikan  sebarang bilangan real a dan b dan sebarang n bilangan bulat nonnegative.

(a + b)ⁿ =  

 = aⁿ +  a^n-1 b +  a^n-2 b² + … +  a b^n-1 + bⁿ.

Contoh

1.      Ekspansikan ekspresi (x – 4y)⁴ dengan teorema binomial

2.      Bilangan manakah yang lebih besar : (1,01)^1.000.000 atau 10.000?

3.      Gunakan teorema binomial untuk menunjukkan bahwa

2ⁿ = = +++ ..... +

Untuk setiap bilangan bulat n ≥ 0.

Jawab

1.      (x – 4y)⁴ =

         =  x⁴ + x^4-1(– 4y)¹ +  x^4-2(– 4y)² + x^4-3(– 4y)³ + (– 4y)⁴

         =  x⁴ + 4 x³(– 4y)  +  6x²(16y²) + 4x (– 64y³) + (256y⁴)

         =  x⁴ – 16 x³ y  +  96x² y² – 256 x y³ + 256y⁴.

2.      (1,01)^1.000.000 = (1 + 0,01)^1.000.000

   = 1 + 1^999.999 (0,01)¹ + suku-suku positif lainnya

   = 1 + (1.000.000) (1) (0,01) + suku-suku positif lainnya

   = 10.001 + suku-suku positif lainnya

        Oleh karena itu (1,01)^1.000.000 > 10.

3.     Untuk latihan saudara.