3.2 Combinatorics
Combinatorics can be classified into three types: enumerative, existential, and constructive. Enumerative combinatorics deals with the counting of combinatorial objects. Existential combinatorics studies the existence or nonexistence of combinatorial configurations. Constructive combinatorics deals with methods for actually finding specific configurations. (Pólya, Tarjan, and Woods 1983, prefácio)
In this text, the enumerative approach will be considered, focusing on counting. To deepen this topic, (Berman and Fryer 1972), volume 5 of (Iezzi and Murakami 1977) and (Pólya, Tarjan, and Woods 1983) are recommended.
3.2.1 Rule of product
If a set of objects can be separated or partitioned into \(k\) nonempty disjoint subsets, and if each of these subsets can be separated into \(m\) nonempty disjoint subsets, then the original set can be separated into \(km\) nonempty disjoint subsets. (Berman and Fryer 1972, 33)
If we wish to combine \(n_1\) objects of type 1 with \(n_2\) objects of type 2, …, with \(n_k\) objects of type \(k\), the total possibilities are \[\begin{equation} T = n_1 \, n_2 \ldots n_k \tag{3.15} \end{equation}\]
Example 3.11 If John has 3 pants, 4 shirts and 2 hats, he can combine them in \(T=3 \times 4 \times 2 = 24\) different ways and \(k=3\).
3.2.2 \(r\)-Arrangement
By an \(r\)-arrangement of \(n\) distinct objects we mean an ordered selection of \(r\) of the objects. (Berman and Fryer 1972, 38)
- \(n\) elements taken from \(x\) to \(x\)
- change order
- changes nature (element)
Simple (no repetition of elements in subsets) \[\begin{equation} A_{n}^{x} = \frac{n!}{\left( {n - x} \right)!} \tag{3.16} \end{equation}\]
3.2.3 Permutation
A permutation is an ordering of a set of objects. (Pólya, Tarjan, and Woods 1983, 6)
- \(r\)-arrangement where \(n=x\)
- change order
Simple (no repeating elements) \[\begin{equation} P_{n} = n! \tag{3.17} \end{equation}\]
With repetition of elements 1 to \(k\). \[\begin{equation} P_{n}^{n_{1},\ldots,n_{k}} = \frac{n!}{n_{1}! n_{2}! \ldots n_{k}!} \tag{3.18} \end{equation}\]
3.2.4 Combination
A combination of a set of objects is an unordered selection of the objects. Repetitions may or may not be permitted. (Berman and Fryer 1972, 42)
- \(n\) elements taken from \(x\) to \(x\), each subset consisting of \(x\) elements
- changes nature (element)
\[\begin{equation} C_{n}^{x} = {n \choose x} = {n \choose n-x} = \frac{n!}{x!\left( {n - x} \right)!} \tag{3.19} \end{equation}\]
Exercise 3.1 Perform the exercises available in the Khan Academy Counting Permutations and Combinations unit.
Exercise 3.2 Read the summary and do the exercises in Chapter 1 of Probability Exercises by professor Élcio Lebensztayn.