3.2 Combinatória
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)
Neste texto será considerada a abordagem enumerativa, com foco na contagem. Para aprofundar este tópico recomendam-se (Berman and Fryer 1972), o volume 5 de (Iezzi and Murakami 1977) e (Pólya, Tarjan, and Woods 1983).
3.2.1 Princípio fundamental da contagem
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)
Se deseja-se combinar \(n_1\) objetos do tipo 1 com \(n_2\) objetos do tipo 2, …, com \(n_k\) objetos do tipo \(k\), o total de possibilidades é \[\begin{equation} T = n_1 \, n_2 \ldots n_k \tag{3.15} \end{equation}\]
Exemplo 3.11 Se João tem 3 calças, 4 blusas e 2 bonés, pode combiná-los de \(T=3 \times 4 \times 2 = 24\) formas distintas e \(k=3\).
3.2.2 Arranjo
By an \(r\)-arrangement of \(n\) distinct objects we mean an ordered selection of \(r\) of the objects. (Berman and Fryer 1972, 38)
- \(n\) elementos tomados \(x\) a \(x\)
- muda ordem
- muda natureza (elemento)
Simples (sem repetição de elementos nos subconjuntos) \[\begin{equation} A_{n}^{x} = \frac{n!}{\left( {n - x} \right)!} \tag{3.16} \end{equation}\]
3.2.3 Permutação
A permutation is an ordering of a set of objects. (Pólya, Tarjan, and Woods 1983, 6)
- arranjo em que \(n=x\)
- muda ordem
Simples (sem repetição de elementos) \[\begin{equation} P_{n} = n! \tag{3.17} \end{equation}\]
Com repetição dos elementos 1 a \(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 Combinação
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\) elementos tomados \(x\) a \(x\), cada subconjunto constituído de \(x\) elemetos
- muda natureza (elemento)
O coeficiente binomial é dado por \[\begin{equation} C_{n}^{x} = {n \choose x} = {n \choose n-x} = \frac{n!}{x!\left( {n - x} \right)!} \tag{3.19} \end{equation}\]
Exercício 3.2 Realize os exercícios disponíveis na unidade de Contagem, permutações e combinações do Khan Academy.
Exercício 3.3 Leia o resumo e faça os exercícios do Capítulo 1 dos Exercícios de Probabilidade do professor Élcio Lebensztayn.