Penjelasan Permutasi dan Kombinasi

Aturan perkalian

Soal kombinatorika menanyakan dengan berapa cara berbeda sesuatu dapat terjadi. Dasarnya adalah aturan perkalian: jika suatu pilihan dapat dilakukan dengan $m$ cara dan pilihan kedua yang tidak bergantung padanya dapat dilakukan dengan $n$ cara, keduanya bersama-sama dapat dilakukan dengan $m \times n$ cara. Gagasan ini berlaku untuk berapa pun banyaknya tahap.

Dengan 3 kemeja, 4 celana, dan 2 pasang sepatu dapat dibentuk $3 \times 4 \times 2 = 24$ padanan pakaian yang berbeda. Kode PIN empat digit yang tersusun dari angka 0 sampai 9, dengan pengulangan diperbolehkan, memiliki $10 \times 10 \times 10 \times 10 = 10^4 = 10{,}000$ kemungkinan. Semua rumus dalam artikel ini adalah singkatan dari perkalian semacam itu: jika suatu soal tampak janggal, kembali menghitung tahap demi tahap selalu dapat diandalkan.

Faktorial

Untuk menyusun $n$ benda yang berbeda dalam satu barisan, ada $n$ pilihan untuk tempat pertama, $n - 1$ pilihan untuk tempat kedua, dan seterusnya sampai 1. Hasil kali ini disebut $n$ faktorial:

Jadi $5! = 120$: lima buku dapat disusun di sebuah rak dengan 120 cara berbeda. Menurut definisi, $0! = 1$; ini menjaga rumus-rumus di bawah tetap konsisten: ada tepat satu cara untuk mengurutkan «tidak ada apa-apa». Faktorial tumbuh dengan sangat cepat: $10! = 3{,}628{,}800$, sedangkan satu set kartu remi yang dikocok memiliki $52!$ kemungkinan urutan; itu bilangan dengan 68 angka.

Permutasi: urutan penting

Permutasi adalah susunan berurutan dari $r$ benda yang dipilih di antara $n$ benda berbeda. Karena urutannya penting, susunan «pertama, kedua, ketiga» berbeda dari susunan «ketiga, kedua, pertama». Banyaknya permutasi adalah:

Susunan duduk mengelilingi meja bundar adalah kasus khusus. Jika semua orang bergeser satu kursi, susunannya tetap sama; karena itu $n$ orang dapat didudukkan dengan $(n-1)!$ cara berbeda. Enam orang di meja bundar memiliki $5! = 120$ susunan duduk, bukan 720. Ini disebut permutasi siklis.

Kombinasi: urutan tidak penting

Kombinasi adalah pilihan yang hanya mementingkan unsur mana yang terpilih. Jika Ani, Budi, dan Citra dipilih menjadi panitia, dalam urutan apa pun mereka dipilih, panitianya tetap sama. Setiap kelompok yang terdiri atas $r$ benda sesuai dengan $r!$ permutasi; karena itu kita membagi dengan bilangan ini:

Kombinasi bersifat simetris: $\binom{n}{r} = \binom{n}{n-r}$, karena memilih 3 orang yang masuk sama saja dengan memilih 5 orang yang tidak masuk. Bilangan-bilangan ini juga merupakan bilangan dalam segitiga Pascal dan koefisien dalam penjabaran binomial $(a + b)^n$.

Bagaimana mengetahui mana yang diperlukan?

Ajukan satu pertanyaan: jika dua unsur yang terpilih ditukar tempatnya, apakah hasilnya berbeda? Jika ya, urutan penting dan yang diperlukan adalah permutasi. Jika tidak, gunakan kombinasi.

• Juara dalam lomba, peringkat, kode PIN, susunan duduk, dan jadwal: permutasi.
• Tim, panitia, kartu di tangan, tiket lotre, dan topping pizza: kombinasi.
• Jabatan di dalam kelompok, misalnya ketua dan bendahara, membuat urutan menjadi penting walaupun orang-orangnya dipilih dari kelompok yang sama.

Pemeriksaan cepat: banyaknya permutasi selalu $r!$ kali banyaknya kombinasi. Jika kedua hasil Anda tidak memenuhi hubungan ini, salah satunya keliru.

Pilihan dengan pengulangan dan menghitung huruf yang berulang

