Ir ao conteúdo principal

Análise Combinatória e Probabilidade: Com Aplicações no SageMath

Ricardo Machado, Gabriel Guedes, Luiz Manoel

Seção 2.1 Princípio da Inclusão-Exclusão

Subseção 2.1.1 O Princípio da Inclusão-Exclusão para 2 e 3 conjuntos

Demonstração.

Sejam \(A\) e \(B\) conjuntos finitos, \(T_1\) a tarefa de selecionar um elemento de \(A\) e \(T_2\) a tarefa de selecionar um elemento de \(B\text{.}\)
Existem \(\#A\) maneiras de realizar \(T_1\) e \(\#B\) maneiras de realizar \(T_2\text{.}\) O número de maneiras de executar \(T_1\) ou \(T_2\) é a soma do número de maneiras de executar \(T_1\) com o número de maneiras de executar \(T_2\) menos o número de maneiras de executar ambos \(T_1\) e \(T_2\text{,}\) pois esta quantidade já foi contada duas vezes.
Como existem \(\#(A\cup B)\) maneiras de realizar \(T_1\) ou \(T_2\) e \(\#(A\cap B)\) maneiras de realizar \(T_1\) e \(T_2\text{,}\) temos:
\begin{equation*} \#(A\cup B)=\#A+\#B-\#(A\cap B). \end{equation*}

Exemplo 2.1.3.

Numa pesquisa com jovens foram feitas as seguintes perguntas para que respondessem sim ou não. Gosta de exatas? Gosta de humanas? Responderam sim a primeira pergunta 80 jovens, 60 reponderam sim a segunda e 15 responderam sim a ambas. Quantos jovens responderam sim a pelo menos uma pergunta?
Solução.
Defina \(E\) como o conjunto dos alunos entrevistados que gostam de exatas e defina \(H\) como o conjunto dos alunos entrevistados que gostam de humanas, assim
\begin{equation*} \#E=80, \#H = 60 \text{ e }\#(E\cap H) = 15. \end{equation*}
Dessa forma, calculando \(\#E+\#H\) o número de alunos que gostam de ambas as áreas é contado duas vezes. Portanto, para determinar o número de alunos entrevistados, retira-se o número de alunos que foi contado duas vezes, ou seja
\begin{equation*} \#(E\cup H)= \#E+\#H-\#(E\cap H) = 80 + 60-15 = 125. \end{equation*}

Demonstração.

Considere \((A\cup B)\) como um conjunto, usando o (Teorema 2.1.1) temos:
\begin{align*} \#[A\cup B\cup C] = \amp~\#[(A\cup B)\cup C] \\ = \amp ~\#(A\cup B)+\#C-\#[(A\cup B)\cap C] \\ = \amp ~ \#A+\#B-\#(A\cap B)+\#C-\#[(A\cup B)\cap C]. \end{align*}
Usando a igualdade:
\begin{equation*} (A\cup B)\cap C = (A\cap C)\cup (B\cap C), \end{equation*}
temos
\begin{equation*} \#[A\cup B\cup C] = \#A+\#B-\#(A\cap B)+\#C-\#[(A\cap C)\cup (B\cap C)]. \end{equation*}
Aplicando o (Teorema 2.1.1) na união \([(A\cap C)\cup (B\cap C)]\text{,}\) concluímos a demonstração:
\begin{align*} \#(A\cup B\cup C) = \amp ~\#A+\#B-\#(A\cap B)+\#C \\ \amp ~ -\#(A\cap C)-\#(B\cap C) \\ \amp ~ +\#(A\cap B\cap C). \end{align*}

Subseção 2.1.2 O Princípio da Inclusão-Exclusão para \(n\) conjuntos

Demonstração.

Suponha que o elemento \(a\) pertence a exatamente \(r\) (\(1\leq r\leq n\)) dos conjuntos \(A_1, A_2, \ldots, A_n\text{.}\) Será mostrado que \(a\) é contado exatamente uma vez pelo lado direito da Expressão (2.1.2).
No somatório:
\begin{equation*} \sum_{i=1}^{n}\#A_i, \end{equation*}
observa-se que \(a\) é contado \(C_r^1=r\) vezes, pois \(a\) pertence a exatamente \(r\) dos conjuntos. No somatório
\begin{equation*} \sum_{0\lt i \lt j\leq n}\#(A_i\cap A_j), \end{equation*}
nota-se que \(a\) é contado \(C_r^2\) vezes, pois, em cada termo do somatório, para que \(a\) seja contado, \(a\) precisa pertencer aos dois conjuntos. Se separarmos os \(r\) conjuntos que contém \(a\text{,}\) existem \(C_r^2\) interseções contendo \(a\text{.}\) No caso geral, \(a\) será contado \(C_r^m\) vezes, pelo somatório envolvendo \(m\) dos conjuntos \(A_i, i\in \{1, 2, \ldots, n\}\text{.}\)
Desta forma, o elemento \(a\) será contado exatamente
\begin{equation*} C_r^1-C_r^2+C_r^3-\cdots+(-1)^{r+1}C_r^r \end{equation*}
vezes pelo lado direito de (2.1.2). Usando a Expansão do Binômio de Newton (veja Teorema 3.2.1), temos
\begin{equation*} 0 = (1-1)^p = C_r^0 -\left(C_r^1-C_r^2+C_r^3-\cdots+(-1)^{r+1}C_r^r\right). \end{equation*}
Portanto,
\begin{equation*} C_r^1-C_r^2+C_r^3-\cdots+(-1)^{r+1}C_r^r = C_r^0 = 1. \end{equation*}
Isto mostra que o elemento \(a\) é contado exatamente uma vez pelo lado direito de (2.1.2).
Como o elemento \(a\) é arbitrário e a quantidade \(r\text{,}\) também é arbitrária, esse argumento serve para cada um dos elementos de (2.1.1), o que prova o teorema.

Exemplo 2.1.7.

Quantos são os anagramas da palavra COMPLEXA que tem C em 1º lugar, ou O em 2º lugar, ou M em 3º lugar ou P em 4º lugar?
Solução.
Sejam
\begin{align*} A_1, ~\amp \text{o conjunto dos anagramas de COMPLEXA que tem C em 1º lugar}; \\ A_2, ~\amp \text{o conjunto dos anagramas de COMPLEXA que tem O em 2º lugar}; \\ A_3, ~\amp \text{o conjunto dos anagramas de COMPLEXA que tem M em 3º lugar}; \\ A_4, ~\amp \text{o conjunto dos anagramas de COMPLEXA que tem P em 4º lugar}. \end{align*}
Assim, \(\#A_i = 7!,\) para \(i\in \{1, 2, 3, 4\}\text{.}\)
Observe que \(\#(A_i\cap A_j), 1\leq i\lt j\leq 4\) é o número de anagramas da palavra COMPLEXA que estão em dois dos conjuntos \(A_i's, i\in\{1, 2, 3, 4\}\text{,}\) logo
\begin{equation*} \#(A_i\cap A_j) = 6! \end{equation*}
Observe que \(\#(A_i\cap A_j\cap A_k), 1\leq i\lt j\leq 4\) é o número de anagramas da palavra COMPLEXA que estão em três dos conjuntos \(A_i's, i\in\{1, 2, 3, 4\}\text{,}\) logo
\begin{equation*} \#(A_i\cap A_j\cap A_k) = 5! \end{equation*}
Observe que \(\#(A_1\cap A_2\cap A_3\cap A_4)\) é o número de anagramas da palavra COMPLEXA que tem as letras C, O, M e P nas posições \(1, 2, 3, 4\) fixas, logo
\begin{equation*} \#(A_1\cap A_2\cap A_3\cap A_4) = 4! \end{equation*}
Pelo Princípio da Inclusão-Exclusão (Teorema 2.1.6),
\begin{align*} \#(A_1\cup A_2\cup A_3\cup A_4) = \amp ~\sum_{i=1}^{4} \#A_i - \sum_{1\leq i\lt j\leq 4} \#(A_i\cap A_j) \\ \amp ~ +\sum_{1\leq i\lt j\lt k \leq 4} \#(A_i\cap A_j\cap A_k) \\ \amp ~ -\#(A_1\cap A_2\cap A_3\cap A_4). \end{align*}
Organizando, temos
\begin{align*} \#(A_1\cup A_2\cup A_3\cup A_4) = \amp ~ 4\times\#A_1 - C_4^2\times\#(A_1\cap A_2) \\ \amp ~ +C_4^3\times\#(A_1\cap A_2\cap A_3) \\ \amp ~ -\#(A_1\cap A_2\cap A_3\cap A_4). \end{align*}
Substituindo, temos
\begin{align*} \#(A_1\cup A_2\cup A_3\cup A_4) = \amp ~ 4\times 7! - C_4^2\times 6! +C_4^3\times 5! -4! \\ =\amp ~ 16296. \end{align*}

Tecnologia 2.1.8.

Escolha uma palavra e uma lista de posições para obter o número de anagramas da palavra, na qual pelo menos uma das letras das posições escolhidas estará na posição original.
Figura 2.1.9.

Exemplo 2.1.10.

Determine o número de elementos dos conjuntos:
  1. \(\displaystyle A = \{ a\in \mathbb{N}~|~ a \text{ é múltiplo de } 2, \text{ ou } 3, \text{ ou } 5 \text{ e } a \leq 10000\}; \)
  2. \(\displaystyle B = \{ b\in \mathbb{N}~|~ b \text{ é múltiplo de } 2, \text{ ou } 3, \text{ ou } 15 \text{ e } b\leq 10000\}. \)
Solução.
item a) Sejam
\begin{gather*} A_2=\{n\in\mathbb{N}~|~ 1\leq n\leq 10000 \text{ e } n \text{ é múltiplo de 2}\}; \\ A_3=\{n\in\mathbb{N}~|~ 1\leq n\leq 10000 \text{ e } n \text{ é múltiplo de 3}\}; \\ A_5=\{n\in\mathbb{N}~|~ 1\leq n\leq 10000 \text{ e } n \text{ é múltiplo de 5}\}. \end{gather*}
A resposta do item a) é a cardinalidade do conjunto:
\begin{equation*} A_2\cup A_3\cup A_5. \end{equation*}
Pelo Princípio da Inclusão-Exclusão (Teorema 2.1.6):
\begin{align*} \#(A_2\cup A_3\cup A_5) = \amp ~ \#A_2+\#A_3+\#A_5 \\ \amp ~ - \#(A_2\cap A_3) - \#(A_2\cap A_5) - \#(A_3\cap A_5) \\ \amp ~ +\#(A_2\cap A_3\cap A_5). \end{align*}
Para obter a cardinalidade de cada um dos conjuntos \(A_i's\text{,}\) vamos dividir 10000 por \(i\text{,}\) pois se obtermos \(10000 = p\times i + r\text{,}\) na divisão Euclideana, significa que \(1\times i, 2\times i, \ldots, p\times i \) são todos múltiplos de \(i\) e são menores que 10000. Fazendo as divisões obtemos:
\begin{align*} 10000 \amp = ~ 5000\times 2 + 0 \Rightarrow \#A_2 = 5000 \\ 10000 \amp = ~ 3333\times 3 + 1 \Rightarrow \#A_3 = 3333 \\ 10000 \amp = ~ 2000\times 5 + 0 \Rightarrow \#A_5 = 2000. \end{align*}
Para obter a cardinalidade de cada uma das interseções \(A_i\cap A_j\text{,}\) vamos dividir 10000 por \(i\times j\text{:}\)
\begin{align*} 10000 \amp = ~ 1666\times 6 + 4 \Rightarrow \#(A_2\cap A_3) = 1666 \\ 10000 \amp = ~ 1000\times 10 + 0 \Rightarrow \#(A_2\cap A_5) = 1000 \\ 10000 \amp = ~ 666\times 15 + 10 \Rightarrow \#(A_3\cap A_5) = 666. \end{align*}
Para obter a cardinalidade de \(A_2\cap A_3\cap A_5\text{,}\) vamos dividir 10000 por \(2\times 3\times 5\text{:}\)
\begin{align*} 10000 \amp = ~ 333\times 30 + 10 \Rightarrow \#(A_2\cap A_3\cap A_5) = 333. \end{align*}
Portanto, pelo Princípio Inclusão-Exclusão temos:
\begin{align*} \#(A_2\cup A_3\cup A_5) \amp = 5000+3333+2000-1666-1000-666+333 \\ \amp = ~ 7334. \end{align*}
item b) Usando a ideia do item a), queremos calcular a cardinalidade do conjunto:
\begin{equation*} A_2\cup A_3\cup A_{15}. \end{equation*}
Vamos começar calculando a cardinalidade de cada conjunto:
\begin{align*} 10000 \amp = ~ 5000\times 2 + 0 \Rightarrow \#A_2 = 5000 \\ 10000 \amp = ~ 3333\times 3 + 1 \Rightarrow \#A_3 = 3333 \\ 10000 \amp = ~ 666\times 15 + 10 \Rightarrow \#A_{15} = 666. \end{align*}
Calculando a cardinalidade de cada uma das interseções \(A_i\cap A_j\text{:}\)
\begin{align*} 10000 \amp = ~ 1666\times 6 + 4 \Rightarrow \#(A_2\cap A_3) = 1666 \\ 10000 \amp = ~ 333\times 30 + 10 \Rightarrow \#(A_2\cap A_{15}) = 333 \\ 10000 \amp = ~ 666\times 15 + 10 \Rightarrow \#(A_3\cap A_{15}) = 666. \end{align*}
Para obter a cardinalidade de \(A_2\cap A_3\cap A_{15}\text{,}\) dividimos \(10000\) pelo \(mmc(2, 3, 15)\text{,}\) logo:
\begin{align*} 10000 \amp = ~ 333\times 30 + 10 \Rightarrow \#(A_2\cap A_3\cap A_{15}) = 333. \end{align*}
Portanto, pelo Princípio da Inclusão-Exclusão:
\begin{align*} \#(A_2\cap A_3\cap A_{15}) =\amp~ 5000+3333+666-1666-333-666+333\\ =\amp~6667. \end{align*}

Tecnologia 2.1.11.

Escolha os valores dos campos, Vmin ,Vmax e lista, para determinar a cardinalidade do conjunto abaixo:
\begin{equation*} C = \{n\in \mathbb{N}~|~ n \text{ é múltiplo de } n_1, \text{ ou } n_2, \text{ ou } \ldots n_k \text{ e } Vmin \leq n\leq Vmax \}. \end{equation*}
Figura 2.1.12.

Subseção 2.1.3 Outros Casos do Princípio da Inclusão-Exclusão

Definição 2.1.13.

Sejam \(\Omega\) um conjunto, \(A_1, A_2, \ldots, A_n\) subconjuntos de \(\Omega\text{.}\) Definimos os números \(S_0, S_1, S_2, \ldots, S_n\) da seguinte maneira:
\begin{align*} S_0=\amp~\#\Omega;\\ S_1=\amp~\sum_{i=1}^n\#A_i;\\ S_2=\amp~\sum_{1\leq i\lt j\leq n}^n\#(A_i\cap A_j);\\ \vdots\\ S_n=\amp~\#(A_1\cap A_2\cap \ldots\cap A_n). \end{align*}

Exemplo 2.1.15.

Determine quantos inteiros estão compreendidos entre \(1\) e \(10000\) inclusive, e são múltiplos de
  1. exatamente dois dos números: \(2, 3\) e \(15\text{;}\)
  2. pelo menos dois dos números: \(2, 3\) e \(15\text{.}\)
Solução.
Pelo item b. do Exemplo 2.1.10, sabemos que
\begin{align*} S_0=\amp~10000;\\ S_1=\amp~5000+3333+666=8999;\\ S_2=\amp~1666+333+666=2665;\\ S_3=\amp~333. \end{align*}
item a)
\begin{align*} a_2 =\amp~ (-1)^0C_2^0S_2 + (-1)^1C_3^1S_3\\ =\amp~ 2665-3\times 333\\ =\amp~1666. \end{align*}
item b)
\begin{align*} b_2 =\amp~ (-1)^0C_1^0S_2 + (-1)^1C_2^1S_3\\ =\amp~ 2665-2\times 333\\ =\amp~1999. \end{align*}

Tecnologia 2.1.16.

Escolha os valores dos campos, Vmin ,Vmax, lista e p, para determinar os valores de \(S_i\text{,}\) \(a_p\text{,}\) \(b_p\) e a cardinalidade do conjunto \(C\text{,}\) definido abaixo:
\begin{equation*} C = \{n\in \mathbb{N}~|~ n \text{ é múltiplo de } n_1, \text{ ou } n_2, \text{ ou } \ldots n_k \text{ e } Vmin \leq n\leq Vmax \}. \end{equation*}
Figura 2.1.17.

Exercícios 2.1.4 Exercícios

1.

Quantos são os anagramas da palavra PETELECOS que possuem a letra P na 1ª posição, ou a letra E na 2ª posição, ou a letra T na 3ª posição?
Resposta.
\(28080\)
Solução.
Sejam
\begin{align*} A_1, ~\amp \text{o conjunto dos anagramas de PETELECOS que tem P em 1º lugar}; \\ A_2, ~\amp \text{o conjunto dos anagramas de PETELECOS que tem E em 2º lugar}; \\ A_3, ~\amp \text{o conjunto dos anagramas de PETELECOS que tem T em 3º lugar}. \end{align*}
Queremos calcular \(\#(A_1\cup A_2\cup A_3)\text{.}\) Note que \(\#A_1=\#A_3=PR_8^3\text{,}\) pois são as quantidades de anagramas da palavra PETELECOS com a letra P na primeira posição, para \(\#A_1\text{,}\) e com a letra T na terceira posição, para \(\#A_3\text{.}\) Note também que \(\#A_2 = PR_8^2\text{.}\)
Agora, vamos calcular as cardinalidades das interseções \(A_i\cap A_j\text{,}\) com \(1\leq i\lt j\leq 3\text{.}\)
  • \(A_1\cap A_2= PR_7^2\text{,}\) pois P e E ficam fixados;
  • \(A_1\cap A_3= PR_7^3\text{,}\) pois P e T ficam fixados;
  • \(A_2\cap A_3= PR_7^2\text{,}\) pois E e T ficam fixados.
Finalmente, \(\#(A_1\cap A_2\cap A_3) = PR_6^2\text{.}\) Aplicando o Princípio da Inclusão-Exclusão:
\begin{align*} \#(A_1\cup A_2\cup A_3) =\amp~ PR_8^3\times 2 + PR_8^2 - PR_7^2\times 2 - PR_7^3 + PR_6^2\\ =\amp~28080. \end{align*}

2.

(OBM 2011 - 1ª fase do nível 3) Três polı́gonos regulares, de 8, 12 e 18 lados respectivamente, estão inscritos em uma mesma circunferência e têm um vértice em comum. Os vértices dos três polı́gonos são marcados na circunferência. Quantos vértices distintos foram marcados?
Dica.
Sendo \(A_k\) a quantidade de pontos do polı́gono de \(k\) vértices, queremos calcular \(\#(A_8 \cup A_{12} \cup A_{18})\text{.}\) Note que \(\#(A_{i_1} \cap A_{i_2} \cap\ldots \cap A_{i_n}) = mdc(i_1 , i_2 , \ldots , i_n)\text{.}\)
Resposta.
28
Solução.
Sejam \(A_k\text{,}\) \(k = 8, 12, 18\text{,}\) os conjuntos dos vértices dos polígonos com 8, 12 e 18 lados, respectivamente. Queremos calcular \(\#(A_8\cup A_{12}\cup A_{18})\text{.}\) Pelo Princípio da Inclusão-Exclusão, temos
\begin{align*} \#(A_8\cup A_{12}\cup A_{18}) =\amp~ \#A_8+\#A_{12}+\#A_{18} \\ ~~~~\amp~ - \#(A_8\cap A_{12}) - \#(A_{8}\cap A_{18}) - \#(A_{12}\cap A_{18})\\ ~~~~\amp~+ \#(A_8\cap A_{12}\cap A_{18}). \end{align*}
Como \(\#A_k = k\text{,}\) para concluir o cálculo, precisamos descobrir a cardinalidade de cada interseção.
Usando a figura abaixo como referência, se expandirmos os polígonos até a circunferência, estaremos de acordo com o enunciado. O vértice em comum aos três polígonos foi desenhado no ponto extremo superior, sem perda de generalidade, pois independente de onde ele esteja, os polígonos podem ser girados para ficarem desta forma.
Figura 2.1.18. Polígonos encolhidos.
Considere os semicírculos que partem do extremo superior no sentido horário, até o vértice seguinte de \(A_k\) e assim sucessivamente, de um vértice de \(A_k\) até o seguinte. Desta forma cada conjunto \(A_k\) define \(k\) semicírculos. Teremos a interseção de dois ou três vértices quando a respectiva quantidade de extremidades dos semicírculos coincidirem. Portanto, usaremos o máximo divisor comum para calcular a quantidade de interseções dos vértices. Assim, \(\#(A_i\cap A_j) = \text{mdc}(i, j)\text{,}\) para \(i, j \in \{8, 12, 18\}\text{,}\) com \(i\neq j\) e \(\#(A_8\cap A_{12} \cap A_{18}) = \text{mdc}(8, 12, 18)\text{.}\) Logo,
\begin{equation*} \#(A_8\cup A_{12}\cup A_{18}) = 8+12+18 - 4 - 2 - 6 + 2 = 28. \end{equation*}
Na figura abaixo, podemos imaginar que os polígonos foram "cortados" e esticados para podermos visualizar as interseções dos vértices de acordo com os valores dos mdcs.
Figura 2.1.19. Verificação das interseções.

3.

Determine o número de permutações de \((1, 2, 3, 4, 5, 6, 7, 8)\) nas quais nem o 2 ocupa o 2ª lugar nem o 3 ocupa o 3º lugar nem o 4 ocupa o 4º lugar?
Resposta.
27240

4.

Quantos são os inteiros de \(n\) dígitos, que têm todos os dígitos pertencentes ao conjunto \(\{1, 2, 3\}\text{?}\) Em quantos deles os inteiros \(1, 2\) e \(3\) figuram todos?
Resposta.
a) \(3^n\) , b) \(3^n-3\cdot 2^n+3\text{.}\)
Solução.
item a) Temos 3 opções para o primeiro dígito, 3 opções para o segundo dígito e assim sucessivamente, até o \(n\)-ésimo dígito que também temos 3 opções. Portanto a resposta é \(\underbrace{3\times \cdots \times 3}_{n\text{ parcelas}} = 3^n\text{.}\)
item b) Agora precisamos subtrair de \(3^n\) a quantidade de números de \(n\) dígitos, na qual, nem todos os três dígitos disponíveis aparecem. Defina \(A_1\) como o subconjunto dos números de \(n\) dígitos formados pelos dígitos \(1, 2\) e \(3\) tal que o dígito \(1\) não aparece. De maneira análoga defina os subconjuntos \(A_2\) e \(A_3\text{.}\) Desta forma, queremos calcular
\begin{equation*} 3^n - \#(A_1\cup A_2 \cup A_3)\text{.} \end{equation*}
Pelo Princípio da Inclusão-Exclusão, sabemos que
\begin{align*} \#(A_1\cup A_2\cup A_3) = \amp ~\#A_1+\#A_2+\#A_3 \\ \amp ~ -\#(A_1\cap A_2)-\#(A_1\cap A_3)-\#(A_2\cap A_3) \\ \amp ~ +\#(A_1\cap A_2\cap A_3). \end{align*}
\(A_1\) possui \(2^n\) elementos, pois o dígito \(1\) não pode figurar no número de \(n\) dígitos, sobrando apenas os dígitos \(2\) e \(3\text{.}\) Desta forma, temos duas opções para o primeiro dígito, 2 opções para o segundo dígito e assim sucessivamente. Observe que os conjuntos \(A_2\) e \(A_3\) possuem a mesma quantidade de elementos.
\(A_1\cap A_2\) possui apenas \(1\) elemento, pois os dígitos \(1\) e \(2\) não podem figurar, sobrando apenas o dígito 3. Desta forma temos apenas uma opções para o primeiro dígito, uma opção para o segundo dígito e assim sucessivamente. De maneira análoga observamos que \(A_1\cap A_2\) e \(A_2\cap A_3\) também possuem apenas um elemento.
Finalmente, \(A_1\cap A_2\cap A_3\) não possui elementos, pois nenhum dos três dígitos podem figurar. Portanto a resposta é
\begin{equation*} 3^n - 2^n - 2^n - 2^n + 1 + 1+ 1 -0 = 3^n - 3\times 2^n + 3. \end{equation*}

5.

Se \(\#A = n\) e \(\#B=m\) (\(n\geq m\)), quantas são as funções \(f:A\rightarrow B\) sobrejetoras?
Resposta.
\(\displaystyle\sum_{k=0}^m (-1)^kC_m^k(m-k)^n\)
Solução.
Note que, no total, exitem \(m^n\) funções \(f:A\rightarrow B\text{,}\) pois existem \(m\) maneiras de escolher a imagem de cada um dos \(n\) elementos de \(A\text{.}\)
Sejam \(y_1, y_2, \ldots, y_m\) os elementos do conjunto \(B\text{.}\) Defina \(F_j\) o conjunto das funções \(f_{j,l}:A\rightarrow B\text{,}\) tais que \(y_j\) não pertence a imagem de \(f_{j,l}\text{.}\) Logo, \(j\in \{1, 2, \ldots, m\}\) e \(l=(m-1)^n\text{.}\)
As funções que não são sobrejetivas são as que pertencem a
\begin{equation*} F_1\cup F_2\cup\cdots\cup F_m\text{.} \end{equation*}
Então, o número de funções sobrejetoras é dado por
\begin{equation*} m^n-\#(F_1\cup F_2\cup\cdots\cup F_m)\text{.} \end{equation*}
Para usar o Princípio da Inclusão-Exclusão, precisamos calcular a cardinalidade dos conjuntos \(F_j\text{,}\) a cardinalidade das interseções \(p\) a \(p\) desses conjuntos, com \(2\leq p \leq m\) e a quantidade de interseções \(p\) a \(p\) desses conjuntos:
  • Para o caso de apenas um conjunto, já sabemos que \(\#F_j=(m-1)^n\) e no total existem \(m\) conjuntos;
  • Para o caso das interseções de dois conjuntos, temos \(\#(F_{j_1}\cap F_{j_2})=(m-2)^n\) e no total existem \(C_m^2\) dessas interseções;
  • Para o caso das interseções de \(p\) conjuntos, temos \(\#(F_{j_1}\cap\cdots\cap F_{j_p})=(m-p)^n\) e no total existem \(C_m^p\) dessas interseções.
Aplicando o Princípio da Inclusão-Exclusão, a resposta é
\begin{align*} m^n-\amp\#(F_1\cup F_2\cup\cdots\cup F_m)=\\ =\amp~m^n - C_m^1(m-1)^n+C_m^2(m-2)^n-\cdots+(-1)^mC_m^m(m-m)^n\\ =\amp~\sum_{k=0}^m (-1)^kC_m^k(m-k)^n. \end{align*}

6.

(IME) Cinco equipes concorrem numa competição automobilı́stica, em que cada equipe possui dois carros. Para a largada são formadas duas colunas de carros lado a lado, de tal forma que cada carro da coluna da direita tenha ao seu lado, na coluna da esquerda, um carro de outra equipe. Determine o número de formações possı́veis para a largada.
Resposta.
2088960
Solução.
Inicialmente, temos 10! possibilidades de colocarmos esses 10 veículos na posição de largada. Dessas permutações, vamos excluir aquelas que possuem uma equipe com dois carros lado a lado. Para isso, existem \(C_5^1\) maneiras de escolhermos essa equipe que poderá ser colocada em uma das 5 filas na largada \((1^{a}, 2^{a}, 3^{a}, 4^{a} \ ou \ 5^{a})\text{.}\) Devemos, ainda, permutar os carros de uma mesma equipe 2! e os demais 8 carros podem ser organizados de 8!. Assim, temos \(C_5^1\times 5\times 2!\times 8!\) formas distintas de organizarmos esses carros.
Algumas dessas maneiras de organizar os carros apresentam mais de uma equipe com seus carros emparelhados.
Agora, calcularemos em quantos casos teremos ao menos 2 equipes com seus carros emparelhados. Primeiramente, temos \(C_5^2\) formas de escolhermos essas 2 equipes e podemos colocá-las de \(5\times4\) maneiras diferentes nas 5 filas da largada (a primeira equipe pode entrar em qualquer uma das 5 filas e a segunda em uma das outras 4 que restaram). Mas, ainda, devemos permutar os carros das duas equipes lado a lado \(2!\times2\) e das demais \(6\) equipes \(6!\text{.}\)
Seguindo essa linha de raciocínio, pelo Princípio da Inclusão-Exclusão temos
\begin{align*} 10! - \#(A_1\cup A_2\cup A_3\cup A_4\cup A_5) \amp = ~ 10! - C_5^1\times 5\times 2\times 8! \\ \amp ~~~~~~ + C_5^2\times 5\times 4\times 2^2\times 6!\\ \amp ~~~~~~ -C_5^3\times 5\times 4\times 3\times2^3\times 4! \\ \amp ~~~~~~ +C_5^4\times 5\times 4\times 3\times 2\times 2^4\times 2! \\ \amp ~~~~~~ - 5!\times 2^5\\ \amp ~ = 2088960. \end{align*}

7.

(ITA 2010) Sejam \(A, B\) e \(C\) conjuntos tais que
  • \(C\subset B\text{,}\)
  • \(\#(B\setminus C) = 3\times\#(B\cap C) = 6\times\#(A\cap B)\text{,}\)
  • \(\displaystyle \#(A\cup B) = 22\)
e \((\#C, \#A, \#B)\) é uma progressão geométrica de razão \(r>0\text{.}\)
  1. Determine \(\#C\)
  2. Determine \(\#(\mathcal{P}(B\setminus C)).\)
Resposta.
a) \(\#C = 4~~~~\) b) \(\#(\mathcal{P}(B\setminus C)) = 4096\text{.}\)
Solução.
item a) Como \(C\subset B\text{,}\) temos \(B\cap C = C\text{,}\) logo \(\#(B\cap C) = \#C\) e \(\#(B\setminus C) = \#B - \#C\text{.}\) Logo
\begin{equation*} \#B - \#C = \overbrace{\#(B\setminus C) = 3\times \#(B\cap C)}^{\text{por hipótese}} = 3\times\#C. \end{equation*}
Ou seja,
\begin{equation} \#B = 4\times\#C.\tag{2.1.3} \end{equation}
Usando que \((\#C, \#A, \#B)\) é uma P.G., podemos escrever \(\#C=a_0r^0, \#A=a_0r^1\) e \(\#B=a_0r^2\text{.}\) Logo,
\begin{align*} (a_0r^1)^2 =\amp~ (a_0r^0)(a_0r^2)\\ ( \#A )^2 =\amp~ \#C\times \#B\\ ( \#A )^2 =\amp~\#C\times 4\times\#C. \end{align*}
Portanto,
\begin{equation} \#A=2\times \#C\text{.}\tag{2.1.4} \end{equation}
Por hipótese, \(3\times\#(B\cap C) = 6\times\#(A\cap B)\text{,}\) mas \(\#(B\cap C) = \#C\text{,}\) assim
\begin{equation} \#C = 2\#(A\cap B) \quad \Rightarrow \quad \#(A\cap B) = \frac{\#C}{2}.\tag{2.1.5} \end{equation}
Finalmente, usando as igualdades (2.1.3), (2.1.4), (2.1.5) e o Princípio da Inclusão-Exclusão (Teorema 2.1.1), obtemos
\begin{equation*} \underbrace{\#(A\cup B)}_{22} = \underbrace{\#A}_{2\times \#C} + \underbrace{\#B}_{4\times \#C} -\underbrace{\#(A\cap B)}_{\#C/2}. \end{equation*}
Efetuando o cálculo, \(\#C = 4\text{.}\)
item b) Como \(\#(B\setminus C) = 3\times \#C = 12\text{,}\) temos
\begin{equation*} \#\mathcal{P}(B\setminus C) = 2^{\#(B\setminus C)} = 2^{12} = 4096. \end{equation*}
AnteriorTopPróximo