Problemas de Combinatória e Teoria dos Grafos

Prévia do material em texto

439. Questão: Se \( A = \{a, b, c, d\} \), quantos subconjuntos podem ser formados 
contendo pelo menos 2 elementos? 
 Resposta: O número de subconjuntos é \( 2^4 - \binom{4}{1} - \binom{4}{0} = 14 \). 
 
440. Questão: Se \( n = 87 \), qual é o valor de \( \binom{n}{2} - \binom{n}{3} + \binom{n}{4} 
\)? 
 Resposta: O valor é \( \binom{87}{2} - \binom{87}{3} + \binom{87}{4} = 3786 - 65610 + 
1009470 = 944646 \). 
 
441. Questão: Qual é o número mínimo de cores necessárias para colorir um grafo 
completo com 60 vértices? 
 Resposta: O número mínimo de cores é 60. 
 
442. Questão: Se \( A = \{1,2,3,4,5\} \), quantos subconjuntos podem ser formados 
contendo exatamente 2 elementos? 
 Resposta: O número de subconjuntos é \( \binom{5}{2} = 10 \). 
 
443. Questão: Determine o número de soluções inteiras não negativas da equação \( x_1 + 
x_2 + x_3 = 66 \). 
 Resposta: O número de soluções é \( \binom{66 + 3 - 1}{3 - 1} = \binom{68}{2} = 2278 \). 
 
444. Questão: Se \( |A| = 64 \) e \( |B| = 65 \), quantos elementos existem em \( A \times B 
\)? 
 Resposta: O número de elementos em \( A \times B \) é \( 64 \times 65 = 4160 \). 
 
445. Questão: Determine o valor de \( \sum_{k=1}^{295} k^2 \). 
 Resposta: O valor é \( \frac{295(295 + 1)(2 \times 295 + 1)}{6} = 14800325 \). 
 
446. Questão: Se \( n = 88 \), qual é o valor de \( \binom{n}{3} - \binom{n}{4} + \binom{n}{5} 
- \binom{n}{6} \)? 
 Resposta: O valor é \( \binom{88}{3} - \binom{88}{4} + \binom{88}{5} - \binom{88}{6} = 
156424 - 2752512 + 42353664 - 558702144 = -516902468 \). 
 
447. Questão: Qual é o número máximo de arestas em um grafo simples com 61 vértices?