4. Pencacahan Pengantar

Pencacahan (counting) adalah bagian dari matematika kombinatorial. Matematika

kombinatorial berkaitan dengan pengaturan sekumpulan objek. Pencacahan berusaha

menjawab pertanyaan-pertanyaan berikut:

• “Ada berapa banyak password yang bisa dibuat dengan 8 buah abjad?”

• “Ada berapa banyak cara yang bisa dipakai untuk mengambil 11 orang

pemain bola dari 20 orang pemain yang ada didalam suatu tim?”

Lebih penting lagi, pencacahan merupakan dasar dari penghitungan peluang kejadian diskrit,

misalnya “Berapakah peluang seseorang untuk memenangkan suatu undian?”

Beberapa prinsip dasar dari pencacahan diuraikan di bawah ini.

Aturan penjumlahan (sum rule)

Andaikan suatu prosedur dapat dipecah menjadi dua buah pekerjaan (tasks), sebut sebagai T1

dan T2. Jika T1 dapat dilakukan dengan n1 cara dan T2 dengan n2 cara, dan jika kedua

pekerjaan ini tidak dapat dilakukan pada saat yang bersamaan, maka akan terdapat n1+n2 cara

untuk melakukan prosedur ini.

Contoh: Departemen Teknik elektro ITB akan memberikan hadiah sebuah komputer kepada

seorang mahasiswa atau (eksklusif) seorang dosen. Ada berapa banyak pilihan berbeda jika

ada 800 mahasiswa dan 110 orang dosen di DTE? Jawab: Ada 800 + 110 = 910 buah pilihan.

Aturan penjumlahan Yang Diperumum

Jika ada suatu prosedur terdiri dari m-buah pekerjaan, T1, T2, …, Tm, yang masing-masing

dapat dilakukan dengan n1, n2, …, nm cara, dan setiap pasang pekerjaan tersebut tidak dapat

dilakukan secara bersamaan, maka akan ada n1 + n2 + … + nm cara untuk melakukan

pekerjaan ini.

Aturan Perkalian (Product Rule)

4. Pencacahan - 1

Andaikan suatu prosedur dapat dipecah menjadi dua buah pekerjaan yang dilakukan secara

berurutan. Jika ada n1 buah cara untuk melakukan pekerjaan pertama dan n2 buah cara untuk

melakukan pekerjaan yang kedua setelah pekerjaan pertama selesai, maka akan ada n1×n2

buah cara untuk mengerjakan prosedur tersebut.

Aturan Perkalian Yang Diperumum

Jika ada suatu prosedur yang terdiri atas pekerjaan-pekerjaan yang dilakukan secara

berurutan T1, T2, …, Tm yang masing-masing dapat dilakukan dengan n1, n2, …, nm buah cara,

maka akan ada n1×n2 ⋅ …×nm buah cara untuk mengerjakan prosedur tersebut.

Contoh 4.1: Suatu kode seri kendaraan (nomor polisi) dibuat dengan 3 buah abjad. Ada

berapa buah kemungkinan kode yang dapat dibuat?

Jawab: Ada 26 buah kemungkinan untuk huruf pertama, kemudian 26 buah kemungkinan

untuk huruf kedua dan 26 kemungkinan lain untuk huruf terakhir. Jadi terdapat 26⋅26⋅26 =

17576 buah kode seri kendaraan yang berbeda yang bisa dibuat dari 3 buah abjad.

Aturan penjumlahan dan perkalian dapat juga dinyatakan kedalam teori himpunan, seperti

dinyatakan dalam aturan berikut ini.

Aturan penjumlahan (Dalam operasi Himpunan)

Misalkan A1, A2, …, Am adalah himpunan-himpunan yang tak beririsan (disjoint). Maka

banyaknya cara untuk memilih satu anggota dari himpunan-himpunan ini adalah

|A1 ∪ A2 ∪ … ∪ Am | = |A1| + |A2| + … + |Am|.

Aturan perkalian (Dalam operasi Himpunan)

Misalkan A1, A2, …, Am adalah himpunan-himpunan yang berhingga. Maka banyaknya cara

