Kalkulator Permutasi dan Kombinasi

Gunakan pilih atur apabila urutan atau susunan item yang dipilih adalah penting:

• menetapkan kedudukan berkedudukan (tempat pertama, ke-2, ke-3)
• menyusun buku di atas rak
• mencipta kata laluan atau kod PIN
• susunan tempat duduk
• nombor telefon

Gunakan gabungan apabila anda sekadar memilih subset dan urutan tidak relevan:

• memilih ahli pasukan
• memilih nombor loteri
• memilih item menu
• membentuk jawatankuasa

Ujian mudah: jika menukar tempat dua item yang dipilih menghasilkan keputusan yang berbeza, gunakan pilih atur; jika pertukaran itu tidak menjejaskan keputusan, gunakan gabungan.

Nombor loteri mengilustrasikan perkara ini dengan sempurna — cabutan Mega Millions memilih 5 nombor daripada 70 ditambah 1 daripada 25: C(70,5) × 25 = 302,575,350 kemungkinan tiket. Jika urutan diambil kira, terdapat P(70,5) × 25 = 36,309,042,000 kemungkinan — 120 kali ganda lebih banyak.

Pilih atur asas: P(n,r) = n!/(n-r)!. P(10,3) = 10!/7! = 10×9×8 = 720.

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

Dengan ulangan dibenarkan: pilih atur = n^r (contohnya, PIN 4 digit daripada digit 0-9 mempunyai 10⁴ = 10,000 kemungkinan).

Gabungan dengan ulangan: C(n+r-1, r) — memilih 3 cedok daripada 5 perisa aiskrim dengan ulangan dibenarkan memberikan C(7,3) = 35.

Untuk nilai yang besar, gunakan formula pendaraban untuk mengelakkan pengiraan faktorial yang terlalu besar: C(52,5) = (52×51×50×49×48)/(5×4×3×2×1) = 2,598,960 — jumlah kemungkinan daun terup poker 5 kad.

Keselamatan kata laluan: kata laluan 8 aksara yang menggunakan huruf besar, huruf kecil, digit, dan 10 simbol (72 aksara) mempunyai 72⁸ = 722 trilion pilih atur dengan ulangan — mengambil masa kira-kira 22,800 tahun untuk serangan 'brute-force' pada kadar 1 bilion percubaan sesaat. Menambah 2 aksara lagi (kata laluan 10 aksara) meningkatkan jumlah ini kepada 3.7 kuadrilion — 5,140 kali lebih sukar untuk dipecahkan.

• Dalam genetik, bilangan cara memilih 23 pasangan kromosom daripada 46 kromosom ibu bapa ialah C(46,23) ≈ 8.2 bilion, menjelaskan kepelbagaian genetik.
• Dalam kawalan kualiti, memilih 5 item daripada kelompok 100 untuk ujian melibatkan C(100,5) = 75,287,520 kemungkinan sampel.
• Dalam jadual kejohanan, bilangan kemungkinan carta kejohanan NCAA March Madness ialah 2⁶³ ≈ 9.2 kuintilion — itulah sebabnya tiada sesiapa pernah meramal carta yang sempurna dengan tepat.

Sesuatu pilih atur ialah susunan bertertib bagi item, manakala gabungan ialah pilihan tanpa urutan — perbezaan tunggal ini, iaitu urutan, merupakan teras utamanya.

Jika anda memilih huruf A, B, dan C, susunan ABC dan CAB ialah dua pilih atur yang berbeza tetapi merupakan gabungan yang sama, kerana gabungan hanya mengambil kira item mana yang dipilih, bukannya urutannya. Seperti yang dijelaskan oleh Encyclopaedia Britannica, kombinatorik ialah cabang matematik yang khusus untuk mengira susunan dan pilihan sedemikian.

Ujian pantas: tanya sama ada menukar dua item yang dipilih akan mengubah keputusan. Menentukan kedudukan pemenang pingat emas, perak, dan gangsa akan berubah jika anda menukar dua pelari, jadi urutan adalah penting dan anda menggunakan pilih atur. Memilih tiga 'topping' piza tidak berubah jika anda menukar urutannya, jadi anda menggunakan gabungan.

Formula pilih atur ialah nPr = n! / (n − r)! dan formula gabungan ialah nCr = n! / [r! × (n − r)!], di mana n! (faktorial n) ialah hasil darab setiap nombor bulat dari 1 hingga n.

Untuk mencari P(10,3), kira 10! / 7!, yang dipermudahkan menjadi 10 × 9 × 8 = 720. Untuk mencari C(10,3), bahagikan keputusan tersebut dengan 3! = 6, memberikan 120. Faktorial itu sendiri berkembang dengan cepat: 5! = 120 dan 10! = 3,628,800.

Wolfram MathWorld mentakrifkan koefisien binomial C(n,r) tepat dengan cara ini. Oleh kerana nCr membahagikan susunan r! yang dikira secara berasingan oleh pilih atur, nCr sentiasa kurang daripada atau sama dengan nPr untuk nilai n dan r yang sama.

Untuk mengira C(52,5) — bilangan daun terup poker lima kad — mulakan dengan bentuk pendaraban berbanding faktorial penuh untuk memastikan nombor kekal boleh dikendalikan. Tulis pengangka sebagai lima faktor menurun teratas, 52 × 51 × 50 × 49 × 48, dan penyebut sebagai 5! = 120. Pengangka bersamaan dengan 311,875,200; membahagikan dengan 120 menghasilkan tepat 2,598,960 kemungkinan daun terup.

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

