Memilih formula yang tepat: urutan dan pengulangan
Empat formula penghitungan yang berbeda berlaku tergantung pada dua pertanyaan ya/tidak yang independen: apakah urutan diperhitungkan, dan apakah pengulangan diizinkan?
| Urutan diperhitungkan? | Pengulangan diizinkan? | Formula | Contoh skenario |
|---|---|---|---|
| Ya | Tidak | nPr = n! ÷ (n − r)! | Memberikan juara 1/2/3 di antara 7 pelari |
| Ya | Ya | nʳ | Membuat PIN 3 digit dari digit 0–6, pengulangan diizinkan |
| Tidak | Tidak | nCr = n! ÷ (r!(n−r)!) | Memilih komite 3 orang dari 7 orang |
| Tidak | Ya | C(n+r−1, r) | Memilih 3 scoop dari 7 rasa es krim, pengulangan diizinkan |
- nCr selalu kurang dari atau sama dengan nPr untuk n dan r yang sama (secara spesifik nCr = nPr ÷ r!), karena kombinasi menggabungkan setiap kelompok dari r! urutan item yang sama menjadi satu hitungan.
- Ketika r = 0, baik nPr maupun nCr sama dengan 1 menurut konvensi — ada tepat satu cara untuk memilih nol item (pemilihan kosong).
- Ketika r = n (tanpa pengulangan), nPr = n! dan nCr = 1 — hanya ada satu cara untuk 'memilih' semua n item sebagai himpunan tidak berurutan, tetapi ada n! cara untuk menyusun semuanya secara berurutan.
Apa itu permutasi dan kombinasi?
Permutasi adalah susunan item di mana urutan diperhitungkan. Jumlah permutasi dari r item yang dipilih dari suatu himpunan n item berbeda (tanpa pengulangan) ditulis nPr dan menghitung susunan seperti 'tempat pertama, tempat kedua, tempat ketiga' di mana menukar dua item yang dipilih menghasilkan hasil yang berbeda dan tersendiri.
Kombinasi adalah pemilihan item di mana urutan tidak diperhitungkan. Jumlah kombinasi dari r item yang dipilih dari n item berbeda ditulis nCr (juga disebut 'n choose r' atau koefisien binomial) dan menghitung pengelompokan seperti komite atau satu tangan kartu, di mana himpunan item yang sama dalam urutan yang berbeda dianggap sebagai hasil yang sama.
Pertanyaan kunci yang membedakan keduanya adalah: apakah menyusun ulang item yang sama yang dipilih menghasilkan hasil yang berbeda? Jika ya (misalnya, memberikan medali emas/perak/perunggu, atau menyusun buku di rak), gunakan permutasi. Jika tidak (misalnya, memilih komite 3 orang, atau mengambil satu tangan kartu), gunakan kombinasi. Kalkulator ini juga menampilkan varian 'dengan pengulangan', yang berlaku ketika item yang sama dapat dipilih lebih dari satu kali (misalnya, memilih digit untuk PIN, atau scoop rasa es krim di mana pengulangan diizinkan).
Cara menggunakan kalkulator permutasi dan kombinasi ini
- Masukkan n — jumlah total item berbeda yang tersedia untuk dipilih.
- Masukkan r — jumlah item yang akan dipilih atau disusun. r harus kurang dari atau sama dengan n: jika r lebih besar dari n, kalkulator tidak akan menampilkan hasil sama sekali, termasuk hasil yang mengizinkan pengulangan.
- Baca permutasi (nPr) jika urutan pemilihan diperhitungkan dan pengulangan tidak diizinkan, atau kombinasi (nCr) jika urutan tidak diperhitungkan dan pengulangan tidak diizinkan.
- Untuk skenario yang mengizinkan item yang sama dipilih lebih dari satu kali, gunakan hasil 'dengan pengulangan' alih-alih nilai nPr/nCr standar.
Formula permutasi dan kombinasi
Jumlah permutasi dari r item yang dipilih dari n, tanpa pengulangan, adalah nPr = n! ÷ (n − r)!, yang setara dengan hasil kali r bilangan bulat berurutan menurun yang dimulai dari n. Contoh perhitungan dengan n = 7, r = 3: 7P3 = 7 × 6 × 5 = 210 — jumlah cara untuk memberikan hadiah juara 1, 2, dan 3 yang berbeda di antara 7 peserta.
Jumlah kombinasi dari r item yang dipilih dari n, tanpa pengulangan, adalah nCr = n! ÷ (r! × (n − r)!) = nPr ÷ r!. Ini membagi habis r! cara mengurutkan setiap kelompok yang dipilih, karena kombinasi tidak membedakan urutan. Contoh perhitungan dengan n = 7, r = 3: 7C3 = 210 ÷ 3! = 210 ÷ 6 = 35 — jumlah komite 3 orang berbeda yang dapat dibentuk dari 7 orang.
Permutasi dengan pengulangan yang diizinkan (setiap dari r posisi dapat secara independen berupa salah satu dari n item) adalah cukup nʳ. Untuk n = 7, r = 3: 7³ = 343 — misalnya, jumlah kode 3 digit berbeda menggunakan digit 0–6 jika pengulangan diizinkan. Kombinasi dengan pengulangan yang diizinkan menggunakan formula 'stars and bars': C(n + r − 1, r). Untuk n = 7, r = 3: C(9, 3) = 84 — misalnya, jumlah cara untuk memilih 3 scoop es krim dari 7 rasa ketika rasa yang berulang diizinkan dan urutan tidak diperhitungkan.
Kesalahan umum
- Menggunakan formula permutasi ketika urutan sebenarnya tidak diperhitungkan (atau sebaliknya) — periksa apakah menukar dua item yang dipilih mengubah hasilnya sebelum memilih formula.
- Lupa memeriksa apakah pengulangan diizinkan — 'memilih PIN' (digit dapat berulang) memerlukan formula yang berbeda dari 'membagikan kartu dari satu setumpuk kartu' (tanpa pengulangan, kartu tidak dikembalikan ke tumpukan).
- Menerapkan nPr atau nCr dengan r lebih besar dari n ketika pengulangan tidak diizinkan — ini tidak terdefinisi, karena Anda tidak dapat memilih lebih banyak item berbeda daripada yang ada dalam himpunan tanpa mengulang salah satunya.
- Mengacaukan 'kombinasi dengan pengulangan' (formula stars-and-bars) dengan nCr biasa — keduanya memberikan hasil yang sangat berbeda dan berlaku untuk skenario yang berbeda (pengulangan diizinkan vs. tidak).
Pertanyaan yang sering diajukan
Apa perbedaan antara permutasi dan kombinasi?
Permutasi menghitung susunan di mana urutan diperhitungkan (nPr = n! ÷ (n−r)!) — misalnya, menentukan peringkat juara 1, 2, dan 3. Kombinasi menghitung pemilihan di mana urutan tidak diperhitungkan (nCr = n! ÷ (r!(n−r)!)) — misalnya, memilih komite. Untuk n = 7 dan r = 3: 7P3 = 210 (berurutan), tetapi 7C3 = 35 (tidak berurutan), karena setiap kelompok 3 orang dapat disusun dalam 3! = 6 urutan berbeda, dan 210 ÷ 6 = 35.
Bagaimana cara menghitung nCr (n choose r)?
Gunakan formula nCr = n! ÷ (r! × (n − r)!). Untuk n = 7, r = 3: 7C3 = 7! ÷ (3! × 4!) = 5.040 ÷ (6 × 24) = 5.040 ÷ 144 = 35. Setara dengan itu, hitung nPr terlebih dahulu (7 × 6 × 5 = 210) dan bagi dengan r! (3! = 6): 210 ÷ 6 = 35.
Bagaimana cara menghitung nPr?
Gunakan formula nPr = n! ÷ (n − r)!, yang dapat disederhanakan menjadi hasil kali r bilangan bulat berurutan menurun yang dimulai dari n. Untuk n = 7, r = 3: 7P3 = 7 × 6 × 5 = 210.
Kapan saya harus mengizinkan pengulangan dalam soal permutasi atau kombinasi?
Izinkan pengulangan ketika item yang sama dapat dipilih lebih dari satu kali dalam satu hasil — misalnya, digit dalam kode PIN, atau rasa es krim ketika pelanggan dapat memilih rasa yang sama untuk beberapa scoop. Jangan izinkan pengulangan ketika setiap item hanya dapat digunakan satu kali — misalnya, membagikan kartu remi yang berbeda, atau menugaskan orang yang berbeda ke peran tertentu.
Berapa nPr ketika r sama dengan n?
Ketika r = n (menyusun semua n item tanpa pengulangan), nPr dapat disederhanakan menjadi n! ÷ (n − n)! = n! ÷ 0! = n! ÷ 1 = n!. Ini merepresentasikan jumlah total cara untuk menyusun semua n item berbeda dalam satu baris — misalnya, 5 item dapat disusun sepenuhnya dalam 5! = 120 cara.
Apa arti 'stars and bars' untuk kombinasi dengan pengulangan?
'Stars and bars' adalah teknik kombinatorika standar untuk menghitung kombinasi dengan pengulangan yang diizinkan, menghasilkan formula C(n + r − 1, r). Teknik ini bekerja dengan merepresentasikan r item yang dipilih sebagai 'bintang' yang dipisahkan oleh 'batang' yang menandai batas antara n kategori, lalu menghitung susunan bintang dan batang tersebut. Untuk n = 7, r = 3: C(9, 3) = 84.
Referensi
- Rosen KH. Discrete Mathematics and Its Applications. 8th ed. McGraw-Hill, 2018. (Permutations, combinations, and the stars-and-bars method.)
- NIST Digital Library of Mathematical Functions (DLMF), §26.1–26.3 Combinatorial Analysis. dlmf.nist.gov.
- Feller W. An Introduction to Probability Theory and Its Applications, Vol. 1. 3rd ed. Wiley, 1968. (Classic treatment of permutations and combinations.)