Kalkulator Permutasi dan Kombinasi

Gunakan permutasi ketika urutan atau susunan item yang dipilih itu penting:

• menetapkan posisi berjenjang (juara 1, 2, 3)
• menyusun buku di rak
• membuat kata sandi atau kode PIN
• susunan tempat duduk
• nomor telepon

Gunakan kombinasi ketika Anda hanya memilih subhimpunan dan urutan tidak relevan:

• memilih anggota tim
• memilih nomor lotre
• memilih item menu
• membentuk komite

Uji yang membantu: jika menukar dua item yang dipilih menciptakan hasil yang berbeda, gunakan permutasi; jika pertukaran tersebut tidak masalah, gunakan kombinasi.

Nomor lotre mengilustrasikannya dengan sempurna — undian Mega Millions memilih 5 nomor dari 70 ditambah 1 dari 25: C(70,5) × 25 = 302.575.350 tiket yang mungkin. Jika urutan penting, akan ada P(70,5) × 25 = 36.309.042.000 kemungkinan — 120 kali lebih banyak.

Permutasi dasar: P(n,r) = n!/(n-r)!. P(10,3) = 10!/7! = 10×9×8 = 720.

Kombinasi dasar: C(n,r) = n!/[r!(n-r)!]. C(10,3) = 10!/(3!×7!) = 720/6 = 120.

Dengan pengulangan yang diizinkan: permutasi = n^r (misalnya, PIN 4 digit dari digit 0-9 memiliki 10⁴ = 10.000 kemungkinan).

Kombinasi dengan pengulangan: C(n+r-1, r) — memilih 3 sendok dari 5 rasa es krim dengan pengulangan yang diizinkan memberikan C(7,3) = 35.

Untuk nilai yang besar, gunakan rumus perkalian untuk menghindari penghitungan faktorial yang besar: C(52,5) = (52×51×50×49×48)/(5×4×3×2×1) = 2.598.960 — jumlah tangan poker 5 kartu yang mungkin.

Keamanan kata sandi: kata sandi 8 karakter menggunakan huruf besar, huruf kecil, digit, dan 10 simbol (72 karakter) memiliki 72⁸ = 722 triliun permutasi dengan pengulangan — memerlukan serangan brute-force sekitar 22.800 tahun pada 1 miliar percobaan per detik. Menambahkan hanya 2 karakter lagi (kata sandi 10 karakter) meningkatkan ini menjadi 3,7 kuadriliun — 5.140 kali lebih sulit untuk diretas.

• Dalam genetika, jumlah cara untuk memilih 23 pasang kromosom dari 46 kromosom orang tua adalah C(46,23) ≈ 8,2 miliar, menjelaskan keragaman genetik.
• Dalam pengendalian kualitas, memilih 5 item dari sekumpulan 100 untuk pengujian melibatkan C(100,5) = 75.287.520 sampel yang mungkin.
• Dalam bagan turnamen, jumlah kemungkinan bagan NCAA March Madness adalah 2⁶³ ≈ 9,2 kuintiliun — itulah sebabnya tidak seorang pun pernah berhasil memprediksi bagan yang sempurna secara akurat.

Sebuah permutasi adalah susunan item yang berurutan, sedangkan kombinasi adalah pilihan yang tidak berurutan — satu perbedaan tunggal itu, urutan, adalah inti keseluruhannya.

Jika Anda memilih huruf A, B, dan C, susunan ABC dan CAB adalah dua permutasi yang berbeda tetapi kombinasi yang sama, karena kombinasi hanya peduli item mana yang dipilih, bukan urutannya. Seperti yang dijelaskan Encyclopaedia Britannica, kombinatorika adalah cabang matematika yang dikhususkan untuk menghitung susunan dan pilihan tersebut.

Uji cepat: tanyakan apakah menukar dua item yang dipilih mengubah hasilnya. Memperingkatkan peraih medali emas, perak, dan perunggu berubah jika Anda menukar dua pelari, sehingga urutan penting dan Anda menggunakan permutasi. Memilih tiga topping pizza tidak berubah jika Anda menukarnya, sehingga Anda menggunakan kombinasi.

Rumus permutasi adalah nPr = n! / (n − r)! dan rumus kombinasi adalah nCr = n! / [r! × (n − r)!], di mana n! (n faktorial) adalah produk dari setiap bilangan bulat dari 1 hingga n.

Untuk mencari P(10,3), hitung 10! / 7!, yang disederhanakan menjadi 10 × 9 × 8 = 720. Untuk mencari C(10,3), bagi hasil tersebut dengan 3! = 6, menghasilkan 120. Faktorial itu sendiri tumbuh dengan cepat: 5! = 120 dan 10! = 3.628.800.

Wolfram MathWorld mendefinisikan koefisien binomial C(n,r) persis dengan cara ini. Karena nCr membagi urutan r! yang dihitung secara terpisah oleh permutasi, nCr selalu kurang dari atau sama dengan nPr untuk n dan r yang sama.

Untuk menghitung C(52,5) — jumlah tangan poker lima kartu — mulailah dengan bentuk perkalian alih-alih faktorial penuh agar angka tetap dapat dikelola. Tulis pembilang sebagai lima faktor menurun teratas, 52 × 51 × 50 × 49 × 48, dan penyebut sebagai 5! = 120. Pembilang sama dengan 311.875.200; membagi dengan 120 memberikan tepat 2.598.960 tangan yang mungkin.

Untuk pemeriksaan yang lebih kecil, C(5,2) = (5 × 4) / (2 × 1) = 10, dan C(8,3) = (8 × 7 × 6) / (3 × 2 × 1) = 56.

