Gabungan dengan ulangan

Gabungan dengan ulangan menyerupai gabungan biasa, cuma unsur daripada set asas M dibenarkan berulang.

Takrif dan rumus

Mari kita mulakan dengan contoh yang menarik: anda pergi ke kedai untuk membeli dua belas botol minuman bagi aktiviti perkhemahan. Di rak terdapat empat perisa minuman yang berbeza. Ada beberapa cara untuk membelinya. Contohnya, anda boleh membeli 5 botol perisa oren, 2 botol epal, 1 botol mangga dan 4 botol laici, atau membeli tiga botol bagi setiap perisa. Berapa banyak cara berbeza untuk membeli minuman itu supaya anda mendapat tepat dua belas botol?

Jadi, kita mempunyai set asas M = {Oren, Epal, Mangga, Laici} dan kita bertanya: berapa banyak k-tupel, dengan k = 12, yang mengandungi unsur set M dan susunannya tidak penting?

Pembuktian rumus ini agak lebih rumit berbanding soalan kombinatorik yang lain. Pertama, kita gambarkan pembelian kita sebagai jujukan sifar dan satu. Bilangan digit satu sepadan dengan bilangan botol yang dibeli bagi suatu perisa, manakala sifar memisahkan perisa yang berbeza. Jadi, 111011101111101 bermaksud kita membeli tiga botol oren (tiga digit 1 yang pertama), kemudian tiga botol epal (0 ialah pemisah, diikuti tiga digit 1), kemudian lima botol mangga (pemisah 0 dan lima digit 1), dan akhirnya sebotol laici. Prinsip ini ditunjukkan seperti berikut:

$$\underset{Or}{\underbrace{111}}0\underset{Ep}{\underbrace{111}}0\underset{Ma}{\underbrace{11111}}0\underset{La}{\underbrace{1}}$$

Jika kita mahu membeli 6 botol oren, 4 botol epal, 2 botol laici dan tiada botol mangga, jujukannya adalah seperti berikut:

$$\underset{Or}{\underbrace{111111}}0\underset{Ep}{\underbrace{1111}}00\underset{La}{\underbrace{11}}$$

Perhatikan bahawa panjang jujukan ini sentiasa 15. Jujukan itu mesti mengandungi 12 digit satu supaya kita membeli 12 botol kesemuanya, dan tiga pemisah supaya empat perisa yang berbeza dapat dipisahkan. Jadi, kita perlu mengira bilangan jujukan dengan panjang 15 yang mengandungi tepat tiga sifar.

Kita hanya perlu mengira kedudukan sifar. Sebaik sahaja 3 sifar diletakkan di antara 12 digit satu, kita memperoleh satu gabungan minuman yang sah. Dengan kata lain, terdapat 15 kedudukan dan 3 daripadanya mesti diisi dengan sifar. Kedudukan yang selebihnya secara automatik diisi dengan satu.

Ini ialah soalan gabungan tanpa ulangan yang mudah. Kita nomborkan 15 kedudukan itu dengan nombor {1, …, 15}, kemudian memilih tiga nombor daripada set ini. Tiga nombor itu ialah kedudukan sifar. Contohnya, gabungan {2, 4, 7} memberikan jujukan 101011011111111: tempat ke-2, ke-4 dan ke-7 berisi sifar, manakala yang lain berisi satu. Jadi, terdapat

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

cara berbeza untuk meletakkan sifar dalam 15 kedudukan, dan oleh itu terdapat 455 cara berbeza untuk membeli 12 botol minuman jika terdapat empat perisa yang berbeza.

Hujah ini boleh diitlakkan. Jika kita mempunyai set M bersaiz n dan memilih k-tupel daripadanya dengan unsur yang boleh berulang, maka kita membentuk jujukan sifar dan satu dengan panjang n + k − 1 (k digit satu dan n − 1 sifar) dan mengira bilangan cara untuk meletakkan n − 1 sifar. Jadi, bilangan gabungan dengan ulangan (tiada tatatanda khas baginya) ialah

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

Kesamaan antara kedua-dua pekali binomial itu dibenarkan oleh hubungan asas antara pekali binomial.

Contoh soalan dan penyelesaian

1. Dengan berapa cara 20 tiket percuma untuk tayangan perdana sebuah filem tempatan boleh dibahagikan kepada 10 orang warga emas? Ini ialah soalan gabungan dengan ulangan kerana seorang warga emas boleh menerima lebih daripada satu tiket, malah kemungkinan semua tiket. Kita hanya perlu memahami dengan betul apakah n dan apakah k. Sebenarnya kita memilih gabungan 20 objek daripada 10 orang warga emas. Dengan kata lain, kita membentuk jujukan sifar dan satu dengan panjang 29 yang mengandungi 20 digit satu dan 9 sifar. Jadi, n = 10, k = 20. Kita memperoleh jawapan:

$$(\genfrac{}{}{0ex}{}{10+20-1}{20})={}^{29}{C}_{20}=10015005.$$