Susunan dengan ulangan

Susunan dengan ulangan menyerupai pilih atur biasa, cuma unsur daripada set asas M dibenarkan berulang.

Takrif dan rumus

Mari kita mulakan dengan contoh klasik: berapa banyak perkataan berbeza boleh dibentuk daripada huruf abjad Inggeris (abc … xyz, iaitu 26 huruf) jika setiap perkataan mesti mempunyai 6 huruf? Enam huruf tidaklah banyak, tetapi bilangan perkataan yang terhasil agak besar. Kita tidak mengambil kira makna perkataan, jadi “weqrww” juga dianggap perkataan enam huruf yang sah.

Untuk pengiraan ini, kita hanya perlu mengetahui petua pendaraban. Terdapat 26 huruf berbeza yang boleh digunakan. Di tempat pertama kita boleh meletakkan salah satu daripada 26 huruf. Di tempat kedua juga kita boleh meletakkan salah satu daripada 26 huruf kerana kita tidak menetapkan syarat bahawa huruf tidak boleh berulang. Jadi, di setiap kedudukan kita memilih daripada 26 huruf, dan mengikut petua pendaraban, jumlah susunan ialah 26⁶ = 308 915 776. Bilangan ini agak besar memandangkan kita hanya menggunakan 26 huruf.

Susunan k objek dengan ulangan daripada set M bersaiz n ialah sebarang k-tupel tertib yang unsurnya diambil daripada set M, dengan setiap unsur boleh muncul sehingga k kali dalam k-tupel itu. Contohnya, jika M = {1, 2, 3}, maka semua yang berikut ialah susunan 4 objek dengan ulangan yang sah: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). Bilangan susunan dengan ulangan sedemikian (tiada tatatanda khas baginya) ialah

$$n^k.$$

Contoh soalan dan penyelesaian

1. Berapa banyak nombor enam digit boleh dibentuk daripada digit {2, 4, 6, 8} jika digit boleh berulang? Kita hanya perlu menggantikan nilai ke dalam rumus. Set itu bersaiz 4 dan kita memilih enam-tupel:

   $$4^6=4096.$$

2. Komputer lazimnya menggunakan sistem nombor dalam asas dua, iaitu sistem yang hanya menggunakan digit 0 dan 1. Unit baharu digunakan dalam sistem ini. Contohnya, satu bit ialah sejenis sel yang menyimpan sama ada sifar atau satu. Unit yang lebih besar ialah bait (bahasa Inggeris: byte), yang mengandungi 8 bit. Jadi, 1 ialah satu bit, manakala 01110001 ialah satu bait. Berapa banyak cara berbeza untuk mengisi satu bait dengan 8 bit?

   Kita memilih daripada set {0, 1}, iaitu daripada dua unsur. Kita memilih k-tupel bersaiz k = 8, jadi bilangan semua kemungkinan ialah

   $$2^8=256.$$

3. Daripada contoh sebelumnya, kita tahu bahawa satu bait boleh membezakan sehingga 256 nilai yang berbeza. Berapa banyak cara untuk mengisi 4 bait?

   Empat bait mengandungi 4 · 8 = 32 bit, dan kita masih memilih daripada set bersaiz 2. Jadi, jawapannya ialah:

   $$2^{32}=4294967296.$$

   Kita lihat bahawa empat bait sahaja sudah dapat membezakan lebih daripada empat bilion nilai. Sebagai gambaran, komputer masa kini mempunyai cakera bersaiz ratusan gigabait, malah beberapa terabait. Satu terabait mengandungi 1 000 000 000 000 bait, iaitu 8 000 000 000 000 bit. Jadi, cakera satu terabait boleh menyimpan sehingga 2^{8 000 000 000 000} nilai yang berbeza.

   Catatan: pada masa ini terdapat sedikit kekeliruan tentang istilah kilobait (megabait dan seterusnya). Atas sebab teknologi, satu kilobait dahulunya bukan 1000 bait seperti kebiasaan bagi unit lain (satu kilogram sama dengan seribu gram), tetapi 2¹⁰ bait, iaitu 1024 bait. Satu megabait pula ialah 2²⁰ bait, atau 2¹⁰ kilobait.

   Oleh itu, kini kita membezakan dua jenis tatatanda: 1 kB (dibaca kilobait) ialah 1000 bait, manakala 1 KiB (dibaca kibibait) ialah 2¹⁰ = 1024 bait.

4. Satu lagi contoh terdapat dalam artikel berasingan tentang keselamatan kata laluan.