Search for probability and statistics terms on Statlect
StatLect
Index > Mathematical tools

k-permutations

by , PhD

This lecture introduces k-permutations, a basic concept in combinatorial analysis. Before reading this lecture, you should read the lecture on permutations.

We first deal with k-permutations without repetition and then with k-permutations with repetition.

Table of Contents

k-permutation without repetition

A k-permutation without repetition of n objects is a way of selecting k objects from a list of n. The selection rules are:

  1. the order of selection matters (the same k objects selected in different orders are regarded as different k-permutations);

  2. each object can be selected only once.

A k-permutation without repetition is also simply called k-permutation.

The following subsections give a slightly more formal definition of k-permutation and deal with the problem of counting the number of possible k-permutations.

Definition of k-permutation without repetition

Let a_1, a_2,..., a_n be n objects. Let $s_{1}$, $s_{2}$, ..., $s_{k}$ be k ($kleq n$) slots to which k of the n objects can be assigned. A k-permutation (or k-permutation without repetition or simple k-permutation) of n objects from a_1, a_2,..., a_n is one of the possible ways to choose k of the n objects and fill each of the k slots with one and only one object. Each object can be chosen only once.

Example Consider three objects a_1, a_2 and $a_{3}$. There are two slots ($s_{1}$ and $s_{2}$) to which we can assign two of the three objects. There are six possible $2$-permutations of the three objects (six possible ways to choose two objects and fill the two slots with the two objects):[eq1]

Number of k-permutations without repetition

Denote by $P_{n,k}$ the number of possible k-permutations of n objects. How much is $P_{n,k}$ in general? In other words, how do we count the number of possible k-permutations of n objects?

We can derive a general formula for $P_{n,k}$ by filling the k slots in a sequential manner:

  1. First, we assign an object to the first slot. There are n objects that can be assigned to the first slot, so there are [eq2]

  2. Then, we assign an object to the second slot. There were n objects, but one has already been assigned to a slot. So, we are left with $n-1$ objects that can be assigned to the second slot. Thus, there are[eq3]and[eq4]

  3. Then, we assign an object to the third slot. There were n objects, but two have already been assigned to a slot. So, we are left with $n-2$ objects that can be assigned to the third slot. Thus, there are[eq5]and[eq6]

  4. An so on, until we are left with $n-k+1$ objects and only one free slot (the k-th).

  5. Finally, when only one free slot remains, we assign one of the remaining $n-k+1$ objects to it. Thus, there are[eq7]and[eq8]

Therefore, by the above sequential argument, the total number of possible k-permutations of n objects is[eq9]

$P_{n,k}$ can be written as[eq10]

Remembering the definition of factorial, we can see that the numerator of the above ratio is $n!$ while the denominator is [eq11], so the number of possible k-permutations of n objects is[eq12]

The number $P_{n,k}$ is usually indicated as follows:[eq13]

Example The number of possible $3$-permutations of $5$ objects is[eq14]

k-permutation with repetition

A k-permutation with repetition of n objects is a way of selecting k objects from a list of n. The selection rules are:

  1. the order of selection matters (the same k objects selected in different orders are regarded as different k-permutations);

  2. each object can be selected more than once.

Thus, the difference between k-permutations without repetition and k-permutations with repetition is that objects can be selected more than once in the latter, while they can be selected only once in the former.

The following subsections give a slightly more formal definition of k-permutation with repetition and deal with the problem of counting the number of possible k-permutations with repetition.

Definition of k-permutation with repetition

Let a_1, a_2,..., a_n be n objects. Let $s_{1}$, $s_{2}$, ..., $s_{k}$ be k ($kleq n$) slots to which k of the n objects can be assigned. A k-permutation with repetition of n objects from a_1, a_2,..., a_n is one of the possible ways to choose k of the n objects and fill each of the k slots with one and only one object. Each object can be chosen more than once.

Example Consider three objects a_1, a_2 and $a_{3}$ and two slots ($s_{1}$ and $s_{2}$). There are nine possible $2$-permutations with repetition of the three objects (nine possible ways to choose two objects and fill the two slots with the two objects, being allowed to pick the same object more than once):[eq15]

