## 3.2Combinatorics

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, , volume 5 of and are recommended.

### 3.2.1Rule 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.

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.

• $$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.3Permutation

A permutation is an ordering of a set of objects.

• $$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.4Combination

A combination of a set of objects is an unordered selection of the objects. Repetitions may or may not be permitted.

• $$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.

### References

Berman, Gerald, and Kenneth D Fryer. 1972. Introduction to Combinatorics. Academic Press - New York; London.
Iezzi, G., and C. Murakami. 1977. Fundamentos de Matemática Elementar 1: Conjuntos, Funções. SP Editora Atual. https://barbosadejesu.files.wordpress.com/2021/09/fundamentos-da-matematica-elementar-1-.pdf.
Pólya, George, R Tarjan, and D Woods. 1983. “Notes on Introductory Combinatorics, Progress in Computer Science, No. 4.” Birkhauser, Boston, Basel, Stuttgart.