Proposisi 2.9.
Jika \(n\) dan \(k\) merupakan bilangan bulat dengan \(0\le k\le n\text{,}\) maka
\begin{equation*}
\binom{n}{k}=C(n,k)=\frac{P(n,k)}{k!}=\frac{n!}{k!(n-k)!}
\end{equation*}
Subbab 2.3 Kombinasi
Untuk memotivasi topik bagian ini, kita akan membahas variasi lain dari soal pemilihan pengurus dalam Contoh 2.7. Andaikan kelas tersebut tidak memilih mahasiswa untuk jabatan tertentu, tetapi memilih dewan eksekutif beranggotakan empat mahasiswa dari \(80\) mahasiswa yang tersedia. Setiap posisi dalam dewan eksekutif itu setara, sehingga tidak ada perbedaan antara Alice memperoleh kursi “pertama” dan memperoleh kursi “keempat” dalam dewan tersebut. Dengan kata lain, kita hanya ingin memilih empat dari \(80\) mahasiswa tanpa memperhatikan urutan. Kita akan kembali ke pertanyaan ini setelah memperkenalkan konsep berikutnya.
Misalkan \(X\) sebuah himpunan berhingga dan \(k\) sebuah bilangan bulat dengan \(0\le k\le |X|\text{.}\) Himpunan bagian beranggota \(k\) dari \(X\) juga disebut kombinasi berukuran \(k\text{.}\) Jika \(|X| =n\text{,}\) banyaknya himpunan bagian beranggota \(k\) dari \(X\) dinyatakan dengan \(\binom{n}{k}\text{.}\) Bilangan berbentuk \(\binom{n}{k}\) disebut koefisien binomial, dan banyak ahli kombinatorika membaca \(\binom{n}{k}\) sebagai “\(n\) pilih \(k\text{.}\)” Ketika kita memerlukan bentuk sebaris, notasi yang diutamakan adalah \(C(n,k)\). Besaran \(C(n,k)\) juga disebut banyaknya kombinasi dari \(n\) objek yang diambil \(k\) sekaligus.
Bob mencatat bahwa dengan notasi ini, banyaknya cara memilih dewan eksekutif beranggotakan empat orang dari \(80\) mahasiswa yang berminat adalah \(C(80,4)\text{.}\) Namun, ia bingung tentang cara menghitung nilai \(C(80,4)\text{.}\) Alice menunjukkan bahwa nilainya pasti lebih kecil daripada \(P(80,4)\text{,}\) karena setiap dewan eksekutif dapat diubah menjadi \(4!\) susunan pengurus yang berbeda. Carlos setuju dan mengatakan bahwa Alice telah menemukan gagasan kunci untuk memperoleh rumus yang menghitung \(C(n,k)\) secara umum.
Bukti.
Jika \(X\) merupakan himpunan beranggota \(n\text{,}\) maka \(P(n,k)\) menghitung banyaknya permutasi atas \(X\) dengan panjang \(k\text{.}\) Masing-masing dari \(C(n,k)\) himpunan bagian beranggota \(k\) dari \(X\) dapat diubah menjadi \(k!\) permutasi, dan cara ini memperhitungkan setiap permutasi tepat satu kali. Oleh karena itu, \(k! C(n,k)=P(n,k)\text{,}\) dan pembagian dengan \(k!\) menghasilkan rumus untuk banyaknya himpunan bagian beranggota \(k\text{.}\)
Dengan menggunakan Proposisi 2.9, sekarang kita dapat menentukan bahwa \(C(80,4)=1581580\) adalah banyaknya cara memilih dewan eksekutif beranggotakan empat orang dari \(80\) mahasiswa yang berminat.
Argumen di atas menggambarkan strategi pencacahan kombinatorial yang umum. Kita menghitung satu jenis objek dan menentukan bahwa setiap objek yang sebenarnya ingin kita hitung telah terhitung berlebih dalam jumlah yang sama, sehingga kita membagi hasilnya dengan jumlah tersebut (dalam kasus ini, \(k!\)).
Hasil berikut setara dengan mengatakan bahwa memilih elemen-elemen yang akan menjadi anggota suatu himpunan (pemenang pemilihan dewan eksekutif) sama dengan memilih elemen-elemen yang tidak akan dimasukkan (pihak yang kalah dalam pemilihan).
Proposisi 2.10.
Untuk semua bilangan bulat \(n\) dan \(k\) dengan \(0\le k\le n\text{,}\) berlaku
\begin{equation*}
\binom{n}{k}=\binom{n}{n-k}.
\end{equation*}
Contoh 2.11.
Sebuah restoran di wilayah Selatan Amerika Serikat mencantumkan 21 hidangan dalam kategori “sayuran” pada menunya. (Seperti restoran khas Selatan yang baik, makaroni dan keju merupakan salah satu pilihan sayuran.) Restoran itu menjual hidangan sayuran yang berisi empat pilihan sayuran berbeda dari menu. Karena urutan penempatan sayuran di piring tidak penting, terdapat \(C(21,4)=5985\) cara berbeda bagi pelanggan untuk memesan hidangan sayuran di restoran tersebut.
Contoh berikutnya memperkenalkan korespondensi penting antara himpunan dan string bit yang akan berulang kali kita manfaatkan dalam buku ini.
Contoh 2.12.
Misalkan \(n\) sebuah bilangan bulat positif dan \(X\) sebuah himpunan beranggota \(n\text{.}\) Terdapat korespondensi satu-ke-satu yang alami antara himpunan-himpunan bagian dari \(X\) dan string bit dengan panjang \(n\text{.}\) Secara lebih tepat, misalkan \(X=\{x_1,x_2,\dots,x_n\}\text{.}\) Suatu himpunan bagian \(A\subseteq X\) berkorespondensi dengan string \(s\text{,}\) dengan \(s(i) = 1\) jika dan hanya jika \(x_i\in A\text{.}\) Sebagai contoh, jika \(X=\{a,b,c,d,e,f,g,h\}\text{,}\) maka himpunan bagian \(\{b,c,g\}\) berkorespondensi dengan string bit \(01100010\text{.}\) Terdapat \(C(8,3)=56\) string bit dengan panjang delapan yang memuat tepat tiga karakter \(1\text{.}\) Dengan memikirkan korespondensi ini, berapakah jumlah seluruh himpunan bagian dari sebuah himpunan beranggota \(n\text{?}\)
