Variations with repetition

Variations with repetition are similar to classical variations, only we allow elements from the support set M to repeat.

Definition and formula

Let's start with a classic example: how many different words can we make from the letters of the English alphabet (abc ... xyz, there are 26) if the word is to be 6 in length? Six letters is not a lot, yet there will be quite a lot of words. We don't care about the meaning of the words, so we take even "weqrww" as a valid word of length six.

We only need to know the combinatorial product rule to do the calculation. We have a total of 26 different letters that we can use. So we can put one of the 26 letters in the first place. But we can also put one of the 26 letters in the second place, because we have not set the condition that the letters must not be repeated. This brings us to the fact that in each position we are choosing from 26 letters and the total number of variations is, according to the product rule, 26⁶ = 308 915 776. This is quite a lot for the fact that we have used only 26 letters.

We say that a k-element variation with repetition from the set M of size n is any ordered k-tice whose elements are from the set M and each element can occur up to k-times in the k-tice. Thus if we have a set M = {1, 2, 3}, then these are all valid 4-membered variations with repetition: [1, 1, 1, 1], [1, 2, 3, 1], [2, 2, 3, 3]. The number of such variations with repetition, denoted V'(k, n), is then equal to

$$ V'(k, n) = n^k. $$

Solved examples

1. How many six-digit numbers can be constructed from the digits {2, 4, 6, 8}, if the digits can repeat? Simply plug in the formula, the set is of size 4, and pick sixes:

   $$ V'(6, 4) = 4^6=4096. $$

2. A binary number system is commonly used in computers, i.e. a system that uses only the digits 0 and 1. New units are introduced, e.g. one bit represents a kind of cell in which one just stores either zero or one. The larger is the byte, which contains 8 bits. So 1 is one bit, while 01110001 is one byte. How many different ways are there to fill one byte with 8 bits?

   We choose from the set {0, 1}, i.e., two elements. We choose k-this is the size of k = 8, so the number of all possibilities is equal to

   $$ V'(8, 2) = 2^8 = 256. $$

3. From the previous example, we know that a single byte is capable of resolving up to 256 different values. How many ways are there to fill 4 bytes?

   The four bytes contain 4 · 8 = 32 bits, still selecting from a set of size 2. So the result is:

   $$ V'(32, 2) = 2^{32} = 4{,}294,967{,}296. $$

   We can see that just four bytes can distinguish over four billion values. To give you an idea: today's computers have disks of hundreds of gigabytes or even terabytes. One terabyte contains 1 000 000 000 000 bytes and therefore 8 000 000 000 000 bits. So we can store up to 2^{8 000 000 000 000} different values on a terabyte disk.

   Note: there is currently some confusion about the term kilobyte (megabyte, etc.). For technological reasons, one kilobyte did not contain 1000 bytes, as is usual in other units (one kilogram is equal to one thousand grams), but one kilobyte was equal to 2¹⁰ bytes, which is 1024 bytes. One megabyte was then 2²⁰ bytes or also 2¹⁰ kilobytes.

   Thus, today we distinguish two kinds of notation: 1 kB (read kilobyte) is 1000 bytes and 1 KiB (read kibyte) is 2¹⁰ = 1024 bytes.

4. For another example, see the separate article dealing with password security.

Resources and further reading

• Combinatorics at cuni.cz
• Bělohlávek, Vychodil: Discrete Mathematics [PDF]