Ismétléses variációk

Az ismétléses variációk hasonlítanak a hagyományos variációkhoz, csak megengedjük, hogy az alaphalmaz, az M elemei ismétlődjenek.

Definíció és képlet

Kezdjük egy klasszikus példával: hány különböző szót alkothatunk az angol ábécé betűiből (abc … xyz, összesen 26), ha a szó hossza 6? Hat betű nem sok, a szavak száma mégis meglehetősen nagy lesz. A szavak jelentésével nem törődünk, ezért a „weqrww” is érvényes hatbetűs szónak számít.

A számoláshoz csak a kombinatorikai szorzatszabályt kell ismernünk. Összesen 26 különböző betűt használhatunk. Az első helyre tehát a 26 betű egyikét írhatjuk. A második helyre is a 26 betű egyikét írhatjuk, mert nem szabtuk meg feltételként, hogy a betűk nem ismétlődhetnek. Így minden helyen a 26 betűből választunk, és a variációk száma a szorzatszabály szerint 26⁶ = 308 915 776. Ez elég sok ahhoz képest, hogy csak 26 betűt használtunk.

Azt mondjuk, hogy az n elemű M halmaz k tagú ismétléses variációja minden olyan rendezett k-as, amelynek elemei az M halmazból valók, és minden elem legfeljebb k-szor fordulhat elő benne. Ha tehát M = {1, 2, 3}, akkor ezek mind érvényes 4 tagú ismétléses variációk: (1; 1; 1; 1), (1; 2; 3; 1), (2; 2; 3; 3). Az ilyen ismétléses variációk száma, jelölése $V_n^{k,i}$, a következő:

$$V_n^{k,i}=n^k.$$

Megoldott példák

1. Hány hatjegyű szám állítható össze a {2, 4, 6, 8} számjegyekből, ha a számjegyek ismétlődhetnek? Egyszerűen behelyettesítünk a képletbe, a halmaz elemszáma 4, és hatosokat választunk:

   $$V_4^{6,i}=4^6=4096.$$

2. A számítógépekben általában kettes számrendszert használnak, vagyis olyat, amelyben csak a 0 és az 1 számjegy szerepel. Új egységeket vezettek be, például az egy bit afféle cella, amelybe vagy egy nullát, vagy egy egyest írunk. Nagyobb egység a bájt (angolul byte), amely 8 bitből áll. Tehát az 1 egy bit, a 01110001 pedig egy bájt. Hányféleképpen tölthetünk ki egy bájtot 8 bittel?

   A {0, 1} halmazból, vagyis két elemből választunk. Egy k = 8 hosszúságú k-ast választunk, így az összes lehetőség száma

   $$V_2^{8,i}=2^8=256.$$

3. Az előző példából tudjuk, hogy egy bájt akár 256 különböző értéket meg tud különböztetni. Hányféleképpen tölthetünk ki 4 bájtot?

   Négy bájt 4 · 8 = 32 bitet tartalmaz, és továbbra is kételemű halmazból választunk. Az eredmény tehát:

   $$V_2^{32,i}=2^{32}=4294967296.$$

   Látjuk, hogy mindössze négy bájt több mint négymilliárd értéket képes megkülönböztetni. Hogy képet kapj róla: a mai számítógépek lemezei több száz gigabájtosak, sőt akár terabájtosak. Egy terabájt 1 000 000 000 000 bájtot, vagyis 8 000 000 000 000 bitet tartalmaz. Egy terabájtos lemezen tehát akár 2^{8 000 000 000 000} különböző érték tárolható.

   Megjegyzés: manapság bizonyos zűrzavar uralkodik a kilobájt (megabájt stb.) fogalma körül. Technikai okokból egy kilobájt nem 1000 bájtot tartalmazott, ahogy a többi mértékegységnél szokás (egy kilogramm egyenlő ezer grammal), hanem egy kilobájt 2¹⁰ bájt, vagyis 1024 bájt volt. Egy megabájt akkor 2²⁰ bájt, vagyis 2¹⁰ kilobájt volt.

   Ma kétféle jelölést különböztetünk meg: az 1 kB (kilobájt) 1000 bájt, az 1 KiB (kibibájt) pedig 2¹⁰ = 1024 bájt.

4. Egy további példa a jelszavak biztonságával foglalkozó külön cikkben található.