Number of k-permutations with repetition

Denote by $P_{n,k}^{prime }$ the number of possible k-permutations with repetition of n objects. How much is $P_{n,k}^{prime }$ in general? In other words, how do we count the number of possible k-permutations with repetition of n objects?

We can derive a general formula for $P_{n,k}^{prime }$ by filling the k slots in a sequential manner:

  1. First, we assign an object to the first slot. There are n objects that can be assigned to the first slot, so there are [eq16]

  2. Then, we assign an object to the second slot. Even if one object has been assigned to a slot in the previous step, we can still choose among n objects, because we are allowed to choose an object more than once. So, there are n objects that can be assigned to the second slot and[eq17]and[eq18]

  3. Then, we assign an object to the third slot. Even if two objects have been assigned to a slot in the previous two steps, we can still choose among n objects, because we are allowed to choose an object more than once. So, there are n objects that can be assigned to the second slot and[eq19]and[eq20]

  4. An so on, until we are left with only one free slot (the k-th).

  5. When only one free slot remains, we assign one of the n objects to it. Thus, there are:[eq21]and[eq22]

Therefore, by the above sequential argument, the total number of possible k-permutations with repetition of n objects is[eq23]

Example The number of possible $2$-permutations of $4$ objects is[eq24]

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

There is a basket of fruit containing an apple, a banana and an orange and there are five girls who want to eat one fruit. How many ways are there to give three of the five girls one fruit each and leave two of them without a fruit to eat?

Solution

Giving the 3 fruits to 3 of the 5 girls is a sequential problem. We first give the apple to one of the girls. There are 5 possible ways to do this. Then we give the banana to one of the remaining girls. There are 4 possible ways to do this, because one girl has already been given a fruit. Finally, we give the orange to one of the remaining girls. There are 3 possible ways to do this, because 2 girls have already been given a fruit. Summing up, the number of ways to assign the three fruits is equal to the number of 3-permutations of 5 objects (without repetition). If we denote it by $P_{5,3}$, then[eq25]

Exercise 2

An hexadecimal number is a number whose digits can take sixteen different values: either one of the ten numbers from 0 to 9, or one of the six letters from A to F. How many different 8-digit hexadecimal numbers are there, if an hexadecimal number is allowed to begin with any number of zeros?

Solution

Choosing the 8 digits of the hexadecimal number is a sequential problem. There are 16 possible ways to choose the first digit and 16 possible ways to choose the second digit. So, there are 16x16 possible ways to choose the first two digits. There are 16 possible ways two choose the third digit and 16x16 possible ways to choose the first two. Thus, there are 16x16x16 possible ways to choose the first three digits. An so on, until we have chosen all digits. Therefore, the number of ways to choose the 8 digits is equal to the number of 8-permutations with repetition of 16 objects:[eq26]

Exercise 3

An urn contains ten balls, each representing one of the ten numbers from 0 to 9. Three balls are drawn at random from the urn and the corresponding numbers are written down to form a 3-digit number, writing down the digits from left to right in the order in which they have been extracted. When a ball is drawn from the urn it is set aside, so that it cannot be extracted again. If one were to write down all the 3-digit numbers that could possibly be formed, how many would they be?

Solution

The 3 balls are drawn sequentially. At the first draw there are 10 balls, hence 10 possible values for the first digit of our 3-digit number. At the second draw there are 9 balls left, hence 9 possible values for the second digit of our 3-digit number. At the third and last draw there are 8 balls left, hence 8 possible values for the third digit of our 3-digit number. In summary, the number of possible 3-digit numbers is equal to the number of 3-permutations of 10 objects (without repetition). If we denote it by $P_{10,3}$, then[eq27]

How to cite

Please cite as:

Taboga, Marco (2021). "k-permutations", Lectures on probability theory and mathematical statistics. Kindle Direct Publishing. Online appendix. https://www.statlect.com/mathematical-tools/k-permutations.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.

Featured pages
Explore
Main sections
About
Glossary entries
Share
  • To enhance your privacy,
  • we removed the social buttons,
  • but don't forget to share.