Permutasi dan kombinasi, berbagai cara di mana objek dari himpunan dapat dipilih, umumnya tanpa penggantian, untuk membentuk himpunan bagian. Pilihan himpunan bagian ini disebut permutasi ketika urutan seleksi adalah faktor, kombinasi ketika urutan bukan merupakan faktor. Dengan mempertimbangkan rasio jumlah himpunan bagian yang diinginkan dengan jumlah semua himpunan bagian yang mungkin untuk banyak permainan kesempatan di abad ke-17, ahli matematika Prancis Blaise Pascal dan Pierre de Fermat memberikan dorongan untuk pengembangan kombinatorik dan teori probabilitas.
kombinatorik: koefisien binomial
n objek disebut permutasi dari n hal yang diambil r pada suatu waktu. Jumlah permutasi adalah
Konsep dan perbedaan antara permutasi dan kombinasi dapat diilustrasikan dengan memeriksa semua cara yang berbeda di mana sepasang objek dapat dipilih dari lima objek yang dapat dibedakan — seperti huruf A, B, C, D, dan E. Jika keduanya surat-surat yang dipilih dan urutan seleksi dipertimbangkan, maka 20 hasil berikut dimungkinkan:
Masing-masing dari 20 pilihan yang berbeda ini disebut permutasi. Secara khusus, mereka disebut permutasi dari lima objek yang diambil dua sekaligus, dan jumlah permutasi tersebut mungkin dilambangkan dengan simbol 5 P 2, baca “5 permute 2.” Secara umum, jika ada n objek yang tersedia untuk dipilih, dan permutasi (P) harus dibentuk menggunakan k dari objek pada suatu waktu, jumlah permutasi yang berbeda mungkin dilambangkan dengan simbol n P k. Rumus untuk evaluasinya adalah n P k = n! / (N - k)! Ungkapan n! —Baca “n factorial” —menunjukkan bahwa semua bilangan bulat positif berturut-turut dari 1 hingga dan termasuk n harus dikalikan bersama, dan 0! didefinisikan sama dengan 1. Misalnya, menggunakan rumus ini, jumlah permutasi dari lima objek yang diambil dua sekaligus adalah
(Untuk k = n, n P k = n! Jadi, untuk 5 objek ada 5! = 120 pengaturan.)
Untuk kombinasi, objek k dipilih dari serangkaian objek n untuk menghasilkan himpunan bagian tanpa memesan. Berbeda dengan contoh permutasi sebelumnya dengan kombinasi yang sesuai, himpunan bagian AB dan BA bukan lagi pilihan yang berbeda; dengan menghilangkan kasus-kasus seperti itu, hanya ada 10 himpunan bagian yang mungkin — AB, AC, AD, AE, BC, BD, BE, CD, CE, dan DE.
Jumlah subset tersebut dilambangkan dengan n C k, baca “n pilih k.” Untuk kombinasi, karena k objek memiliki k! pengaturan, ada k! permutasi yang tidak dapat dibedakan untuk setiap pilihan objek k; karenanya membagi rumus permutasi dengan k! menghasilkan rumus kombinasi berikut:
Ini sama dengan koefisien binomial (n, k) (lihat teorema binomial). Sebagai contoh, jumlah kombinasi dari lima objek yang diambil dua sekaligus adalah
Rumus untuk n P k dan n C k disebut rumus penghitungan karena rumus tersebut dapat digunakan untuk menghitung jumlah kemungkinan permutasi atau kombinasi dalam situasi tertentu tanpa harus membuat daftar semuanya.
