Susunan dengan pengulangan

Susunan dengan pengulangan mirip dengan permutasi k dari n unsur biasa, hanya saja unsur-unsur dari himpunan dasar M boleh berulang.

Definisi dan rumus

Kita mulai dengan contoh klasik: berapa banyak kata berbeda yang dapat dibentuk dari huruf-huruf alfabet Latin (abc … xyz, ada 26 huruf) jika panjang kata harus 6 huruf? Enam huruf memang tidak banyak, tetapi kata yang terbentuk ternyata cukup banyak. Kita tidak peduli pada arti kata, jadi “weqrww” pun kita anggap kata yang sah dengan panjang enam.

Untuk menghitungnya, kita hanya perlu aturan perkalian. Ada 26 huruf berbeda yang boleh dipakai. Di tempat pertama kita dapat menaruh salah satu dari 26 huruf. Di tempat kedua kita juga dapat menaruh salah satu dari 26 huruf, karena tidak ada syarat bahwa huruf tidak boleh berulang. Jadi, di setiap posisi kita memilih dari 26 huruf, dan menurut aturan perkalian banyak semua susunan adalah 26⁶ = 308.915.776. Cukup banyak, padahal kita hanya memakai 26 huruf.

Susunan k unsur dengan pengulangan dari himpunan M yang beranggotakan n unsur adalah setiap urutan k unsur yang semua unsurnya berasal dari himpunan M; setiap unsur boleh muncul di dalam susunan k unsur itu sampai k kali. Jadi, jika M = {1, 2, 3}, semua yang berikut ini adalah susunan empat unsur dengan pengulangan yang sah: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). Banyak susunan seperti itu sama dengan

$$n^k.$$

Contoh soal

1. Berapa banyak bilangan enam angka yang dapat disusun dari angka-angka {2, 4, 6, 8} jika angkanya boleh berulang? Kita cukup memasukkan nilai ke rumus: himpunan mempunyai 4 anggota dan kita membentuk susunan enam unsur:

   $$4^6=4096.$$

2. Komputer biasanya memakai sistem bilangan biner, yaitu sistem yang hanya memakai angka 0 dan 1. Di sana dipakai satuan baru. Misalnya, satu bit adalah semacam sel yang dapat menyimpan tepat satu nilai, nol atau satu. Satuan yang lebih besar adalah byte, yang terdiri atas 8 bit. Jadi, 1 adalah satu bit, sedangkan 01110001 adalah satu byte. Ada berapa cara berbeda untuk mengisi satu byte dengan 8 bit?

   Kita memilih dari himpunan {0, 1}, yaitu dari dua unsur. Kita membentuk susunan k unsur dengan k = 8, jadi banyak semua kemungkinan adalah

   $$2^8=256.$$

3. Dari contoh sebelumnya kita tahu bahwa satu byte dapat membedakan sampai 256 nilai yang berbeda. Ada berapa cara untuk mengisi 4 byte?

   Empat byte terdiri atas 4 · 8 = 32 bit, dan kita tetap memilih dari himpunan dengan 2 anggota. Jadi, hasilnya adalah:

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

   Ternyata empat byte saja dapat membedakan lebih dari empat miliar nilai. Sebagai gambaran: komputer sekarang mempunyai disk berkapasitas ratusan gigabyte, bahkan terabyte. Satu terabyte terdiri atas 1.000.000.000.000 byte, jadi 8.000.000.000.000 bit. Pada disk berkapasitas satu terabyte kita dapat menyimpan sampai 2^{8.000.000.000.000} nilai yang berbeda.

   Catatan: saat ini ada sedikit kerancuan dalam istilah kilobyte (megabyte, dan seterusnya). Karena alasan teknis, dulu satu kilobyte tidak berisi 1.000 byte seperti yang lazim pada satuan lain (satu kilogram sama dengan seribu gram), tetapi 2¹⁰ byte, yaitu 1024 byte. Satu megabyte sama dengan 2²⁰ byte atau 2¹⁰ kilobyte.

   Karena itu, sekarang dibedakan dua penulisan: 1 kB (dibaca kilobyte) adalah 1.000 byte dan 1 KiB (dibaca kibibyte) adalah 2¹⁰ = 1024 byte.

4. Contoh lain dibahas dalam artikel tersendiri tentang keamanan kata sandi.