untuk memilih satu anggota dari masing-masing himpunan dengan urutan A1, A2, …, Am

adalah kardinalitas dari perkalian Kartesian semua himpunan tersebut

|A1× A2 × … ×Am | = |A1| ⋅ |A2| ⋅ … ⋅ |Am|.

4. Pencacahan - 2

Sebagai ilustrasi, perhatikan contoh berikut ini. Contoh: berapa banyak bit string dengan

panjang 8 bit yang bisa dimulai dengan “1” atau berakhir dengan “00”?

Pekerjaan-1

Bentuk suatu string dengan panjang 8 yang dimulai dengan 1.

Ada satu cara untuk mengambil bit pertama (1),

dua cara untuk mengambil bit kedua (0 atau 1),

dua cara untuk mengambil bit ketiga (0 atau 1),

…..

dua cara untuk mengambil bit kedelapan (0 atau 1).

Maka berdasarkan aturan perkalian, pekerjaan 1 dapat dilakukan dengan 1⋅27=128 cara.

Pekerjaan 2

Bentuk suatu string dengan panjang 8 yang berakhir dengan 00.

ada dua cara untuk mengambil bit pertama (0 atau 1),

dua cara untuk mengambil bit kedua (0 atau 1),

……

dua cara untuk mengambil bit ke-enam (0 atau 1),

satu cara untuk mengambil bit ke-tujuh (0), dan

satu cara untuk mengambil bit ke-delapan (0).

Maka berdasarkan aturan perkalian, pekerjaan 2 dapat dilakukan dengan 26 = 64 cara.

Karena ada 128 buah cara untuk melakukan pekerjaan 1 dan 64 cara untuk melakukan

pekerjaan 2, apakah ini berarti ada 192 buah bit string 8 bit yang berawalan dengan 1 dan

berakhiran dengan 00 ? Tentu saja tidak demikian karena beberapa pekerjaan 1 dan pekerjaan

2 dapat dilakukan pada waktu bersamaan. Ketika kita melakukan pekerjaan 1 dan membuat

string yang diawali dengan 1, beberapa dari string ini berakhiran 00. Karena kadangkala kita

4. Pencacahan - 3

bisa melakukan pekerjaan 1 dan 2 pada saat bersamaan, maka aturan penjumlahan tidak

berlaku.

Jika kita ingin menggunakan aturan penjumlahan dalam kasus yang demikian, kita harus

mengurangkan kasus-kasus dimana pekerjaan 1 dan 2 dilakukan secara bersamaan dari total

kemungkinan. Ada berapa banyak kasus yang demikian, yaitu, berapa banyak string yang

berawal dengan 1 dan berakhir dengan 00?

Ada satu cara untuk mengambil bit pertama (1),

Ada dua cara untuk bit yang kedua (0 atau 1),

…,

ke-enam (0 atau 1),

ada satu cara untuk bit ketujuh (0),

dan satu cara untuk bit kedelapan (0).

Berdasarkan aturan perkalian, maka ada 25 = 32 buah kasus, dimana pekerjaan 1 dan 2 dapat

dikerjakan secara bersamaan.

Karena terdapat 128 cara untuk melakukan pekerjaan 1 dan 64 cara untuk melakukan

pekerjaan 2, dan 32 diantaranya kedua pekerjaan tersebut dilakukan pada saat yang

bersamaan, maka sebenarnya ada 128+64–32=160 cara untuk melakukan pekerjaan 1 dan

pekerjaan 2 (tak bersamaan). Di dalam teori himpunan, hal ini berhubungan dengan

himpunan A1 dan A2 yang tidak beririsan. Maka kita punya: |A1 ∪ A2| = |A1| + |A2| - |A1 ∩ A2|

Ini disebut sebagai prinsip inklusi-eksklusi.

Diagram pohon dapat dipakai untuk menganalisis banyaknya pekerjaan. Sebagai contoh,

berikut ini analisis untuk menghitung banyaknya kombinasi bit string 4 bit yang tidak

memiliki dua bit 1 berurutan. Berdasar diagram tersebut, akan ada 8 buah string.