Jika unsur-unsurnya boleh berulang, rumusnya berubah. Banyaknya pilihan berurutan dengan pengulangan, seperti pada contoh kode PIN, adalah $n^r$. Banyaknya pilihan tanpa urutan dengan pengulangan, misalnya memilih 3 skop es krim dari 5 rasa dengan rasa boleh berulang, adalah:

Susunan huruf yang berulang memerlukan satu koreksi lagi: karena menukar huruf-huruf yang sama tidak mengubah apa pun, kita harus membagi dengan faktorial setiap banyaknya pengulangan. Nama sungai Mississippi dalam bahasa Inggris terdiri atas 11 huruf; 4 di antaranya huruf I, 4 huruf S, dan 2 huruf P: jadi ada $\frac{11!}{4!\,4!\,2!} = 34{,}650$ anagram yang berbeda.

Menghitung untuk perhitungan peluang

Jika hasil-hasilnya sama mungkin, peluang adalah banyaknya hasil yang diinginkan dibagi banyaknya semua hasil yang mungkin; karena itu pekerjaan utamanya dilakukan oleh permutasi dan kombinasi. Dasar perbandingan ini dijelaskan dalam artikel dasar-dasar teori peluang.

Permainan kartu menyediakan lebih banyak latihan lagi. Ada $\binom{52}{5} = 2{,}598{,}960$ kemungkinan susunan lima kartu di tangan. Susunan yang memuat keempat kartu as sekaligus hanya memerlukan satu kartu lagi yang dipilih dari 48 kartu yang tersisa; karena itu peluangnya $\frac{48}{2{,}598{,}960} = \frac{1}{54{,}145}$.

Kesalahan khas

• Memakai permutasi untuk tim atau panitia; ini menggelembungkan hasil hitungan sebanyak $r!$ kali.
• Lupa bahwa $0! = 1$; akibatnya rumus seperti $\binom{n}{n}$ menjadi rusak.
• Tidak memperhitungkan unsur-unsur yang sama, misalnya pada anagram dengan huruf berulang.
• Mengalikan tahap-tahap yang saling bergantung tanpa menyesuaikan bilangan-bilangan berikutnya.

Kalkulator permutasi dan kombinasi menghitung nilai ${}_nP_r$ dan ${}_nC_r$ melalui faktorial lengkap dengan semua langkahnya, sedangkan kalkulator peluang mengubah bilangan-bilangan ini menjadi peluang.

Segitiga Pascal dan himpunan bagian

Setiap bilangan dalam segitiga Pascal adalah jumlah dua bilangan tepat di atasnya, dan baris ke-$n$ memuat nilai-nilai $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. Baris ke-4 adalah 1, 4, 6, 4, 1; inilah tepat koefisien penjabaran $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$. Aturan pembentukan segitiga itu sendiri juga merupakan hasil penghitungan:

Untuk memahami alasannya, tetapkan satu unsur. Setiap pilihan yang terdiri atas $r$ unsur entah memuatnya, sehingga tinggal memilih $r - 1$ unsur dari $n - 1$ unsur sisanya, entah tidak memuatnya, sehingga seluruh $r$ unsur dipilih dari $n - 1$ unsur sisanya. Jumlah seluruh baris adalah $2^n$, yaitu banyaknya seluruh himpunan bagian dari himpunan dengan $n$ unsur, karena setiap unsur entah masuk entah tidak. Karena itu sebuah kedai pizza dengan 8 jenis topping dapat membuat $2^8 = 256$ pizza berbeda, termasuk pizza tanpa topping sama sekali.

Latihan

1. Dengan berapa cara 4 buku yang dipilih dari 7 buku berbeda dapat disusun di sebuah rak? Penyelesaian: ${}_7P_4 = 7 \times 6 \times 5 \times 4 = 840$.
2. Dengan berapa cara 4 topping dapat dipilih dari 10 topping? Penyelesaian: $\binom{10}{4} = 210$.
3. Berapa banyak anagram berbeda dari kata ANANAS? Penyelesaian: $\frac{6!}{3!\,2!} = 60$.
4. Jika pengulangan diperbolehkan, berapa banyak kode lima huruf yang dapat dibentuk dari 26 huruf? Penyelesaian: $26^5 = 11{,}881{,}376$.

Pertanyaan yang sering diajukan