6 Combinatorics

If we want to count \(r\)-element sets created from a set of \(n\) elements, we can use one of the following formulas depending on the situation.

6.1 Variations

If the order in the created \(r\)-element sets matters, such sets (sequences) are called variations1.

If the elements of the variation are taken without replacement (they cannot be repeated), the number of possible variations is:

\[\begin{equation} \text{Number of outcomes} = \frac{n!}{(n-r)!} \tag{6.1} \end{equation}\]

If the elements of the variation can be repeated, the number of possible variations is:

\[\begin{equation} \text{Number of outcomes} = n^r \tag{6.2} \end{equation}\]

In the case of variations with repetitions, \(r\) can be greater than \(n\).

6.2 Combinations

Combinations are sets where the order does not matter, e.g., the arrangements {1; 2} and {2; 1} represent the same set.

When the elements are taken without replacement, to determine the number of combinations we can use the binomial coefficient

\[\begin{equation} \text{Number of outcomes} = \binom{n}{r} = \frac{n!}{r! \left( n-r \right)!} \tag{6.3} \end{equation}\]

Combinations with replacement can be counted using the formula:

\[\begin{equation} \text{Number of outcomes} = \binom{n+r-1}{r} = \frac{\left(n+r-1\right)!}{r! \left( n-1 \right)!} \tag{6.4} \end{equation}\]

6.3 Questions

Question 6.1 Propose an example where combinations with replacement are useful.

Question 6.2 In the case of combinations with replacement, can \(r\) be greater than \(n\)?

Question 6.3 What is the value of 0! (0 factorial)?

6.4 Exercises

Exercise 6.1 A collector has 16 medieval coins, but 6 of them are counterfeits. We randomly select 4 out of the 16 coins. What is the probability that all 4 selected coins will be counterfeits?

Exercise 6.2 How many possible combinations of numbers are there in Polish Lotto (6 out of 49)?

Exercise 6.3 On Saturday, October 8, 2022, the following numbers were drawn in Polish Lotto: 7, 20, 23, 25, 29, 43. How many combinations won a "three"?

Exercise 6.4 How many 8-character passwords can be created from 26 lowercase letters, 26 uppercase letters, 10 digits, and 4 special characters

  1. assuming characters can be repeated and there are no requirements like "at least one digit"?

  2. assuming characters cannot be repeated?

Exercise 6.5 Calculate:

  1. \[\frac{7!}{3!(7-3)!}\]

  2. \[5 \choose 3\]

  3. \[8 \choose 0\]

  4. \[5 \choose 5\]

  5. \[7 \choose 6\]

  1. Note! In older English textbooks, variations are called permutations, although this term is originally defined differently. In Polish, the word permutations is not used in this context. Other English names for variations are, according to wikipedia: r-permutation of n, partial permutation, sequence without repetition, or arrangement.↩︎