4. Pencacahan - 4

Pekerjaan-4 Bit-4

Prinsip Sarang Merpati (Pigeonhole Principles)

Prinsip sarang merpati mengatakan: Jika (k+1) buah atau lebih objek ditempatkan kedalam k

buah kotak, maka akan ada sedikitnya satu buah kotak yang berisi dua atau lebih objek.

Contoh 4.2: Suatu tim sepakbola yang terdiri dari 11 orang pemain menang telak 12-0 atas

lawannya. Maka ada setidaknya seorang pemain didalam tim pemenang yang memasukkan

gol sedikitnya duakali.

Contoh 4.3: Jika seorang mahasiswa mengikuti 6 mata kuliah dari hari Senin sampai hari

Jumat, maka akan ada sedikitnya satu hari dimana dia mengikuti dua mata kuliah.

Prinsip ini bisa diperumum menjadi: Jika N buah objek dimasukkan kedalam k buah kotak,

maka akan ada sedikitnya satu buah kotak yang berisi setidaknya ⎡N/k⎤ buah objek.

Contoh 4.4: Dalam kelas yang berisi 60 orang mahasiswa, minimal 12 orang mahasiswa akan

memiliki nilai yang sama (jika nilai dinyatakan sebagai A, B, C, D, atau F).

0

1

0

10

0

1

0

1

0

1

0

0 0

1

0

1

0

Pekerjaan-1 Bit-1

Pekerjaan-2 Bi -2

Pekerjaan-3 Bit-3

t

4. Pencacahan - 5

Contoh 4.5: Dalam kelas yang berisi 61 orang mahasiswa, sedikitnya ada 13 orang

mahasiswa yang memperoleh nilai (A, B, C, D, atau F) yang sama.

Contoh 4.6: Andaikan ada suatu kotak berisi selusin kaus kaki coklat dan selusin kaus kaki

hitam yang terdistribusi acak. Dalam keadaan gelap, berapa banyak kauskaki yang harus

diambil untuk memastikan bahwa akan didapatkan satu pasang kauskaki dengan warna yang

benar?

Ada dua tipe kaus kaki, jadi jika diambil sedikitnya 3 buah kauskaki, akan ada sedikitnya dua

kauskaki dengan warna atau coklat atau hitam, yakni, menurut prinsip sarang merpati yang

diperumum, akan ada ⎡3/2⎤ = 2. Pemakaian prinsip ini perlu diperhatikan berlakunya.

Perhatikan kasus berikut:

Contoh 4.7: Ada berapa banyak kelompok yg terdiri dari 3 orang yang bisa diambil dari

sekumpulan 6 orang?

Jawab: Ada 6 pilihan untuk orang pertama, 5 untuk yang kedua, dan 4 untuk yang berbeda,

jadi ada 6⋅5⋅4 = 120 buah cara untuk melakukan hal ini. Ini bukanlah hasil yang benar!

Misalnya, mengambil si C, kemudian si A dan lalu si E akan menghasilkan kelompok yang

sama dengan mengambil si E, lalu si C dan kemudian si A. Tetapi, kasus-kasus ini dihitung

secara terpisah ini pada persamaan diatas.

Jadi bagaimana cara menghitung banyaknya himpunan bagian orang berlainan yang dapat

diambil (jadi, kita ingin mengabaikan urutan pengambilan)? Untuk mengetahuinya, kita perlu

melihat permasalahan permutasi. Suatu permutasi dari himpunan objek yang berlainan adalah

pengaturan berurut dari objek-objek ini. Pengaturan berurut dari r elemen dari suatu

himpunan disebut sebagai permutasi-r.

Contoh 4.8: Diketahui suatu himpunan S = {1, 2, 3}. Maka, pengaturan dari 3, 1, 2 adalah

permutasi dari S. Demikian pula, pengaturan 3, 2 adalah permutasi-2 dari S.

Permutasi dan Kombinasi

4. Pencacahan - 6

Banyaknya permutasi-r dari suatu himpunan yang memiliki n buah anggota berlainan