Khan Academy mengajar kaedah pembatalan ringkas ini kerana ia mengelakkan pengiraan faktorial yang terlalu besar secara langsung. Perpustakaan Digital Fungsi Matematik NIST (DLMF) memberikan takrifan koefisien binomial yang sama yang digunakan di sini.

Apabila ulangan dibenarkan, formula akan berubah kerana item boleh digunakan semula.

• Bagi pilih atur dengan ulangan, bilangannya ialah n^r: kod PIN 4 digit yang diambil daripada digit 0–9 mempunyai 10^4 = 10,000 kemungkinan, memandangkan setiap satu daripada empat kedudukan mempunyai sepuluh pilihan secara bebas.
• Bagi gabungan dengan ulangan, bilangannya ialah C(n + r − 1, r). Memilih 3 cedok daripada 5 perisa aiskrim apabila ulangan dibenarkan memberikan C(5 + 3 − 1, 3) = C(7,3) = 35.

Bandingkan ini dengan pilihan tanpa ulangan, di mana setiap pilihan mengurangkan jumlah pilihan sebanyak satu. Ulangan meningkatkan jumlah secara mendadak, itulah sebabnya kekuatan kata laluan dan keselamatan PIN bergantung padanya — setiap aksara tambahan mendarabkan kemungkinan yang ada.

Pilih atur dan gabungan muncul di mana-mana sahaja anda mengira susunan atau pilihan.

• Loteri menggunakan gabungan: memilih 6 nombor daripada 49 memberikan C(49,6) = 13,983,816 kemungkinan tiket, yang menentukan kebarangkalian jackpot.
• Permainan kad juga bergantung padanya — terdapat 2,598,960 kemungkinan daun terup poker lima kad daripada dek 52 kad.
• Keselamatan siber menggunakan pilih atur dengan ulangan untuk mengukur berapa banyak kata laluan atau kunci yang mungkin, yang mempengaruhi ketahanan terhadap serangan 'brute-force'.
• Statistik dan kebarangkalian menggunakan koefisien binomial C(n,r) di dalam taburan binomial dan segi tiga Pascal.
• Penjadualan, penetapan pilihan kejohanan, analisis jujukan DNA, dan persampelan kawalan kualiti semuanya bergantung pada pengiraan ini.

Encyclopaedia Britannica mencatatkan bahawa pengiraan kombinatorik menyokong teori kebarangkalian, itulah sebabnya kalkulator ini dipadankan secara semula jadi dengan alat kebarangkalian dan statistik.

Setiap entri dalam segi tiga Pascal ialah koefisien binomial nCr, jadi output gabungan kalkulator secara harfiah membaca nilai daripada segi tiga tersebut. Baris 6 segi tiga Pascal ialah 1, 6, 15, 20, 15, 6, 1 — tepat C(6,0) hingga C(6,6).

Nombor-nombor ini ialah pekali dalam kembangan binomial (a + b)^n, sebab itulah C(n,r) dipanggil koefisien binomial.

Dua identiti berikut secara langsung:

• petua kesimetrian C(n,r) = C(n, n−r), jadi C(15,4) = C(15,11) = 1,365
• petua jumlah bahawa semua pekali dalam baris n apabila dijumlahkan menjadi 2^n, memandangkan 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 OEIS menyenaraikan segi tiga Pascal sebagai jujukan A007318.

• Kesilapan yang paling kerap berlaku ialah memilih alat yang salah: menggunakan pilih atur apabila urutan tidak penting membesarkan jawapan sebanyak faktor r!, kerana nPr mengira setiap kumpulan tidak bertertib r! kali secara berasingan. Sebagai contoh, menganggap jawatankuasa 3 orang daripada 10 orang sebagai bertertib memberikan P(10,3) = 720 berbanding C(10,3) = 120 yang betul.
• Kesilapan kedua ialah lupa sama ada ulangan dibenarkan — PIN mengguna semula digit (n^r), tetapi loteri tidak.
• Kesilapan ketiga ialah keliru antara n dan r, memandangkan formula tidak simetri untuk kedua-duanya.
• Akhir sekali, elakkan mengira faktorial gergasi secara penuh dan kemudian membahagikannya; gunakan kaedah pembatalan supaya nilai pertengahan kekal kecil dan anda dapat mengelakkan ralat 'overflow' atau pembundaran.

Bagi mana-mana n dan r yang tetap, permutasi sentiasa menyamai atau melebihi kombinasi kerana nPr = nCr × r!, dengan faktor tambahan tersebut mengambil kira setiap susunan item yang dipilih.

Apabila r = 1, kedua-duanya adalah sama kerana satu item hanya mempunyai satu susunan: P(20,1) = C(20,1) = 20. Seiring peningkatan r, jurang ini melebar dengan pantas. Dengan n = 10 dan r = 3, P(10,3) = 720 manakala C(10,3) = 120 — bilangan permutasi adalah tepat 3! = 6 kali ganda lebih besar. Jika memilih semua item, P(5,5) = 5! = 120 manakala C(5,5) = 1.

Inilah sebabnya mengapa hasil berperingkat melonjak dengan lebih cepat berbanding pemilihan tanpa urutan, dan mengapa loteri (kombinasi) mempunyai peluang yang jauh lebih baik berbanding jika urutan cabutan mengambil kira. Memahami nisbah ini membantu anda menyemak semula keabsahan sebarang keputusan yang dihasilkan oleh kalkulator.