Pengaturan Benda Identik dan Berbeda (Multiset & Stars and Bars)

Dalam banyak kasus, kita bekerja dengan koleksi objek di mana beberapa objek tidak dapat dibedakan satu sama lain. Koleksi seperti ini disebut sebagai multiset.

1. Permutasi Multiset

Definisi (Multiset)

Sebuah multiset $S$ dapat direpresentasikan sebagai ${n_{1} \cdot a_{1}, n_{2} \cdot a_{2}, \dots, n_{k} \cdot a_{k}}$ , di mana $a_{i}$ adalah jenis objek dan $n_{i}$ adalah jumlah kemunculan (multiplisitas) dari objek tersebut. Total anggota multiset adalah $n = \sum_{i = 1}^{k} n_{i}$ .

Banyaknya cara menyusun seluruh anggota multiset $S$ secara linear adalah:

$\frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}$

2. Kombinasi Multiset (Metode Stars and Bars)

Seringkali kita diminta memilih $r$ objek dari $n$ jenis objek yang berbeda, di mana setiap jenis tersedia dalam jumlah tak terbatas. Ini setara dengan mencari banyaknya solusi bulat non-negatif dari persamaan:

$x_{1} + x_{2} + \dots + x_{n} = r, x_{i} \geq 0$

Teorema (Formula Stars and Bars)

Banyaknya cara memilih $r$ objek dari $n$ jenis objek (banyaknya solusi bulat non-negatif dari $x_{1} + \dots + x_{n} = r$ ) adalah:

$(r r + n - 1) = (n - 1 r + n - 1)$

Contoh Soal & Pembahasan

Contoh (Permutasi Huruf MISSISSIPPI)

Tentukan banyaknya cara menyusun huruf-huruf dari kata “MISSISSIPPI”.

Contoh (Pembelian Donat (Stars and Bars))

Toko roti menjual 4 jenis donat berbeda. Seseorang ingin membeli 10 buah donat. Berapa banyak kombinasi donat yang dapat dipilih?

Contoh (Solusi Bulat Positif)

Berapa banyak solusi bulat positif ( $x_{i} > 0$ ) untuk persamaan $x_{1} + x_{2} + x_{3} + x_{4} = 12$ ?

Latihan Soal

✏️ Latihan Soal 1 (Susunan Kata COMBINATORICS)

Berapa banyak susunan berbeda dari kata “COMBINATORICS”?

💡 Tampilkan Pembahasan / Solusi

▾

Pembahasan:

Pembahasan: Total 12 huruf: C=2, O=2, M=1, B=1, I=2, N=1, A=1, T=1, R=1, S=1. Banyak susunan: $\frac{12 !}{2 ! 2 ! 2 !} = \frac{479.001.600}{8} = 59.875.200$ . $■$

Navigasi Sub-Topik

← Sub-Topik Sebelumnya: Permutasi dan Kombinasi
Sub-Topik Selanjutnya: Teorema Binomial dan Identitas Pascal →

Pengaturan Benda Identik dan Berbeda (Multiset & Stars and Bars)

1. Permutasi Multiset

2. Kombinasi Multiset (Metode Stars and Bars)

Contoh Soal & Pembahasan

Latihan Soal

Navigasi Sub-Topik

Materi Terkait (Linked References) (2)

Permutasi dan Kombinasi

Teorema Binomial dan Identitas Pascal

Diskusi & Tanya Jawab

Title