Kombinasi dengan pengulangan

Kombinasi dengan pengulangan mirip dengan kombinasi biasa, hanya saja unsur-unsur dari himpunan dasar M boleh berulang.

Definisi dan rumus

Kita mulai dengan contoh yang menarik: kamu pergi ke toko dan ingin membeli dua belas botol minuman untuk berkemah. Di rak ada empat jenis minuman botol. Ada beberapa cara membelinya. Misalnya, kamu bisa membeli 5 botol teh, 2 botol jus, 1 botol susu, dan 4 botol air mineral, atau membeli tepat tiga botol dari setiap jenis. Ada berapa cara berbeda seluruhnya untuk membeli minuman sehingga jumlahnya tepat dua belas botol?

Jadi, himpunan dasarnya adalah M = {Teh, Jus, Susu, Air}, dan kita bertanya: ada berapa kelompok k unsur, dengan k = 12, yang unsur-unsurnya berasal dari himpunan M dan urutannya tidak diperhatikan?

Penurunan rumusnya sedikit lebih rumit daripada soal kombinatorika lainnya. Pertama, belanjaan kita bayangkan sebagai barisan angka nol dan satu. Banyak angka satu menyatakan banyak botol yang dibeli dari satu jenis, dan angka nol memisahkan jenis-jenis minuman. Jadi, 111011101111101 berarti kita membeli tiga botol teh (tiga angka 1 pertama), lalu tiga botol jus (0 sebagai pemisah, lalu tiga angka 1), lalu lima botol susu (0 sebagai pemisah, lalu lima angka 1), dan akhirnya satu botol air mineral. Seluruh prinsipnya terlihat pada gambaran berikut:

$$\underset{Teh}{\underbrace{111}}0\underset{Jus}{\underbrace{111}}0\underset{Susu}{\underbrace{11111}}0\underset{Air}{\underbrace{1}}$$

Jika kita ingin membeli 6 botol teh, 4 botol jus, 2 botol air mineral, dan tidak membeli susu, barisannya seperti ini:

$$\underset{Teh}{\underbrace{111111}}0\underset{Jus}{\underbrace{1111}}00\underset{Air}{\underbrace{11}}$$

Perhatikan bahwa panjang barisan ini selalu 15. Di dalamnya harus ada 12 angka satu agar kita membeli 12 botol. Selain itu, harus ada tiga pemisah agar empat jenis minuman dapat dipisahkan. Jadi, tinggal dihitung: ada berapa barisan dengan panjang 15 yang memuat tepat tiga angka nol?

Kita cukup menghitung letak angka nol. Begitu 3 angka nol ditempatkan di antara 12 angka satu, diperoleh satu cara membeli minuman yang sah. Dengan kata lain, ada 15 posisi dan 3 di antaranya harus diisi nol. Posisi sisanya otomatis diisi angka satu.

Sekarang soalnya menjadi soal sederhana tentang kombinasi tanpa pengulangan. Ke-15 posisi kita beri nomor {1, …, 15}, lalu dari himpunan ini kita selalu memilih tiga nomor. Dengan begitu, kita memperoleh tiga posisi tempat angka nol ditaruh. Misalnya, kombinasi {2, 4, 7} menghasilkan barisan 101011011111111. Di posisi ke-2, ke-4, dan ke-7 ada angka nol, sisanya angka satu. Jadi, seluruhnya ada

$$(\genfrac{}{}{0ex}{}{15}{3})=455$$

cara berbeda menempatkan angka nol di 15 posisi. Karena itu, ada juga 455 cara berbeda membeli 12 botol minuman jika tersedia empat jenis minuman.

Cara berpikir tadi dapat diperumum. Jika ada himpunan M dengan n anggota dan kita memilih kelompok k unsur darinya, dengan unsur-unsurnya boleh berulang, kita menyusun barisan angka nol dan satu dengan panjang n + k − 1 (k angka satu dan n − 1 angka nol). Lalu kita menghitung banyak cara menempatkan n − 1 angka nol. Jadi, banyak kombinasi dengan pengulangan adalah

$$C(n+k-1,k)=(\genfrac{}{}{0ex}{}{n+k-1}{n-1})=(\genfrac{}{}{0ex}{}{n+k-1}{k}).$$

Langkah terakhir boleh dilakukan berkat hubungan dasar antara koefisien binomial.

Contoh soal

1. Ada berapa cara membagikan 20 tiket gratis pemutaran perdana sebuah film kepada 10 orang nenek? Ini contoh kombinasi dengan pengulangan, karena satu nenek boleh mendapat lebih dari satu tiket, bahkan bisa saja semua tiket. Kita hanya perlu menentukan dengan benar apa n dan apa k. Sebenarnya kita memilih kombinasi 20 unsur dari 10 nenek. Dengan kata lain, kita membentuk barisan angka nol dan satu yang panjangnya 29, berisi 20 angka satu dan 9 angka nol. Jadi, n = 10, k = 20. Diperoleh hasil:

$$C(10+20-1,20)=(\genfrac{}{}{0ex}{}{10+20-1}{20})=10.015.005.$$