Usar o princípio da inclusão e exclusão para achar o número de maneiras de se escolher 8 letras de uma coleção contendo
3 a’s, 3 b’s, e 4 c’s

Passo 1

O enunciado pede o número de modos de escolher 8 letras de um multiconjunto com 3 a's, 3 b's e 4 c's. Em termos de contagem, isso equivale a encontrar soluções inteiras não negativas (x_a,x_b,x_c) de
x_a + x_b + x_c = 8
sujeitas às restrições
0 \le x_a \le 3,\quad 0 \le x_b \le 3,\quad 0 \le x_c \le 4.
Vamos usar o princípio da inclusão e exclusão junto com o método “estrelas e barras”.

Passo 2

Contamos primeiro sem nenhuma restrição superior. Pelo método de estrelas e barras, o número de soluções não negativas de
x_a + x_b + x_c = 8
é
\binom{8 + 3 - 1}{3 - 1} \;=\;\binom{10}{2}\;=\;45.
Esse é o total sem considerar que há limite na quantidade de cada letra.

Passo 3

Definimos os conjuntos de soluções que violam cada limite:
A = soluções com x_a \ge 4,
B = soluções com x_b \ge 4,
C = soluções com x_c \ge 5.
Para \lvert A\rvert, fazemos y_a = x_a - 4\ge0, então
y_a + x_b + x_c = 8 - 4 = 4
tem
\binom{4 + 3 - 1}{3 - 1} \;=\;\binom{6}{2}\;=\;15.
Pela mesma razão, \lvert B\rvert = 15. Para \lvert C\rvert, fazemos y_c = x_c - 5\ge0, então
x_a + x_b + y_c = 8 - 5 = 3
que dá
\binom{3 + 3 - 1}{3 - 1} \;=\;\binom{5}{2}\;=\;10.

Passo 4

Agora as intersecções de duas violações:
  • A\cap B: x_a\ge4, x_b\ge4. Defina y_a=x_a-4, y_b=x_b-4; então y_a + y_b + x_c = 8 - 8 = 0e há \binom{0 + 3 - 1}{3 - 1} \;=\;\binom{2}{2}\;=\;1solução.
  • A\cap C: exigiria x_a\ge4 e x_c\ge5, levando a soma negativa 8-9=-1, logo \lvert A\cap C\rvert =0.
  • B\cap C: idem, soma fica 8-9=-1, logo \lvert B\cap C\rvert =0.
Intersecção tripla A\cap B\cap C também é impossível, pois 4+4+5>8.

Passo 5

Aplicamos o princípio da inclusão e exclusão:
\begin{aligned} N &= \text{total} - (\lvert A\rvert + \lvert B\rvert + \lvert C\rvert) + (\lvert A\cap B\rvert + \lvert A\cap C\rvert + \lvert B\cap C\rvert) - \lvert A\cap B\cap C\rvert,\\\ &= 45 - (15 + 15 + 10) + (1 + 0 + 0) - 0,\\\ &= 45 - 40 + 1 = 6. \end{aligned}

Resposta

O número de maneiras de escolher 8 letras sob essas condições é 6.

Exercícios relacionados