Khan Academy mengajarkan jalan pintas pencoretan ini karena menghindari penghitungan faktorial yang sangat besar secara langsung. NIST Digital Library of Mathematical Functions (DLMF) memberikan definisi koefisien binomial yang sama seperti yang digunakan di sini.

Ketika pengulangan diizinkan, rumus berubah karena item dapat digunakan kembali.

• Untuk permutasi dengan pengulangan, jumlahnya secara sederhana adalah n^r: PIN 4 digit yang ditarik dari digit 0–9 memiliki 10^4 = 10.000 kemungkinan, karena masing-masing dari keempat posisi secara independen memiliki sepuluh pilihan.
• Untuk kombinasi dengan pengulangan, jumlahnya adalah C(n + r − 1, r). Memilih 3 sendok dari 5 rasa es krim ketika pengulangan diizinkan memberikan C(5 + 3 − 1, 3) = C(7,3) = 35.

Kontraskan ini dengan pemilihan tanpa pengulangan, di mana setiap pilihan mengurangi kumpulan sebanyak satu. Pengulangan secara drastis meningkatkan total, itulah sebabnya kekuatan kata sandi dan keamanan PIN mengandalkannya — setiap karakter yang ditambahkan mengalikan kemungkinan.

Permutasi dan kombinasi muncul di mana pun Anda menghitung susunan atau pilihan.

• Lotre menggunakan kombinasi: memilih 6 nomor dari 49 memberikan C(49,6) = 13.983.816 tiket yang mungkin, yang menentukan peluang jackpot.
• Permainan kartu juga mengandalkannya — ada 2.598.960 kemungkinan tangan poker lima kartu dari dek berisi 52 kartu.
• Keamanan siber menggunakan permutasi dengan pengulangan untuk mengukur berapa banyak kata sandi atau kunci yang mungkin, yang secara langsung mendorong ketahanan terhadap brute-force.
• Statistik dan probabilitas menggunakan koefisien binomial C(n,r) di dalam distribusi binomial dan segitiga Pascal.
• Penjadwalan, penentuan unggulan turnamen, analisis urutan DNA, dan pengambilan sampel pengendalian kualitas semuanya bergantung pada hitungan ini.

Encyclopaedia Britannica mencatat bahwa penghitungan kombinatorial mendasari teori probabilitas, itulah sebabnya kalkulator ini berpasangan secara alami dengan alat probabilitas dan statistik.

Setiap entri dalam Segitiga Pascal adalah koefisien binomial nCr, sehingga keluaran kombinasi kalkulator secara harfiah membaca nilai dari segitiga tersebut. Baris ke-6 dari Segitiga Pascal adalah 1, 6, 15, 20, 15, 6, 1 — persis C(6,0) hingga C(6,6).

Angka-angka ini adalah koefisien dalam ekspansi binomial (a + b)^n, itulah sebabnya C(n,r) disebut koefisien binomial.

Dua identitas mengikutinya secara langsung:

• aturan simetri C(n,r) = C(n, n−r), sehingga C(15,4) = C(15,11) = 1.365
• aturan jumlah bahwa semua koefisien pada baris n menjumlahkan hingga 2^n, karena C(4,0)+C(4,1)+C(4,2)+C(4,3)+C(4,4) = 1+4+6+4+1 = 16 = 2^4

Wolfram MathWorld dan katalog OEIS mencatat Segitiga Pascal sebagai barisan A007318.

• Kesalahan yang paling sering terjadi adalah memilih alat yang salah: menggunakan permutasi ketika urutan tidak penting melambungkan jawaban sebesar faktor r!, karena nPr menghitung setiap kelompok yang tidak berurutan sebanyak r! kali secara terpisah. Sebagai contoh, memperlakukan komite 3 orang dari 10 orang sebagai hal yang berurutan menghasilkan P(10,3) = 720 alih-alih C(10,3) = 120 yang benar.
• Kesalahan kedua adalah lupa apakah pengulangan diizinkan — PIN menggunakan ulang digit (n^r), tetapi lotre tidak.
• Kesalahan ketiga adalah salah membedakan n dan r, karena rumusnya tidak simetris terhadap keduanya.
• Terakhir, hindari menghitung faktorial raksasa secara penuh lalu membaginya; gunakan metode pencoretan agar nilai menengah tetap kecil dan Anda menghindari limpahan (overflow) atau kesalahan pembulatan.

Untuk nilai n dan r apa pun yang tetap, permutasi selalu sama dengan atau melebihi kombinasi karena nPr = nCr × r!, faktor ekstra yang memperhitungkan setiap susunan dari item yang dipilih.

Ketika r = 1 keduanya bernilai sama, karena satu item tunggal hanya memiliki satu pengaturan: P(20,1) = C(20,1) = 20. Seiring bertambahnya r, selisihnya melebar dengan cepat. Dengan n = 10 dan r = 3, P(10,3) = 720 tetapi C(10,3) = 120 — jumlah permutasi tepat 3! = 6 kali lipat lebih besar. Saat memilih semua item, P(5,5) = 5! = 120 sedangkan C(5,5) = 1.

Inilah sebabnya mengapa hasil yang berperingkat melonjak jumlahnya lebih cepat daripada pemilihan yang tidak berurutan, dan mengapa lotere (kombinasi) memiliki peluang yang jauh lebih baik daripada jika urutan pengundian dihitung. Memahami rasio ini membantu Anda memeriksa kewarasan hasil apa pun yang dikembalikan oleh kalkulator.