Arrangements with repetition

Arrangements with repetition are similar to ordinary k-permutations, except that we allow the elements of the underlying 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 alphabet (abc … xyz, there are 26 of them) if the word has to be 6 letters long? Six letters is not many, but there will still be quite a lot of words. We don’t care about meaning, so even “weqrww” counts as a valid six-letter word.

To work this out we only need the product rule for counting. We have 26 different letters to use. In the first place we can put one of the 26 letters. In the second place we can also put one of the 26 letters, because we set no condition that letters must not repeat. So in every position we choose from 26 letters, and by the product rule the total number of arrangements is 26⁶ = 308,915,776. That is quite a lot, considering we only used 26 letters.

We say that a k-element arrangement with repetition from a set M of size n is any ordered k-tuple whose elements come from M, where each element may appear in the k-tuple up to k times. So if M = {1, 2, 3}, then all of these are valid 4-element arrangements with repetition: (1, 1, 1, 1), (1, 2, 3, 1), (2, 2, 3, 3). There are n choices for each of the k positions, so the number of such arrangements is

$$n^k.$$

Worked examples

1. How many six-digit numbers can be made from the digits {2, 4, 6, 8} if digits may be repeated? We simply substitute into the formula: the set has size n = 4 and we choose 6 digits, k = 6:

   $$4^6=4096.$$

2. Computers commonly use the binary number system, which uses only the digits 0 and 1. It introduces new units: for example, one bit is a cell that stores either a zero or a one. A larger unit is the byte, which contains 8 bits. So 1 is one bit, while 01110001 is one byte. In how many different ways can we fill one byte with 8 bits?

   We choose from the set {0, 1}, that is, from two elements. We choose a k-tuple of length k = 8, so the number of all possibilities is

   $$2^8=256.$$

3. From the previous example we know that one byte can distinguish up to 256 different values. In how many ways can we fill 4 bytes?

   Four bytes contain 4 · 8 = 32 bits, and we are still choosing from a set of size 2. So the result is:

   $$2^{32}=\mathrm{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 so 8,000,000,000,000 bits. On a terabyte disk we could therefore store up to 2^{8,000,000,000,000} different values.

   Note: there is currently some confusion about the term kilobyte (megabyte and so on). For technical reasons, one kilobyte used to mean not 1,000 bytes, as the prefix does in other units (one kilogram is one thousand grams), but 2¹⁰ bytes, which is 1024 bytes. One megabyte was then 2²⁰ bytes, or 2¹⁰ kilobytes.

   These days we distinguish two notations: 1 kB (kilobyte) is 1,000 bytes and 1 KiB (kibibyte) is 2¹⁰ = 1024 bytes.

4. Another example can be found in a separate article about password security.