Kombinatorik

Ingin tahu berapa banyak set lima keping kad yang berbeza boleh dipilih daripada satu pek 32 keping kad? Soalan seperti inilah yang diselesaikan oleh kombinatorik. Terdapat dua petua asas kombinatorik, iaitu petua penambahan dan petua pendaraban. Semua kaedah lain hanyalah lanjutan daripada kedua-dua prinsip asas ini.

Petua penambahan

Petua penambahan sangat mudah. Jika kita mempunyai set A, B yang tidak mempunyai sebarang unsur sepunya, maka bilangan semua cara untuk memilih satu unsur daripada kesatuan A ∪ B sama dengan |A| + |B|, iaitu hasil tambah saiz kedua-dua set itu.

Mari kita mulakan dengan contoh yang mudah. Kita mempunyai 6 biji bola merah dan 8 biji bola biru. Semua bola ini dimasukkan ke dalam sebuah kotak. Berapakah jumlah pilihan yang ada jika kita mencabut sebiji bola? Pada mulanya kita mempunyai set bola merah, kita namakan set A, dan set bola biru, kita namakan B. Kedua-dua set ini saling eksklusif, iaitu tiada bola yang terdapat dalam kedua-duanya. Kita mahu mencabut sebiji bola, jadi terdapat |A| + |B| = 6 + 8 = 14 pilihan kesemuanya. Itu sahaja.

Petua pendaraban

Sekali lagi kita mempunyai dua set, Z dan M. Set Z mengandungi tiga orang perempuan dan set M mengandungi empat orang lelaki. Sekarang kita bertanya: berapa banyak pasangan lelaki—perempuan yang berbeza boleh dibentuk daripada set-set ini? Setiap kali, kita mengambil seorang perempuan dan memasangkannya dengan seorang lelaki. Bilangan semua pasangan dikira seperti berikut: kita ambil seorang perempuan, Siti, lalu memasangkannya dengan setiap lelaki satu demi satu. Kita memperoleh 4 pasangan yang berbeza kerana Siti boleh dipasangkan dengan 4 orang lelaki. Hal yang sama dilakukan bagi dua orang perempuan yang lain, dan setiap seorang daripada mereka juga membentuk 4 pasangan lagi. Itu sahaja, kesemuanya terdapat 4 + 4 + 4 = 12 pasangan.

Apakah sebenarnya yang telah kita lakukan? Kita mendarab saiz kedua-dua set. Terdapat 3 orang perempuan dan 4 orang lelaki, maka jumlah pasangan ialah 3 · 4 = 12. Itulah sebabnya petua ini dinamakan petua pendaraban. Jadi, jika kita mempunyai dua set dan membentuk pasangan daripadanya, kita hanya perlu mendarab bilangan unsur set pertama dengan bilangan unsur set kedua.

Anda boleh menyemak bahawa petua ini memang benar. Berikut ialah semua pasangan yang boleh dibentuk daripada 3 orang perempuan dan 4 orang lelaki. Setiap baris mewakili pilihan bagi seorang perempuan dan setiap lajur mewakili pilihan bagi seorang lelaki. Jadi, terdapat tiga baris dan empat lajur, iaitu baris · lajur pilihan kesemuanya.

$$\begin{array}{rcl}& & (Z_1,M_1),(Z_1,M_2),(Z_1,M_3),(Z_1,M_4),\\ & & (Z_2,M_1),(Z_2,M_2),(Z_2,M_3),(Z_2,M_4),\\ & & (Z_3,M_1),(Z_3,M_2),(Z_3,M_3),(Z_3,M_4)\end{array}$$

Contoh soalan dan penyelesaian

1. Berapa banyak nombor dua digit yang berbeza wujud? Bagaimanakah rupa nombor dua digit? Di tempat pertama terdapat salah satu digit 1, …, 9, manakala di tempat kedua digit sifar juga dibenarkan: 0, …, 9. Jadi, set pertama mempunyai 9 digit dan set kedua mempunyai 10 digit. Dengan petua pendaraban, kita memperoleh jawapan akhir: 9 · 10 = 90.

• Berapa banyak nombor tiga digit yang berbeza wujud jika tiada digit yang boleh muncul dua kali? Di tempat pertama sekali lagi boleh terdapat sembilan digit kerana nombor tidak boleh bermula dengan sifar. Di tempat kedua boleh terdapat semua digit termasuk sifar, kecuali digit yang sudah berada di tempat pertama. Jadi, daripada sepuluh digit yang mungkin, kita tolak satu. (Contohnya, jika nombor tiga digit kita bermula dengan 4, jelas bahawa digit 4 tidak boleh muncul lagi di tempat kedua kerana nombor itu akan mengandungi dua digit 4.) Di tempat ketiga juga boleh terdapat semua digit, kecuali digit yang berada di tempat pertama atau kedua, atas sebab yang sama. Jika digit di tempat pertama ialah 4 dan di tempat kedua ialah 7, maka di tempat ketiga kita boleh meletakkan satu digit daripada {0, …, 9} ∖ {4, 7}. Daripada sepuluh digit, kita perlu menolak dua. Sekarang kita hanya perlu mendarab: 9 · 9 · 8 = 648. Maka, terdapat 648 nombor sedemikian.
• Sebiji dadu biasa dilambung dua kali berturut-turut. Berapa banyak keputusan berbeza yang boleh diperoleh? Pada lambungan pertama, terdapat 6 kesudahan yang berbeza. Begitu juga pada lambungan kedua, jadi jumlah pilihan ialah 6 · 6 = 36.
• Sebiji dadu dilambung dua kali berturut-turut. Berapa banyak keputusan berbeza yang boleh diperoleh jika lambungan pertama memberikan nombor genap? Pada lambungan pertama muncul nombor genap, iaitu salah satu daripada nombor 2, 4, 6, jadi terdapat 3 pilihan. Pada lambungan kedua boleh muncul sebarang nombor, jadi kesemuanya terdapat 3 · 6 = 18 pilihan.