dituliskan sebagai P(n, r). Kita bisa menghitung P(n, r) dengan aturan perkalian:

P(n, r) = n⋅(n–1)⋅(n–2) ⋅…⋅(n – r + 1).

(n pilihan untuk elemen pertama, (n–1) untuk yang kedua, (n–2) untuk yang ketiga …dst.)

Contoh 4.9: P(8, 3) = 8⋅7⋅6 = 336 = (8⋅7⋅6⋅5⋅4⋅3⋅2⋅1)/(5⋅4⋅3⋅2⋅1)

Kita memiliki rumus umum untuk menghitung permutasi sebagai berikut:

P(n, r) = n!/(n – r)!

Kembali ke pertanyaan semula: “Berapa banyak kumpulan 3 orang (berbeda) yang

dapat diambil dari sekelompok 6 orang (berbeda)?“ Sebelum bisa menjawab

pertanyaan ini, terlebih dahulu harus diperkenalkan konsep kombinasi.

Suatu kombinasi-r dari elemen suatu himpunan adalah seleksi tak berurut dari r-buah elemen

dari himpunan tsb. Jadi, suatu kombinasi-r adalah himpunan bagian dari suatu himpunan

dengan r-buah elemen. Contoh: Misalkan S = {1, 2, 3, 4}, maka {1, 3, 4} adalah kombinasi-3

dari S.

Banyaknya kombinasi-r dari suatu himpunan dengan n-buah elemen berlainan dituliskan

sebagai C(n, r). Misalnya C(4, 2) = 6, sebagai ilustrasi, kombinasi-kombinasi dari himpunan

{1, 2, 3, 4} adalah {1, 2}, {1,3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}. Bagaimana cara menghitung

C(n, r)? Tinjau bahwa kita dapat memperoleh permutasi-r dari suatu himpunan dengan cara

berikut:

Pertama-tama, kita membentuk semua kombinasi-r dari himpunan tsb (ada C(n,r)

kombinasi-r yg demikian).

Kemudian, kita membangkitkan semua pengurutan (ordering) yang mungkin didalam setiap

kombinasi-r ini (ada P(r, r) pengurutan yang demikian dalam setiap kasus).

4. Pencacahan - 7

Oleh karena itu, kita peroleh: P(n, r) = C(n, r)⋅P(r, r)

C(n, r) = P(n, r)/P(r, r) = n!/(n – r)!/(r!/(r – r)!)

= n!/(r!(n – r)!)

Sekarang kita bisa menjawab pertanyaan awal kita: “Berapa banyak kumpulan 3 orang

(berbeda) yang dapat diambil dari sekelompok 6 orang (dengan mengabaikan

urutan pengambilan)?“ Ini jelas

C(6, 3) = 6!/(3!⋅3!) = 720/(6⋅6) = 720/36 = 20

Jadi akan ada 20 cara berbeda, atau 20 kelompok berbeda yang diambil.

Corollary. Andaikan n dan r bil. bulat tak negatif dengan r ≤ n. Maka C(n, r) = C(n, n – r).

Ingat bahwa “mengambil sekelompok r orang dari kelompok n orang” adalah sama dengan

“memecah sekelompok n orang kedalam suatu kelompok r orang dan sekelompok (n – r)

orang lainnya”.

Contoh 4.10: Suatu klub sepakbola memiliki 8 pemain wanita dan 7 pemain pria. Dalam

suatu pertandingan, 6 pemain wanita dan 5 pemain pria akan diturunkan di lapangan. Berapa

banyak konfigurasi yang bisa dibentuk?

C(8, 6) ⋅ C(7, 5) = 8!/(6!⋅2!) ⋅ 7!/(5!⋅2!) = 28⋅21 = 588

Kita sudah mengetahui banyaknya cara mengambil himpunan bagian dengan kardinalitas r

dari suatu himpunan dengan kardinalitas n. Bilangan ini kita sebut sebagai C(n,r). Dan kita

menemukan rumus menghitung C(n, r):

!( , )!( )!

nC n rr n r

=−

4. Pencacahan - 8

Kita juga melihat hal berikut:

