Where permutations and combinations are used

Combinatorics

1. Permutations

  • \ (k = n \)
    (i.e. all elements \ (k \) of the basic set \ (n \) are considered)
  • The order of the elements is taken into account

1.1 Permutation without repetition

A Permutation without repetition is an arrangement of \ (n \) objects that are all distinguishable.

We have \ (n \) distinguishable objects that we want to arrange in a row next to each other in \ (n \) places.

There are \ (n \) placement options for the first object. For the second object there are \ ((n-1) \) possibilities, for the third object \ ((n-2) \) .... and for the last object there is only one possibility.

In mathematical notation, it looks like this:

\ (n \ cdot (n-1) \ cdot (n-2) \ cdot \ text {...} \ cdot 1 = n! \)

In short, you can write \ (n! \) For a permutation without repetition. This term is called "faculty".

example

There are five different colored balls in an urn. How many ways are there to arrange the balls in a row?

solution

\ (5! = 5 \ times 4 \ times 3 \ times 2 \ times 1 = 120 \)

Answer: There are 120 possibilities to arrange five different colored balls in a row.

>> You can find more on this topic in the chapter on permutation without repetition. <<

1.2 permutation with repetition

A Permutation with repetition is an arrangement of \ (n \) objects, some of which are indistinguishable.

We have already learned that there are \ (n \) ways to distribute \ (n \) distinguishable (!) Objects to \ (n \) places.

However, if exactly \ (k \) objects are identical, then these can be exchanged in their places without resulting in a new order. In this way, exactly \ (k! \) Arrangements are the same.

The number of permutations of \ (n \) objects, of which \ (k \) are identical, is calculated as follows

\ [\ frac {n!} {k!} \]

If there is not just one, but \ (s \) groups, each with \ (k_1, k_2 \ cdot \ text {...} \ cdot k_s \) identical objects, the formula reads

\ [\ frac {n!} {k_1! \ cdot k_2! \ cdot \ text {...} \ cdot k_s!} \]

example

There are three blue and two red balls in an urn. How many ways are there to arrange the balls in a row?

solution

\ [\ frac {5!} {3! \ cdot 2!} = \ frac {5 \ times 4 \ times 3 \ times 2 \ times 1} {(3 \ times 2 \ times 1) \ times (2 \ times 1)} = 10 \]

Answer: There are 10 ways to arrange three blue and two red balls in a row.

>> You can find more on this topic in the chapter on permutation with repetition. <<

2. Variations

  • \ (k (i.e. only one sample - i.e. \ (k \) elements of the basic set \ (n \) - is considered)
  • The order of the elements is taken into account

2.1 Variation without repetition

At a Variation without repetition \ (k \) are selected from \ (n \) objects taking into account the order, whereby each object can only be selected once.

There are \ (n \) placement options for the first object. For the second object there are (n-1) possibilities, for the third object (n-2) .... and for the last object there are still (n-k + 1) possibilities.

\ [n \ cdot (n-1) \ cdot (n-2) \ cdot \ text {...} \ cdot (n-k + 1) = \ frac {n!} {(n-k)!} \]

example

There are five different colored balls in an urn. Three balls should be drawn without replacing (= without repetition) and observing the order. How many options are there?

solution

\ [\ frac {5!} {(5-3)!} = \ frac {5!} {2!} = \ frac {5 \ times 4 \ times 3 \ times 2 \ times 1} {2 \ times 1 } = 5 \ times 4 \ times 3 = 60 \]

Answer: There are 60 ways to draw 3 out of 5 balls without replacing them, observing the order.

>> You can find more on this topic in the chapter on variation without repetition. <<

2.2 Variation with repetition

At a Variation with repetition \ (k \) are selected from \ (n \) objects taking into account the order, whereby objects can also be selected multiple times.

There are \ (n \) options for the first object. Since objects can be selected several times, there are also options for the second, third and kth object. The following applies accordingly:

\ [n \ cdot n \ cdot \ text {...} \ cdot n = n ^ k \]

example

There are five different colored balls in an urn. Three balls should be drawn with replacement (= with repetition) and observing the order. How many options are there?

solution

\ [5 ^ 3 = 5 \ times 5 \ times 5 = 125 \]

Answer: There are 125 possibilities to move 3 out of 5 balls with replacement, observing the order.

>> You can find more on this topic in the chapter on variation with repetition. <<

3. Combinations

  • \ (k (i.e. only one sample - i.e. \ (k \) elements of the basic set \ (n \) - is considered)
  • The order of the elements is not taken into account

3.1 Combination without repetition

At a Combination without repetition \ (k \) are selected from \ (n \) objects regardless of the order, whereby each object can only be selected once.

The only difference between a variation without repetition and a combination without repetition is the fact that in the combination - in contrast to the variation - the order of the objects does not matter.

We already know the formula for the variation without repetition

\ [\ frac {n!} {(n-k)!} \]

The \ (k \) selected objects can be arranged in \ (k! \) Different ways. However, since the order in the combination is irrelevant, the formula reads accordingly

\ [\ frac {n!} {(n-k)! \ cdot k!} = {n \ choose k} \]

\ ({N \ choose k} \) is also called the binomial coefficient.

example

There are five different colored balls in an urn. Three balls should be drawn without replacing (= without repetition) and without considering the order. How many options are there?

solution

\ [{5 \ choose 3} = 10 \]

Answer: There are 10 ways to move 3 out of 5 balls without replacing them, regardless of the order.

>> You can find more on this topic in the chapter on combining without repetition. <<

3.2 Combination with repetition

At a Combination with repetition \ (k \) are selected from \ (n \) objects regardless of the order, whereby objects can also be selected multiple times.

The only difference between a combination without repetition and a combination with repetition is the fact that the combination with repetition allows the objects to be selected more than once.

We already know the formula for the combination without repetition

\ [\ frac {n!} {(n-k)! \ cdot k!} = {n \ choose k} \]

By modifying the numerator and the denominator, we finally arrive at the formula for a combination with repetition

\ [\ frac {(n + k-1)!} {(n-1)! \ cdot k!} = {n + k-1 \ choose k} \]

example

There are five different colored balls in an urn. Three balls should be drawn with replacement (= with repetition) and regardless of the order. How many options are there?

solution

\ [{5 + 3-1 \ choose 3} = {7 \ choose 3} = 35 \]

Answer: There are 35 possibilities to move 3 out of 5 balls with replacement, regardless of the order.

>> You can find more on this topic in the chapter on combination with repetition. <<

Systematically solve combinatorial tasks

If you are dealing with combinatorics for the first time, you must first deal with the above formula and practice it. In an exam, however, you not only have to master the formula, but also know when to use which formula. (Very few teachers will write which case is next to the assignment.)

In combinatorial tasks, two questions arise:

  1. What formula do I have to use in this exercise?
  2. What's the formula

When it comes to the second question, only one thing helps: PRACTICE! (... and memorize!).

However, very few pupils and students have problems memorizing the formulas. It is more difficult to determine which formula to use for a specific task.

By systematic approach you get to the right formula quickly ...

Are all elements of the basic set relevant to the task?
(yes) -> permutation
Are all elements distinguishable from one another?
(yes) -> Permutation without repetition
(no) -> Permutation with repetition
(no) -> variation or combination
Does the order matter?
(yes) -> variation
Are all elements distinguishable from one another?
(in the urn model: without replacing?)
(yes) -> Variation without repetition
(no) -> Variation with repetition
(no) -> combination
Are all elements distinguishable from one another?
(in the urn model: without replacing?)
(yes) -> Combination without repetition
(no) -> Combination with repetition