Tekrarlı Dizilişler

Tekrarlı dizilişler, klasik r’li permütasyonlara benzer; yalnızca başlangıç kümesi M’nin elemanlarının tekrar etmesine izin veriyoruz.

Tanım ve Formül

Klasik bir örnekle başlayalım: İngiliz alfabesinin harflerinden (abc … xyz, 26 harf vardır) 6 harf uzunluğunda kaç farklı sözcük oluşturabiliriz? Altı harf çok değil, yine de sözcük sayısı oldukça fazla olacak. Sözcüklerin anlamıyla ilgilenmiyoruz, dolayısıyla “weqrww” sözcüğünü de altı uzunluğunda geçerli bir sözcük sayarız.

Hesaplamak için yalnızca çarpma yoluyla sayma kuralını bilmemiz yeterli. Kullanabileceğimiz toplam 26 farklı harf var. Birinci yere 26 harften birini koyabiliriz. İkinci yere de 26 harften birini koyabiliriz, çünkü harflerin tekrar edemeyeceği gibi bir koşul koymadık. Böylece her konumda 26 harften seçim yaptığımız ve çarpma kuralına göre toplam dizilişlerin sayısının 26⁶ = 308.915.776 olduğu sonucuna ulaşırız. Yalnızca 26 harf kullandığımıza göre bu oldukça fazla.

n elemanlı bir M kümesinin tekrarlı r’li dizilişi, elemanları M kümesinden olan ve her elemanın r’lide en çok r kez bulunabildiği her sıralı r’lidir. Yani M = {1, 2, 3} kümemiz varsa şunların hepsi geçerli 4 elemanlı tekrarlı dizilişlerdir: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). Bu tür tekrarlı dizilişlerin sayısı şuna eşittir:

$$n^r.$$

Çözümlü Örnekler

1. Rakamların tekrar edebildiği durumda {2, 4, 6, 8} rakamlarından kaç altı basamaklı sayı yazılabilir? Formülde yerine yazmamız yeterli: kümenin 4 elemanı var ve altılılar seçiyoruz:

   $$4^6=4096.$$

2. Bilgisayarlarda genellikle ikili sayı sistemi kullanılır, yani yalnızca 0 ve 1 rakamlarını kullanan bir sistem. Orada yeni birimler tanımlanır; örneğin bir bit, kişinin tam olarak ya 0’ı ya da 1’i depoladığı bir tür hücreyi temsil eder. Daha büyük olan bayttır (İngilizce byte), 8 bit içerir. Yani 1 bir bittir, 01110001 ise bir bayttır. Bir baytı 8 bitle doldurmanın kaç farklı yolu vardır?

   {0, 1} kümesinden, yani iki elemandan seçiyoruz. r = 8 elemanlı bir r’li seçiyoruz; dolayısıyla tüm durumların sayısı şuna eşittir:

   $$2^8=256.$$

3. Önceki örnekten, bir baytın 256’ya kadar farklı değeri ayırt edebildiğini biliyoruz. 4 bayt kaç farklı yolla doldurulabilir?

   Dört bayt 4 · 8 = 32 bit içerir, yine 2 elemanlı kümeden seçiyoruz. Yani sonuç şudur:

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

   Yalnızca dört baytın dört milyardan fazla değeri ayırt edebildiğini görüyoruz. Bir fikir vermesi için: günümüz bilgisayarlarında yüzlerce gigabayt, hatta doğrudan terabayt büyüklüğünde diskler bulunur. Bir terabayt 1.000.000.000.000 bayt, dolayısıyla 8.000.000.000.000 bit içerir. Yani bir terabaytlık disk 2^{8.000.000.000.000} farklı değeri ayırt edebilir.

   Not: şu anda kilobayt (megabayt vb.) kavramında hafif bir karışıklık var. Teknolojik nedenlerle bir kilobayt, diğer birimlerde olağan olduğu gibi (bir kilogram bin grama eşittir) 1000 bayt içermiyordu; bir kilobayt 2¹⁰ bayta, yani 1024 bayta eşitti. Bir megabayt ise 2²⁰ bayt, yani 2¹⁰ kilobaytlık bir büyüklüktü.

   Bugün iki tür gösterim ayırt ediyoruz: 1 kB (kilobayt diye okunur) 1000 bayttır, 1 KiB (kibibayt diye okunur) ise 2¹⁰ = 1024 bayttır.

4. Bir sonraki örnek, parola güvenliğini ele alan ayrı bir makalede yer alıyor.