Kombinasi dengan Perulangan

Seperti halnya permutasi dengan perulangan, kita dapat juga mendiskusikan kombinasi dengan perulangan. Sebagai contoh, misalkan lima sekawan pergi ke warung untuk sarapan . Ada tiga jenis makanan yang disajikan oleh warung tersebut yakni nasi gurih, lontong dan bubur ayam. Pelayan mendatangi meja lima sekawan dan mencatat pesanan dari lima sekawan pada satu kertas bon pesanan. Ada berapa cara bon dapat ditulis untuk lima sekawan tersebut? Perhatikan bahwa urutan pesanan siapa yang ditulis lebih dulu tidak membedakan bon pesanan, sehingga persoalan ini adalah persoalan kombinasi. Lebih lanjut perhatikan bahwa dua orang berbeda bisa memesan makanan yang sama, jadi pada persoalan ini terjadi perulangan (perulangan tak hingga). Lebih lanjut, sangat memungkin bahwa ada jenis makanan yang tidak dipesan.
Baca juga:
- Kombinasi tanpa perulangan.
- Permutasi linear tanpa perulangan.
- Permutasi dengan perulangan.

Contoh-1:
Tentukan banyaknya 5-kombinasi atas himpunan {x, y, z}.
Solusi:
Semua 5-kombinasi dimaksud dapat kita tuliskan sebagai berikut.
xxxxx, xxxxy, xxxxz, xxxyy, xxxyz, xxxzz, xxyyy,
xxyyz, xxyzz, xxzzz, xyyyy, xyyyz, xyyzz, xyzzz,
xzzzz, yyyyy, yyyyz, yyyzz, yyzzz, yzzzz, zzzzz.
Sehingga terdapat 21 buah 5-kombinasi dari {x, y, z}.

Perhatikan bahwa solusi dari persolan pesanan lima sekawan adalah banyaknya 5-kombinasi dari {x, y, z} dengan x menyatakan lontong, y menyatakan nasi gurih dan z menyatakan bubur ayam. Persoalan lebih lanjut adalah bagaimana cara kita menentukan 5-kombinasi atas himpunan {x, y, z} tanpa mentabulasi semua kombinasi yang mungkin?
Untuk menjawab pertanyaan di atas kita gunakan notasi berikut yang menggunakan untaian digit biner. Setiap 5-kombinasi kita bagi menjadi 3 blok digit 1 yang dipisahkan oleh sebuah digit 0. Banyaknya digit 1 pada blok pertama menyatakan banyaknya perulangan untuk x, banyak digit 1 pada blok kedua menyatakan banyak perulangan untuk y, hal sama blok ketiga digunakan untuk menyatakan perulangan dari z. Sebagai contoh untaian digit biner 1110101, 0101111 dan 1101110 masing-masing menyatakan 5-kombinasi xxxyz, yzzzz dan xxyyy. Sehingga persoalan berubah menjadi menentukan banyaknya 7-permutasi berulang atas 7-objek yang terdiri dari dua tipe 1 dan 0 dengan 5 objek tipe 1 dan dan 2 objek tipe 0. Dari rumus permutasi banyaknya 7-permutasi yang demikian adalah $$\frac{7!}{5!.2!}=21.$$
Teorema berikut memberikan bentuk umum dari persoalan pesanan dari lima sekawan.

Teorema 3.4.2
Andaikan $A$ adalah sebuah multiset dengan objek atas $k$ tipe, masing-masing dengan tak hingga perulangan. Maka banyaknya $n$-kombinasi atas $A$ adalah $${n+k-1 \choose n}={n+k-1 \choose k-1}$$

Kembali ke persoalan pesanan 5 sekawan. Persoalan banyaknya pesanan yang mungkin bagi lima sekawan dapat dinyatakan sebagai banyaknya solusi tak negatif dari persamaan diofantin sebagai berikut. Misalkan $x_1$ menyatakan banyak pesanan lontong, $x_2$ menyatakan banyak pesanan nasi gurih, dan $x_3$ menyatakan banyaknya pesanan bubur ayam. Maka persoalan pesanan lima sekawan dapat dinyatakan sebagai banyaknya solusi tak negatif dari persamaan $$x_1 + x_2 + x_3 = 5$$ Akibat berikut ini memberikan bentuk umum banyaknya solusi tak negatif dari persamaan diofantin.

Akibat 3.4.3
Banyaknya solusi tak negatif dari persamaan dio- phantin $x_1 + x_2 + · · · + x_k = n$ adalah $${n+k-1 \choose k-1}$$

Contoh-1:
Tentukan banyaknya barisan bilangan bulat tak negatif (x, y, z) sehingga $x + y + z = 99$.
Solusi. Banyaknya barisan bilangan bulat tak negatif (x, y, z) sehingga $x + y + z = 99$ adalah $${99+3-1 \choose 3-1}=5050$$
Contoh-2:
Tentukan banyaknya solusi tak negatif dari $a + b + c + d \le 35$.
Solusi. Persoalan ini ekivalen dengan menentukan banyaknya solusi tak negatif dari $a + b + c + d + e = 35$. Oleh Akibat 3.4.3 banyaknya solusi adalah $${35+5-1 \choose 5-1}$$ $$={39 \choose 4}=82251$$
Demikianlah materi tentang kombinasi dengan perulangan. Sampai jumpa dan semoga bermanfaat.