! !( , ) ( , )( )![ ( )]! ( )! !

n nC n n r C n rn r n n r n r r

− = = =− − − −

Secara intuitif, kesetangkupan ini masuk akal. Misalnya, tinjau suatu himpunan dengan enam

anggota (n = 6). Ambil dua anggota dan tinggalkan empat pada dasarnya sama dengan ambil

empat anggota dan tinggalkan dua. Yang manapun dari kedua kasus tsb, banyaknya pilihan

kita adalah banyaknya kemungkinan memisahkan himpunan tsb kedalam satu himpunan

beranggota dua dan satu lagi beranggota empat.

Identitas Pascal

Misalkan n dan k dua bilangan bulat positif dengan n ≥ k, maka

C(n + 1, k) = C(n, k – 1) + C(n, k).

Bagaimana menjelaskannya? Apa kegunaannya?

Bayangkan sebuah himpunan S yang mengandung n anggota dan himpunan T yang

mengandung (n+1) anggota, yaitu semua anggota S ditambah satu anggota baru a.

Menghitung C(n+1, k) ekivalen dengan menjawab pertanyaan berikut: Ada berapakah

himpunan bagian dari T yang mengandung k buah anggota?

Kasus I: Himpunan bagian mengandung (k–1) anggota dari S ditambah anggota a: C(n, k – 1)

buah pilihan.

Kasus II: Himpunan bagian mengandung k buah anggota dari S dan tidak mengandung a:

C(n, k) buah pilihan.

Aturan penjumlahan: C(n + 1, k) = C(n, k – 1) + C(n, k).

Didalam segitiga Pascal, setiap bilangan adalah jumlahan dari bilangan di kiri-atasnya dengan

kanan-atasnya:

4. Pencacahan - 9

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

…………

Karena C(n + 1, k) = C(n, k – 1) + C(n, k) dan C(0, 0) = 1, kita dapat menyederhanakan

perhitungan C(n,k) dengan memakai segitiga Pascal:

k

C(0,0)=1 C(1,0)=1 C(1,1)=1 C(2,0)=1 C(2,1)=2 C(2,2)=1

C(3,0)=1 C(3,1)=3 C(3,2)=3 C(3,3)=1

n

C(4,0)=1 C(4,1)=4 C(4,2)=6 C(4,3)=4 C(4,4)=1 …………

Ekspresi berbentuk C(n, k) disebut juga sebagai koefisien binomial. Mengapa demikian?

Suatu ekspresi binomial adalah jumlahan dua suku, seperti (a + b). Sekarang tinjau (a+b)2 =

(a + b)(a + b). Saat melakukan pengembangan ekspresi ini, kita harus membentuk semua

kemungkinan perkalian suatu suku dari faktor pertama dengna suku dari faktor kedua:

(a + b)2 = a·a + a·b + b·a + b·b

Suku-suku sejenis bisa dikumpulkan:

(a + b)2 = a2 + 2ab + b2

Untuk (a + b)3 = (a + b)(a + b)(a + b) kita peroleh

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

(a + b)3 = a3 + 3a2b + 3ab2 + b3

4. Pencacahan - 10

Hanya ada suku a3, karena hanya ada satu kemungkinan untuk membentuknya: Pilih a untuk

ketiga faktor: C(3, 3) = 1. Begitu pula suku a2b muncul tiga kali: C(3, 2) = 3. Suku ab2 juga

muncul tiga kali: C(3, 1) = 3 dan suku b3 muncul satu kali: C(3, 0) = 1. Sehingga kita

mendapatkan rumus:

(Teorema Binomial) 0

( ) ( , )n

n

ja b C n j a b−

=

+ = ⋅∑ n j j

Dengan bantuan segitiga Pascal, rumus ini dapat menyederhanakan proses ekspansi

perpangkatan dalam ekspresi binomial. Misalnya, baris ke-lima dari segitiga Pascal

(1 – 4 – 6 – 4 – 1) membantu kita menghitung

(a + b)4 = a4 + 4a3b + 6a2b2 + 4ab3 + b4

4. Pencacahan - 11