Problema 2.1
Uma senha de um certo sistema de computador deveria ter de quatro a oito caracteres e conter letras minúsculas e/ou maiúsculas. Quantas senhas são possíveis?
Para resolver o problema, o raciocínio pode partir do princípio de que as senhas podem ter quatro, cinco, seis, sete ou oito caracteres. Como o conjunto de todas as senhas é a união dos conjuntos com senhas de tamanho quatro a oito, podemos usar o princípio da adição.
Considere $P_i$ como o conjunto das senhas com $i$ caracteres e $P$ é o conjunto com todas as senhas.
\begin{align*} P = P_4 \cup P_5 \cup P_6 \cup P_7 \cup P_8 \end{align*}Assim:
\begin{align*} \left|P\right| = \sum_{i = 4}^8 \left|P_i\right| \end{align*}Calculando $\left|P_i\right|$: para uma senha com $i$ letras existem 52 escolhas para a primeira letra, 52 para a segunda e assim por diante. Pelo princípio do produto:
\begin{align*} \left|P\right| = 52^i \end{align*}Portanto:
\begin{align*} \left|P\right| = 52^4 + 52^5 + 52^6 + 52^7 + 52^8 \end{align*}Princípio do produto (versão 2)
Se um conjunto $S$ de listas de comprimento $m$ tem propriedades que:
Ao aplicar esse princípio ao Problema 2.1 temos: como uma senha com $m$ letras é uma lista com $m$ elementos, e por existirem 52 primeiros elementos diferentes da senha e 52 escolhas para cada outra posição da senha, temos que $i_1 = 52, i_2 = 52, ..., i_m = 52$, assim, o número de senhas de comprimento $m$ é $i_1 \times i_2 \times ... \times i_m = 52^m$.
Definição formal de lista:
Uma lista de $k$ coisas escolhidas a partir de $T$ consiste em um primeiro membro de $T$ até o $k$-ésimo membro de $T$. Por exemplo, uma lista de 3 coisas escolhidas de um conjunto $T$ consiste nos elementos $t_1, t_2, t_3$. Os elementos da lista não são, necessariamente, diferentes uns dos outros. Se a lista for escrita em uma ordem diferente, será uma lista diferente.
Uma função de um conjunto $S$ (o domínio) para um conjunto $T$ (o contradomínio) é um relacionamento entre os elementos de $S$ e $T$. Por exemplo:
\begin{align*} f(1) = Sam \\ f(2) = Mary \\ f(3) = Sarah \end{align*}indica que $f$ é uma função que descreve uma lista de três nomes. Assim, temos uma definição mais precisa de lista: uma lista de $k$ elementos a partir de um conjunto $T$ é uma função de $\{1, 2, ..., k\}$ para $T$.
Outra lista seria:
\begin{align*} f(1) = Mary \\ f(2) = Sarah \\ f(3) = Sam \end{align*}De outra forma, uma função $f$ de um conjunto $S$ para um conjunto $T$ é um relacionamento entre $S$ e $T$ que relaciona exatamente um elemento de $T$ a cada elemento de $S$. Escrevemos $f(x)$ para cada elemento de $T$ relacionado ao elemento $x$ de $S$. O mesmo elemento de $T$ pode estar relacionado a diferentes membros de $S$.
Exercício 2.1: Quais são as funções do conjunto $\{1, 2\}$ para o conjunto $\{a, b\}$?
Para resolver a questão, precisamos especificar $f_i(1)$ e $f_i(2)$:
\begin{matrix} f_1(1) = a & f_1(2) = b\\ f_2(1) = b & f_2(2) = a\\ f_3(1) = a & f_3(2) = a\\ f_4(1) = b & f_4(2) = b\\ \end{matrix}O conjunto de todas as funções do conjunto $\{1, 2\}$ para o conjunto $\{a, b\}$ é a união entre as funções $f_i$ com $f_i(1) = a$ e aquelas com $f_i(1) = b$. O conjunto de funções com $f_i(1) = a$ tem dois elementos, um para cada escolha de $f_i(2)$:
Pelo princípio do produto, a resposta para a questão é $2 \times 2 = 4$.
O número de funções do conjunto $\{1, 2\}$ para o conjunto $\{a, b, c\}$ é $3 \times 3 = 9$.
O número de funções do conjunto $\{1, 2, 3\}$ para o conjunto $\{a, b\}$ é $4 \times 2 = 8$.
Uma função $f$ de um conjunto $S$ para um conjunto $T$ é chamada um a um, ou injetora, se, para cada $x \in S$ e $y \in S$, com $x \neq y$, $f(x) \neq f(y)$. No Exercício 2.1, as funções $f_1$ e $f_2$ são injetoras, mas $f_3$ e $f_4$ não são.
Uma função $f$ de um conjunto $S$ para um conjunto $T$ é chamada sobrejetora se, para cada elemento $y \in T$ (no contradomínio), existe pelo menos um $x \in S$, tal que $f(x) = y$. No Exercício 2.1, as funções $f_1$ e $f_2$ são sobrejetoras, mas $f_3$ e $f_4$ não são.
Uma função ao mesmo tempo injetora e sobrejetora é chamada bijetora.
Uma bijeção de um conjunto para si mesmo é chamada permutação do conjunto.
Exemplo 2.2: Determinar o número de triângulos formados por $n$ pontos no plano.
c = 0
para i = 1 até n
para j = i + 1 até n
para k = j + 1 até n
se os pontos i, j e k são colineares então
c = c + 1Quando $n = 4$, então as triplas $(i, j, k)$ (os pontos para verificação de colinearidade) são: $(1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)$. Podemos perceber que $i < j < k$.
O número das triplas é o número de subconjuntos com três elementos de um conjunto com $n$ elementos.
Uma lista de $k$ elementos distintos de um conjunto $N$ é chamada permutação de $k$ elementos de N.
Existem $n$ escolhas para o primeiro elemento da lista, para cada uma existem $(n - 1)$ escolhas para o segundo. Para cada escolha dos dois primeiros elementos da lista, há $(n - 2)$ formas de escolher o terceiro elemento, e assim por diante. Por exemplo, se $N = \{1, 2, 3, 4\}$, as permutações de $k = 3$ elementos são:
\begin{align*} L = \{123, 124, 132, 134, 142, 143, \\ 213, 214, 231, 234, 241, 243, \\ 312, 314, 321, 324, 341, 342, \\ 412, 413, 421, 423, 431, 432 \} \end{align*}Ou seja, existem $4 \times 3 \times 2 = 24$ listas com $k = 3$ elementos em $N$. Pelo princípio do produto (versão 2) isso é $n \times (n - 1) \times (n - 2)$.
Dados os primeiros $i - 1$ elementos da lista, temos $n - (i - 1) = n - i + 1$ escolhas para o $i$-ésimo elemento da lista.
Pelo princípio do produto (versão 2) temos $n \times (n - 1) \times ... \times (n - k + 1)$ maneiras de escolher permutações de $k$ elementos de $N$. De outra forma:
\begin{align*} n \times (n - 1) \times ... \times (n - k + 1) = \prod_{i = 0}^{k-1} (n - i) \end{align*}Teorema 2.1
O número de permutações de $k$ elementos de um conjunto de $n$ elementos é:
\begin{align*} n \times (n - 1) \times ... \times (n - k + 1) = \prod_{i = 0}^{k-1} (n - i) = \frac{n!}{(n-k)!} \end{align*}Usamos anteriormente $\binom{n}{3}$, que lemos "$n$ termos, 3 a 3", para representar o número de subconjuntos com três elementos do conjunto $\{1, 2, ..., n\}$.
O número de subconjuntos de $k$ elementos do conjunto $\{1, 2, ..., n\}$ é $\binom{n}{k}$, que lemos como "$n$ termos, $k$ a $k$".
Como o número de permutações de $k$ elementos de um conjunto com $k$ elementos é $k!$ temos:
\begin{align*} \frac{n!}{(n-k)!} = \binom{n}{k} \times k! \end{align*}Isso dá o Teorema 2.2:
Para inteiros $n$ e $k$, com $0 \leq k \leq n$, o número de subconjuntos de $k$ elementos de um conjunto de $n$ elementos é:
\begin{align*} \binom{n}{k} = \frac{n!}{k! \times (n - k)!} \end{align*}Outra notação para isso é $C(n, k)$, os chamados coeficientes binomiais.