Вариации с повторение

Вариациите с повторение приличат на обикновените вариации, само че позволяваме елементите на основното множество M да се повтарят.

Определение и формула

Ще започнем с класически пример: колко различни думи можем да образуваме от буквите на английската азбука (abc … xyz, те са 26), ако думата трябва да е с дължина 6? Шест букви не са много, но все пак думите ще бъдат доста. Не ни интересува смисълът на думите, така че и „weqrww“ приемаме за валидна дума с дължина шест.

За пресмятането ни трябва само комбинаторното правило за умножение. Имаме общо 26 различни букви, които можем да използваме. На първото място можем да поставим една от 26-те букви. На второто място също можем да поставим една от 26-те букви, защото не сме поставили условие буквите да не се повтарят. Така стигаме до извода, че на всяка позиция избираме от 26 букви и общият брой вариации според правилото за умножение е 26⁶ = 308 915 776. Това е доста, при положение че използвахме само 26 букви.

Ще кажем, че вариация с повторение от k-ти клас на множество M с големина n е всяка наредена k-торка, чиито елементи са от множеството M и всеки елемент може да се среща в k-торката до k пъти. Ако имаме множеството M = {1, 2, 3}, то всичко това са валидни вариации с повторение от четвърти клас: (1; 1; 1; 1), (1; 2; 3; 1), (2; 2; 3; 3). Броят на такива вариации с повторение, който означаваме с ${\bar{V}}_n^k$, е равен на

$${\bar{V}}_n^k=n^k.$$

Решени примери

1. Колко шестцифрени числа могат да се съставят от цифрите {2, 4, 6, 8}, ако цифрите могат да се повтарят? Просто заместваме във формулата, множеството има 4 елемента и избираме шесторки:

   $${\bar{V}}_4^6=4^6=4096.$$

2. В компютрите обикновено се използва двоична бройна система, т.е. система, която използва само цифрите 0 и 1. Въвеждат се нови единици, например един бит представлява нещо като клетка, в която се записва точно или нула, или единица. По-голям е байтът (на английски byte), който съдържа 8 бита. Така 1 е един бит, а 01110001 е един байт. По колко различни начина може да се запълни един байт с 8 бита?

   Избираме от множеството {0, 1}, т.е. от два елемента. Избираме k-торка с големина k = 8, така че броят на всички възможности е равен на

   $${\bar{V}}_2^8=2^8=256.$$

3. От предишния пример знаем, че един байт може да различи до 256 различни стойности. По колко начина можем да запълним 4 байта?

   Четирите байта съдържат 4 · 8 = 32 бита, като пак избираме от множество с големина 2. Така че резултатът е:

   $${\bar{V}}_2^{32}=2^{32}=4294967296.$$

   Виждаме, че само четири байта могат да различат над четири милиарда стойности. За представа: днешните компютри имат дискове с обем стотици гигабайти или дори терабайти. Един терабайт съдържа 1 000 000 000 000 байта и следователно 8 000 000 000 000 бита. На терабайтов диск можем да запишем до 2^{8 000 000 000 000} различни стойности.

   Бележка: в момента има известно объркване около понятието килобайт (мегабайт и т.н.). По технологични причини един килобайт не е съдържал 1000 байта, както е обичайно при другите единици (един килограм е равен на хиляда грама), а един килобайт е бил равен на 2¹⁰ байта, което е 1024 байта. Един мегабайт тогава е бил 2²⁰ байта или още 2¹⁰ килобайта.

   В момента различаваме два вида записи: 1 kB (чете се килобайт) е 1000 байта, а 1 KiB (чете се кибибайт) е 2¹⁰ = 1024 байта.

4. Друг пример се намира в отделна статия, посветена на сигурността на паролата.