Kombinatorika Partisi Aljabar

Akar Formal Rumus Kombinasi

Kombinasi $C(n,r)$ diturunkan dengan membagi permutasi $P(n,r)$ dengan $r!$ untuk menghilangkan perhitungan elemen yang sekadar bertukar posisi.

Secara formal, permutasi $P(n,r)$ menyatakan banyaknya cara memilih sekaligus mengurutkan $r$ elemen berbeda dari himpunan berukuran $n$:

$$P(n,r) = \frac{n!}{(n-r)!} = n(n-1)\dots(n-r+1)$$

Namun, dalam sebuah himpunan bagian (subset) berukuran $r$, urutan penulisan anggota di dalamnya sama sekali tidak mengubah identitas himpunan tersebut. Berdasarkan prinsip perkalian, untuk setiap himpunan yang memuat $r$ elemen, ada tepat $r!$ cara untuk menata urutan internal anggotanya. Karena setiap himpunan terhitung sebanyak $r!$ kali dalam ruang permutasi, kita harus mereduksi multiplisitas ini melalui pembagian aljabar:

$$C(n,r) = \frac{P(n,r)}{r!} = \frac{n!}{r!(n-r)!}$$

Diagram pengelompokan permutasi P 3,2 menjadi kombinasi C 3,2 dengan reduksi 2 faktorial.

Sebagai ilustrasi, jika kita memilih $2$ elemen dari himpunan $\{A, B, C\}$, ruang permutasi $P(3,2) = \frac{3!}{(3-2)!} = 6$ menghasilkan susunan terurut: $(A,B), (B,A), (A,C), (C,A), (B,C),$ dan $(C,B)$. Karena pasangan $(A,B)$ dan $(B,A)$ membentuk himpunan yang sama yaitu $\{A, B\}$, pembagian dengan $2! = 2$ mereduksi $6$ susunan terurut tadi menjadi tepat $C(3,2) = 3$ himpunan tak terurut unik.

Definisi Batas Kardinalitas

Analisis sistem kombinatorik formal mewajibkan pengurangan ruang sampel jika terdapat syarat atau elemen tetap pada wadah tujuan.

Pada permasalahan distribusi kendaraan, total himpunan individu yang bepergian adalah $8$ orang. Akan tetapi, tepat $2$ orang di antaranya telah ditetapkan sebagai pemilik mobil sekaligus pengemudi utama. Karena posisi pengemudi telah terkunci pada masing-masing kendaraan, kita harus mengeluarkan kedua elemen tersebut dari ruang pemilihan bebas. Kardinalitas penumpang yang benar-benar harus dipartisi ke dalam mobil adalah:

$$\text{Jumlah penumpang} = 8 - 2 = 6\text{ orang}$$

Fakta formal ini membuktikan kebenaran Opsi A.

Selanjutnya, tinjau batas kapasitas wadah. Informasi soal menyatakan kapasitas maksimum kendaraan adalah $5$ orang, sudah termasuk pengemudi di dalamnya. Karena $1$ kursi pada setiap mobil secara permanen dialokasikan untuk pengemudi tetap, sisa kapasitas efektif yang tersedia untuk penumpang di setiap wadah adalah:

$$\text{Kapasitas maksimal penumpang} = 5 - 1 = 4\text{ orang}$$

Partisi ke Sel Terbedakan

Membagi himpunan ke wadah berlabel (terbedakan) berarti kita cukup mengalikan kombinasi tiap wadah secara berurutan tanpa pembagian tambahan.

Dua kendaraan pada skenario ini merupakan wadah terbedakan (distinct containers) karena dikemudikan oleh dua pemilik yang berbeda (kita dapat menamainya Mobil A dan Mobil B). Untuk membagi $6$ penumpang ke dua wadah ini, kita mengevaluasi kasus-kasus distribusi yang memenuhi batas kapasitas maksimal ($4$ penumpang per mobil).

Untuk skenario distribusi $(2, 4)$—yakni Mobil A memuat $2$ orang dan Mobil B memuat $4$ orang—proses pemilihan berlangsung dalam dua tahap bertingkat:

  1. Memilih $2$ dari $6$ penumpang untuk Mobil A: $C(6,2) = \frac{6 \times 5}{2 \times 1} = 15$ cara.

  2. Mengalokasikan sisa $4$ penumpang ke Mobil B: $C(4,4) = 1$ cara.

Berdasarkan aturan perkalian:

$$\text{Banyak cara } (2,4) = C(6,2) \times C(4,4) = 15 \times 1 = 15\text{ cara}$$

Hasil ini membuktikan bahwa Opsi C bernilai benar.

Sementara itu, untuk skenario distribusi simetris $(3, 3)$—Mobil A memuat $3$ orang dan Mobil B memuat $3$ orang—banyak caranya dihitung dengan:

$$C(6,3) \times C(3,3) = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} \times 1 = 20 \times 1 = 20\text{ cara}$$