Combinatorics helps determine the number of possible arrangements (also called permutations) or selections (called variations or combinations) of objects in experimental outcomes.
In the case of an arrangement or permutation, all elements of the basic set are considered, whereas in the case of selections, either variations or combinations, only a sample of the basic set is the focus of interest. There are also ordered and unordered samples, depending on whether the order of the elements is taken into account, as in variation, or not, as in combination. In the case of arrangements or permutations, the order is always taken into account.
Combinatorics has numerous applications in various areas of mathematics, such as geometry, probability theory, algebra, set theory, and topology. It is also used in computer science and theoretical physics.
Important concepts of combinatorics
In order to understand the specific cases and formulas, you should first have a good overview of the most important basic terms in combinatorics.
What is a faculty?
The notation of the factorial is n! (pronounced «n faculty»). The factorial, sometimes also called factorial, can be used to determine how many ways there are to arrange n objects in a set. The factorial can be calculated by multiplying all natural numbers from 1 to n:
«n» stands for the number from which the factorial is to be formed.
What is the binomial coefficient?
The binomial coefficient tells how many different ways you can choose k objects from a set of n different objects. Written out, the formula for the coefficient looks like this:
N over k is the factorial of n divided by the factorial of k multiplied by the factorial of nk.
What is the k-tuple?
A k-tuple is a collection of k numbers that may be repeated and whose order is important. For example: (1,2,3,4) is a 4-tuple and (1,2,3,4)(1,2,4,3)
What is the k set?
A k-set is a collection of k numbers, with no regard for repetition or order. For example: {6,6,5} = {6,5} and {7,3,1} = {1,3,7}
k-permutation (H3)
What is a permutation?
A k-permutation is a collection of k non-repeating numbers whose order is important. k-permutations are thus a special case of k-tuples. For example: (1,2,3,4) is a 4-permutation, but (1,2,3,3) is not, since the 3 occurs twice.
What is a combination?
A k-combination is a collection of k numbers in which order is not respected, but there is repetition. k-combinations are thus a special case of k-sets. For example: {6,6,5} {6,5} and {7,3,1} = {1,3,7}
Combinatorics formulas
For the calculations of the combinatorics, different formulas are required for permutations, combinations and variations. The n in the formulas always stands for the number of all elements, i.e. for the total population. The k indicates the number of draws.
In order to find out which formula to use, the following questions are useful:
- Am I looking at all items or just a sample?
- Does the order matter?
- Can the elements occur with repetition?
The graphic gives an overview of which formulas are used when:
via studyhelp.de
We now look at the specific cases.
permutations
In the case of permutations, it is generally the case that all elements of the population are taken into account. So n = k. The order is always taken into account here. One must now distinguish between the cases with repetition and without repetition.
Permutation without repetition is the arrangement of objects that are all different. The goal is to arrange all objects in a certain order. At the beginning all places are still free, but only n-1 possibilities remain for the second object, for the third similarly n-2 and so on. If you continue this series, you get the factorial n!, the formula for calculating the number of possibilities. The central point is that all objects in the set are different and therefore no object with the same characteristics can appear twice.
In the case of a permutation with repetition, on the other hand, not all objects can be distinguished from one another. It can therefore happen that the order itself does not change, even if two objects with the same characteristics are exchanged. You can form groups that summarize the objects with the same characteristics.
The number of possibilities is then calculated using the following formula:
variations
In the case of variations, k < n applies. For the calculations, only a few objects are selected from the basic set, so it is a random sample. It should be noted that the order of selection is decisive for the result.
In the variation without repetition, each object occurs only once, the object may not be replaced. There are still n placement options for the first object, n-1 options remain for the second, and so on. Consequently, there are still n-k+1 possibilities for the last object.
The following formula is obtained for the variations:
There is also a variation with repetition. In this case, objects can also be selected more than once. This means that some objects are not distinguishable. This can also be the case if the object is returned to the other elements after it has been selected. As before, there are n selection options for the first object; due to the multiple selection, this now also applies to all other objects.
So you calculate:
combinations
If one now considers the combinations, it is again the case that k < n. It is therefore again a question of a selection of objects from the basic set. The difference to the variations is that here the order does not matter. Again, there is the case of no repetition and the case of repetition.
Once you have selected an object, it cannot appear again. So the selected objects k can only be on k! different places are distributed. With the formula for variations without repetition in mind, one can easily derive the formula for this case.
The formula for the combinations is:
Another possible scenario is that the order of the outcomes of the random experiment doesn’t matter and the outcome may occur again if it has already occurred. The formula for the non-repetition case can be easily adapted.
This results in the following formula:
How do you solve combinatorics problems?
Now let’s look at two concrete examples of combinatorics exercises, so that you not only master the formulas theoretically, but can also apply them well.
Task 1:
You forgot the code for your mobile phone. How many possibilities are there when you at least remember that your code was four characters long?
When calculating combinatorics problems, the following questions are helpful:
-
Am I looking at all items or just a sample?
Only one random sample is considered, since only 4 of the 10 possible digits from 0-9 are selected.
-
Does the order matter?
Yes, of course the order matters to unlock the phone.
-
Can the elements occur with repetition?
Yes, you can theoretically use the same digit four times.
If you now follow the solution tree, which is shown earlier in the article, you get to the formula and the associated solution with .
Exercise 2:
You have a bowl of alphabet soup in front of you. You see that the letters are still swimming in your plate to form the word Mississippi. How many ways do you have to arrange the letters?
Again, you ask yourself the same questions as in the previous task. All elements are considered here, since all letters are to be built into the new word. The order also plays a role in this case.
Task 3:
This is not an urn model with replacement, but the elements can still appear repeatedly, it makes no difference whether you use the first or the second s first. The following formula is used for the calculation:
This gives the result:
Everything you need to know about combinatorics at a glance:
You have already understood the most important facts, formulas and examples in the field of combinatorics. So that you are well prepared for your next exam and don’t forget anything, here is an overview of the most important information. So nothing stands in the way of your next successful exam!
- Combinatorics helps determine the number of possible arrangements/permutations or selections (variations or combinations) of objects in experimental outcomes.
- For the calculations of the combinatorics, different formulas are required for permutations, combinations and variations. The n in the formulas always stands for the number of all elements, i.e. for the total population. The k indicates the number of draws.
- In order to find out which formula to use, it is useful to ask the following questions: Am I looking at all the elements or just a sample? Does the order matter? Can the elements occur with repetition?
- For permutations, n = k. The order is always taken into account here.
- In the case of variations, k < n applies, the order is decisive for the result.
- In the case of combinations, k < n again applies, but the order is irrelevant here.