Kombinasi Tanpa Perulangan Objek

Pada postingan ini kita diskusikan konsep kombinasi tanpa perulangan objek dan hubungannya dengan konsep permutasi tanpa perulangan objek. Kita mulai diskusi kita dengan definisi formal dari kombinasi.
Lambang kombinasi $n$ atas $r$ unsur adalah $$C^n_r$$ atau $$C(n,~r)$$ atau $${n \choose r}.$$

Andaikan $r$ dan $n$ adalah bilangan bulat sehingga $0 \le r \le n$. Sebuah $r$-kombinasi atas sebuah himpunan dengan $n$ objek adalah susunan $r$ objek atas $n$ objek yang dilakukan tanpa memperhatikan urutan objek yang muncul.

Bila $S$ adalah sebuah himpunan, maka sebuah $r$-kombinasi atas $S$ dapat dipandang sebagai sebuah himpunan bagian dari $S$ yang terdiri atas $r$ objek.
Jika $S$ = {a, b, c, d}, maka abc, abd, acd, abd adalah 4 buah 3-kombinasi dari $S$.
Rumus kombinasi:

Untuk $0 \le r \le n$, maka $$C^n_r=\frac{n!}{r!.(n-r)!}$$

Contoh-1:
Pada sebuah lingkaran diletakkan $n$ buah titik. Tentukan banyaknya segitiga yang dapat dibentuk dari $n$ buah titik tersebut.
Solusi. Karena tidak terdapat 3 titik yang kolinier, maka setiap tiga titik akan membentuk sebuah segitiga. Sehingga banyaknya segitiga yang dapat dibentuk adalah $C(n,~3)$ buah.

Contoh-2:
Tentukan banyaknya untaian digit biner dengan panjang $n$ yang ter diri dari $r \le n$ buah digit 0.
Solusi. Perhatikan bahwa penentuan sebuah untaian digit biner dengan panjang $n$ yang memuat $r$ buah digit 0, hanya bergantung pada letak posisi dimana digit 0 berada. Sehingga persoalan penen tuan banyaknya untaian digit biner dengan panjang $n$ yang memuat $r$ digit 0 adalah persoalan kombinasi. Akibatnya banyaknya untaian digit biner dengan panjang $n$ yang terdiri atas $r$ buah bit 0 adalah sebanyak $\displaystyle n \choose r$.
Perhatikan bahwa setiap untaian digit biner dengan panjang $n$ yang terdiri atas $r$ buah digit 0 juga merupakan untaian digit biner yang terdiri atas $(n − r)$ buah digit 1. Sehingga banyaknya untaian digit biner dengan panjang n yang terdiri atas $r$ buat digit 0 adalah sama dengan banyaknya untaian digit biner dengan panjang $n$ yang terdiri atas $(n−r)$ buah digit 1. Karena banyaknya untaian digit biner dengan panjang $n$ yang terdiri atas $(n − r)$ buah digit 1 adalah $\displaystyle n \choose {n-r}$. maka kita telah memperlihatkan bahwa $${n \choose r}={n \choose {n-r}}$$.
Contoh-3:
Tentukan banyaknya himpunan bagian dari X = {1, 2, 3, . . . , 20} yang terdiri atas 3 unsur sehingga hasil kali ketiga unsur tersebut habis dibagi oleh 4.
Solusi. Perhatikan bahwa syarat utama dari himpunan bagian yang diinginkan adalah hasil kali ketiga unsur habis dibagi empat. Kita partisi persoalan berdasarkan ciri hasil kali tiga bilangan dalam bentuk abc habis dibagi 4.
- Himpunan bagian terdiri dari satu bilangan genap dan dua ganjil. Agar hasil kali ketiga bilangan habis dibagi 4, maka bilangan genap yang diinginkan haruslah kelipatan 4. Terdapat 10 bilangan ganjil di X, sehingga terdapat $C^{10}_2$ cara untuk memilih dua bilangan ganjil. Terdapat 5 bilangan kelipatan 4 di X, sehingga terdapat $C^5_1$ cara untuk memilih satu bilangan genap kelipatan 4. Oleh prinsip perkalian terdapat $C^5_1.C^{10}_2$ himpunan bagian pada kasus ini.
- Himpunan bagian terdiri dari dua bilangan genap dan satu bilangan ganjil. Karena terdapat 10 bilangan genap, maka terdapat $C^{10}_2$ cara memilih dua bilangan genap. Karena terdapat 10 bilangan ganjil di X, maka terdapat $C^{10}_1$ cara memilih sebuah bilangan ganjil di X. Oleh prinsip perkalian terdapat sebanyak $C^{10}_2.C^{10}_1$ himpunan bagian.
- Himpunan bagian terdiri dari tiga bilangan genap. Terdapat $C^{10}_3$ himpunan bagian.

Oleh prinsip penjumlahan terdapat $C^5_1.C^{10}_2$ + $C^{10}_2.C^{10}_1$ + $C^{10}_3$ = 795 himpunan bagian yang terdiri dari 3 unsur dan hasil kali ketiga unsur tersebut habis dibagi 4.

Demikianlah materi tentang kombinasi tanpa perulangan objek. Sampai jumpa dan semoga bermanfaat.