Permutasi dan kombinasi, berbagai cara di mana objek dari satu set dapat dipilih, umumnya tanpa penggantian, untuk membentuk subset. Pemilihan subset ini disebut permutasi apabila urutan pemilihan adalah faktor, gabungan ketika pesanan bukan faktor. Dengan mempertimbangkan nisbah jumlah subset yang diinginkan dengan jumlah semua kemungkinan subset untuk banyak peluang permainan pada abad ke-17, ahli matematik Perancis Blaise Pascal dan Pierre de Fermat memberi dorongan kepada pengembangan teori kombinatorik dan kebarangkalian.
kombinatorik: Pekali binomial
objek n dipanggil permutasi dari n benda yang diambil pada satu masa. Jumlah permutasi adalah
Konsep dan perbezaan antara permutasi dan kombinasi dapat digambarkan dengan memeriksa semua cara yang berbeza di mana sepasang objek dapat dipilih dari lima objek yang dapat dibezakan - seperti huruf A, B, C, D, dan E. Jika kedua-duanya huruf yang dipilih dan urutan pemilihan dipertimbangkan, maka kemungkinan 20 hasil berikut:
Setiap 20 pilihan yang berbeza ini disebut permutasi. Secara khusus, mereka disebut permutasi dari lima objek yang diambil dua pada satu masa, dan jumlah permutasi sedemikian mungkin dilambangkan dengan simbol 5 P 2, baca "5 permute 2." Secara umum, jika ada n objek yang tersedia untuk dipilih, dan permutasi (P) akan dibentuk menggunakan k objek pada satu waktu, jumlah permutasi yang berbeza mungkin ditunjukkan dengan simbol n P k. Formula untuk penilaiannya adalah n P k = n! / (N - k)! Ungkapan n! —Baca “n faktorial” —menunjukkan bahawa semua bilangan bulat positif berturut-turut dari 1 hingga dan termasuk n harus dikalikan bersama, dan 0! ditakrifkan sama dengan 1. Contohnya, dengan menggunakan formula ini, bilangan permutasi lima objek yang diambil dua pada satu masa adalah
(Untuk k = n, n P k = n! Oleh itu, untuk 5 objek terdapat 5! = 120 susunan.)
Untuk kombinasi, objek k dipilih dari sekumpulan objek n untuk menghasilkan subset tanpa membuat pesanan. Berbeza dengan contoh permutasi sebelumnya dengan kombinasi yang sesuai, subset AB dan BA bukan lagi pilihan yang berbeza; dengan menghilangkan kes seperti itu, hanya ada 10 subset yang mungkin berbeza - AB, AC, AD, AE, BC, BD, BE, CD, CE, dan DE.
Bilangan subset tersebut dilambangkan dengan n C k, baca "n pilih k." Untuk kombinasi, kerana objek k mempunyai k! pengaturan, ada k! permutasi yang tidak dapat dibezakan untuk setiap pilihan objek k; oleh itu membahagikan formula permutasi dengan k! menghasilkan formula gabungan berikut:
Ini sama dengan pekali binomial (n, k) (lihat teorem binomial). Sebagai contoh, jumlah gabungan lima objek yang diambil dua pada satu masa adalah
Rumus untuk n P k dan n C k disebut formula penghitungan kerana ia dapat digunakan untuk menghitung jumlah kemungkinan permutasi atau kombinasi dalam situasi tertentu tanpa harus menyenaraikan semuanya.
