Matemática Discreta - Aula 05
Análise Combinatória
Trata-se de formas de se analisar a quantidade possível de agrupamentos de elementos. ^3e01a1
Depende da natureza dos elementos, da forma que inserimos estes elementos.
Princípio Aditivo
Dados os conjuntos $A_1, A_2, \dots, A_n$ dois a dois dijuntos (significa que não temos elementos em comum), em que $A_i$ possui exatamente $a_i$ elementos, então a quantidade de elementos da União $A_1 \cup A_2 \cup \dots \cup A_n$ é dado por: $$ q = a_1 + a_2 + \dots + a_n $$
Exemplo
Considere três matérias distintas, onde na primeira o professor passe 2 trabalhos, na segunda 5 e na terceira 4. Assim, $n(m_1) = 2 \ \ n(m_2)= 5 \ \ n(m_3)=4 \quad ••• q = 2 + 5 + 4 \implies q=11$
Princípio Multiplicativo
Se algo ocorre $m_1$ vezes em um “percurso”, $m_2$ em outro e assim sucessivamente, temos: $m_1 × m_2 × \dots × m_n$
Exemplo
Considere 4 salas que você precisa passar da primeira para a última, passando por todas as outras. Da 1ª para a 2ª aula temos 3 corredores, da 2ª para a 3ª 2 corredores, e da 3ª para quarta temos 5 corredores. Quantas maneiras temos de chegar da 1ª para a 4ª?
$$ 2 × 3 × 5 = 30 $$ Portanto, existem 30 maneiras de sair da primeira sala até a última.
Permutação simples
É o número de organizar $n$ elementos em $n$ posições, NÃO HAVENDO ELEMENTOS REPETIDOS É representado por: $P_n = n!$ (n fatorial).
[!info] Fatorial $n! = n × (n-1) × (n-2) × \dots × (n=1)$ Isto é, você irá multiplicar o número e subtrair dele até que ele seja 1. Isto nada mais nada menos é um modo de [[#Princípio Multiplicativo]]
[!note] Observação Sendo o princípio multiplicativo, podemos “parar” o fatorial no número que quisermos, pois: $n! = n×(n-1)!$ tendo em vista que, num breve exemplo $3! = 3×2×1 \text{ E } 2!=2×1 \quad \implies 3! = 3×2!$ Isto é bom para faciltar operações complexas como: $\frac{50!}{49!} \implies \quad \frac{50×\cancel{49!}}{\cancel{49!}} = 50$
[!important] E o fatorial de 0? Fatorial de 0 = 1, pois: $1! = 1×0! \quad \implies 1 × 1 = 1$
^c60fff
Ainda sobre [[#Permutação simples]]:
- n elementos não repetidos
- n posições
- A ordem dos elementos importa.
Arranjo Simples
No Arranjo a ordem também importa, no entanto a diferença delas é que, no arranjo, temos $n$ elementos para $k$ posições, onde $k <= n$.
$$ A_{n,k} = \frac{n!}{(n-k)!} $$
Exemplo
Se temos dois dígitos para formar com os números $1,\ 2,\ 3,\ 4,\ 5$, temos: $$ A_{5,2} = \frac{5!}{(5-2)!} \quad \implies \frac{5×4×\cancel{3!}}{\cancel{3!}} \implies =20 $$
Quando o $k$ for igual a $n$, teremos um fatorial de 0 na divisão, e $0!$ = 1, então é o mesmo que estivéssemos fazendo uma permutação simples.
Combinação Simples
N elementos e K posições onde a ordem dos elementos NÃO importa. $$ C_{n,k} = \frac{n!}{k! \ × \ (n-k)!} $$
Exemplo
Considere 5 frutas distintas (A → E). Determine o número de sucos distintos a se preparar batendo duas frutas juntas.
$$ \begin{align} C_{5,2} = \frac{5!}{2! ×(5-2)!} \ \frac{5×4×\cancel{3!}}{2! × \cancel{3!}} \ \frac{20}{2} = 10 \end{align} $$
Exercícios em aula (terça-feira, 21:37:15)
1. Indivíduo vai escolher um computador. 3 modelos de marca A, 5 Modelos da marca B e 2 Modelos da marca C. Quantos computadores difirentes ele pode escolher?
$$ 3+5+2 = 10 \implies \text{10 computadores para que ele escolha} $$
2. Vetor com 5 posições, apenas letras da palavra FATEC podem ir em uma posição. Determine o número de anagramas possíveis
$$ P_5 = 5! = 120 \text{ anagramas possiveis} $$
3. Em fila indiana, 6 homens e 6 mulheres
a) em qualquer ordem
$$ P_{12} = 12! = 479001600 \text{ posições distintas} $$
b) Iniciando com um homem e terminando com uma mulher
$$ 10! × (6×6) = 3628800 × 36 = 130636800 \text{ posições distintas com homem no início e mulher no fim} $$
4. Senha de 8 caracteres com 62 possíveis caracteres distintos (maíuscula, minúscula e números), supondo que nenhum caractére se repita
$$ \begin{align} A_{62,8} = \frac{62!}{(62-8)!} = \quad \frac{62×61×60×59×58×57×56×55×\cancel{54!}}{\cancel{54!}} \ 62×61×60×59×58×57×56×55 = \ \ = 1,363258933×10^{14} \end{align} $$
5. Um técnico de segurança precisa testar as senhas da empresa. A regra das senhas é: 4 letras distintas (das 26 do alfabeto - não importa maíuscula ou minúscula) e 2 dígitos que não se repetem (0-9, isto é, 10 dígitos)
a) Quantas são as senhas possíveis?
$$ \begin{align} A_{26,4} × A_{10,2} \ \ \frac{26×25×24×23×\cancel{22!}}{\cancel{22!}} \ \ \frac{10×9×\cancel{8!}}{\cancel{8!}} \ \ (26×25×24×23) × (10×9) = \ \ 358800 × 90 = 32292000 \end{align} \qquad \text{Portanto: são 32292000 possibilidades de Senha} $$
b) Quantas senhas apresentam, simultaneamente, apenas consoantes e algarismos maior que 5
$$ \begin{align} A_{23,4} × A_{4,2} \ \ \frac{23×22×21×20×\cancel{19!}}{\cancel{19!}} \ \ \frac{4×3×\cancel{2!}}{\cancel{2!}} \ \ (23×22×21×20) × (4×3) = \ 212520 × 12 \ = 2550240 \ \qquad \text{Portanto, devida as proposições → serão 2550240 senhas} \end{align} $$
Permutação com Repetição
[!note] Regrinhas
- Ordem Importa
- N elementos
- N Posições
- Dentro dos elementos, há repetição de $n_i$
Fórmula da permutação com Repetição
$$ P_n^{n_1, n_2, \dots, n_i} = \frac{n!}{n_1! × n_2! × \dots × n_i!} $$
Exemplos
A palavra PAPALÉGUAS possui dois Ps e três As dentro de seus 10 elementos. Assim, podemos dizer que temos 10 elementos onde o elemento $n_1$ possui 2 repetições, e o elemento $n_2$ possui 3 repetições.
$$ \begin{align} P_{10}^{2,3} = \frac{10!}{2! × 3!} \ \ \frac{10×9×8×7×6×5×4×3×\cancel{2!}}{(3×2×1)×\cancel{2!}} \ \ \frac{10×9×8×7×\cancel6×5×3}{\cancel6} = 302.400 \end{align} $$
Ou seja, temos 302mil e 400 possibilidades de anagramas com a palavra Papaléguas, tendo em vista a repetição no P e no A sendo duas e três vezes, respectivamente.
Arranjo com Repetição
[!note] Regrinhas Ordem importa n elementos k posições com n podendo haver repetições
Fórmula
$$ AR_{n,k} = n^k $$
Exemplos
Tenho os números $5 - 3 - 9$ e quero criar números com dois dígitos podendo repetir os elementos. Assim, temos duas posições e 3 possibilidades para cada uma das posições. Seguindo o [[Aula 05 - MMD001#Princípio Multiplicativo]] temos 3 × 3 possibilidades, também sendo considerado $3^2$, sendo 3 elementos em 2 posições.
Exercício
Quantidade de números distintos que podemos formar com quatro dígitos, podendo repetir dentre os seguintes: $1, 2, 3, 4, 5, 6, 7, 8, 9$. $$ AR_{9,4} = 9^4 = 6.561 $$
Combinação com Repetição
[!note] Regrinhas Ordem não importa n elementos k posições Pode haver repetição de elementos
Fórmula
$$ CR_{n,k} = \frac{(n+k=1)!}{k!×(n-1)!} $$
Exemplo
Considero 5 frutas dadas por A, B, C, D, E. Determine os sucos distintos que podem ser feitos com duas frutas, podendo repetir a fruta.
$$ CR_{5,2} = \frac{(5+2-1)!}{2! × (5-1)!} \quad \implies \frac{6!}{2!×4!} \implies \frac{6×5×\cancel{4!}}{2×\cancel{4!}} = 30/2 = 15. $$