O Princípio da Inclusão-Exclusão é uma ferramenta fundamental da Combinatória, utilizada para realizar a contagem precisa de elementos pertencentes a vários conjuntos. Apresentamos esse princípio combinando teoria e exemplos, com atenção especial à integração de recursos tecnológicos desenvolvidos com o auxílio do SageMath.
Nota2.1.1.
Usaremos o símbolo \(\#A\) para representar o número de elementos do conjunto \(A\text{,}\) isto é, a cardinalidade de \(A\text{.}\)
Dizemos que dois conjuntos \(A\) e \(B\) são disjuntos quando \(A\cap B=\varnothing\text{.}\)
Subseção2.1.1O Princípio da Inclusão-Exclusão para 2 e 3 conjuntos
Teorema2.1.2.
Sejam \(A\) e \(B\) conjuntos finitos, então
\begin{equation*}
\#(A\cup B) = \#A + \# B - \#(A\cap B).
\end{equation*}
Figura2.1.3.Diagrama de Venn para \((A\cup B)\text{.}\)
Ou seja, a cardinalidade de \(A\cup B\) é igual a cardinalidade de \(A\) mais a cardinalidade de \(B\) menos a cardinalidade de \(A\cap B\text{.}\)
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:
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?
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
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
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).
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
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.
Exemplo2.1.8.
Determine o número de elementos dos conjuntos:
\(\displaystyle A = \{ a\in \mathbb{N}~|~ a \text{ é múltiplo de } 2, \text{ ou } 3, \text{ ou } 5 \text{ e } a \leq 10000\}; \)
\(\displaystyle B = \{ b\in \mathbb{N}~|~ b \text{ é múltiplo de } 2, \text{ ou } 3, \text{ ou } 15 \text{ e } b\leq 10000\}. \)
\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:
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:
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*}
Figura2.1.10.
Exemplo2.1.11.
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?
\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
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
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
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.
Figura2.1.13.
Exemplo2.1.14.(POTI Nível 3).
No primeiro dia de uma competição matemática, vinte pessoas tiraram uma foto em grupo, em fila. No último dia, tiraram outra foto, de modo que todos tinham um novo vizinho à sua direita. De quantas maneiras eles poderiam fazer isso?
Considere o conjunto \(\Omega\) das permutações \((j_1, j_2, \ldots, j_{20})\) do conjunto \(\{1,2,\ldots, 20\}\) e seja \(A_r\) o conjunto destas permutações, na qual, o par \((j_r, j_{r+1})\) é uma sucessão, \(r=1,2,\ldots, 19\text{.}\) O número de fotos possíveis é dado por
Vamos precisar do PIE para calcular \(\#(A_1\cup A_2 \cup \cdots \cup A_{19})\text{.}\)
Observe que \(\#A_r = (20-1)!\text{,}\) para qualquer \(r = 1, 2, \ldots, 19\text{.}\) Pois, olhamos para o par \((j_r, j_{r+1})\) como um elemento e ficamos com um conjunto de \(19\) elementos para contar o número de permutações.
O caso de \(\#(A_r\cap A_s)\text{,}\) vamos separar em duas situações.
(\(r\) e \(l\) não são consecutivos) Neste caso, Olhamos para o par \((j_r, j_{r+1})\) como apenas um elemento e o par \((j_s, j_{s+1})\) como um elemento também, ficamos com \(20-2\) elementos para contar o número de permutações.
(\(r\) e \(s\) são consecutivos) Neste caso olhamos para a tripla \((j_r, j_{r+1}, j_{r+2})\) como apenas um elemento e também ficamos com \(20-2\) elementos para contar o número de permutações.
Nos dois casos o número de permutações é \((20-2)!=18!\text{.}\) E o número de interseções 2 a 2 é \(\binom{19}{2}\)
O caso de \(\#(A_r\cap A_s \cap A_p)\text{,}\) vamos separar em três situações.
(\(r\text{,}\)\(s\) e \(p\) não são consecutivos) Neste caso, Olhamos para os pares \((j_i, j_{i+1})\) como apenas um elemento, ficamos com \(20-3\) elementos para contar o número de permutações.
(\(r\text{,}\)\(s\) e \(p\) apenas dois são consecutivos) Neste caso olhamos para a tripla \((j_r, j_{r+1}, j_{r+2})\) como apenas um elemento e um par \((j_i, j_{i+1})\) como um elemento. Também ficamos com \(20-3\) elementos para contar o número de permutações.
(\(r\text{,}\)\(s\) e \(p\) os três são consecutivos) Neste caso olhamos para a tripla \((j_r, j_{r+1}, j_{r+2},j_{r+3})\) como apenas um elemento. Também ficamos com \(20-3\) elementos para contar o número de permutações.
Nos três casos o número de permutações é \((20-3)!=17!\text{.}\) E o número de interseções 3 a 3 é \(\binom{19}{3}\)
Subseção2.1.3Generalização do Princípio da Inclusão-Exclusão
Definição2.1.15.
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:
A estratégia de demonstração para ambas as fórmulas baseia-se em acompanhar um elemento arbitrário \(\omega \in \Omega\) que pertença a exatamente \(m\) dos \(n\) subconjuntos. Devemos calcular quantas vezes esse elemento \(\omega\) é contado pela expressão do lado direito da igualdade.
Lembre-se que \(S_j\) é a soma das cardinalidades de todas as interseções possíveis de \(j\) conjuntos. Como o elemento \(\omega\) pertence a exatamente \(m\) subconjuntos, ele estará presente em exatamente \(C_m^j\) interseções de tamanho \(j\) (convencionando que \(C_m^j = 0\) caso \(j > m\)). Portanto, a contribuição de \(\omega\) para a parcela \(S_j\) é igual a \(C_m^j\text{.}\)
Demonstração do item a)
Substituindo \(S_{p+k}\) por \(C_m^{p+k}\text{,}\) a contribuição total \(T_a\) do elemento \(\omega\) para a fórmula de \(a_p\) é:
Vamos analisar os três casos possíveis para \(m\text{:}\)
\textbf{Se \(m \lt p\text{:}\)} Para todo \(k \ge 0\text{,}\) teremos \(p+k > m\text{,}\) o que implica que \(C_m^{p+k} = 0\text{.}\) Logo, \(T_a = 0\text{.}\)
\textbf{Se \(m = p\text{:}\)} O único termo não nulo ocorre quando \(k = 0\) (pois para \(k \ge 1\text{,}\) temos \(p+k > p\)). Assim, \(T_a = (-1)^0 C_p^0 C_p^p = 1 \times 1 \times 1 = 1\text{.}\)
\textbf{Se \(m > p\text{:}\)} Usaremos uma identidade envolvendo o produto de binomiais:
Pelo Teorema do Binômio de Newton, o somatório equivale a \((1 - 1)^{m-p}\text{.}\) Como \(m > p\text{,}\) essa potência resulta em \(0\text{.}\) Logo, \(T_a = C_m^p \times 0 = 0\text{.}\)
Como a contribuição de \(\omega\) é \(1\) apenas se \(m = p\text{,}\) e \(0\) nos demais casos, a fórmula contabiliza exatamente os elementos que pertencem a \(p\) conjuntos.
Demonstração do item b)
Para o cálculo de \(b_p\text{,}\) a contribuição \(T_b\) do elemento \(\omega\) é dada por:
\textbf{Se \(m \lt p\text{:}\)} Novamente, \(C_m^{p+k} = 0\) para todo \(k \ge 0\text{.}\) Assim, \(T_b = 0\text{.}\)
\textbf{Se \(m \ge p\text{:}\)} Utilizaremos a identidade de extensão dos binomiais para coeficientes negativos: \(C_{p+k-1}^k = (-1)^k C_{-p}^k\text{.}\) Substituindo na soma, o fator \((-1)^k \times (-1)^k = 1\text{.}\) Logo:
Aplicando a identidade da Convolução de Vandermonde (\(\sum C_A^k C_B^{N-k} = C_{A+B}^N\)), onde \(A = -p\text{,}\)\(B = m\) e \(N = m-p\text{,}\) obtemos:
Portanto, a fórmula soma exatamente \(1\) vez todo elemento que pertença a \(p\) conjuntos ou mais, finalizando a demonstração.
Exemplo2.1.17.
Considere um grupo onde as pessoas podem falar três idiomas: Inglês (\(I\)), Espanhol (\(E\)) e Francês (\(F\)). Para compreender intuitivamente como atuam os coeficientes das fórmulas do Princípio da Inclusão-Exclusão Generalizado, considere três pessoas representativas:
Ana: fala apenas Inglês (pertence a exatamente \(1\) conjunto).
Beto: fala Inglês e Espanhol (pertence a exatamente \(2\) conjuntos).
Carlos: fala Inglês, Espanhol e Francês (pertence a exatamente \(3\) conjuntos).
Mostre como as fórmulas a seguir atribuem a contagem correta para cada um desses indivíduos:
A fórmula \(a_1\) para contar quem fala exatamente um idioma.
A fórmula \(b_1\) para contar quem fala pelo menos um idioma.
Antes de aplicar as fórmulas, analisamos quantas vezes cada indivíduo é computado nas somas parciais \(S_k\text{:}\)
\(S_1 = \#I + \#E + \#F\text{:}\) Ana aparece \(1\) vez; Beto aparece \(2\) vezes; Carlos aparece \(3\) vezes.
\(S_2 = \#(I \cap E) + \#(I \cap F) + \#(E \cap F)\text{:}\) Ana aparece \(0\) vezes; Beto aparece \(1\) vez; Carlos aparece nas \(3\) interseções (\(3\) vezes).
\(S_3 = \#(I \cap E \cap F)\text{:}\) Ana aparece \(0\) vezes; Beto aparece \(0\) vezes; Carlos aparece \(1\) vez.
Parte (a): Exatamente 1 idioma (\(a_1\))
Aplicando a fórmula para \(p = 1\) e \(n = 3\text{:}\)
Dessa forma, o ajuste nos coeficientes faz com que qualquer elemento presente em \(1, 2\) ou \(3\) conjuntos contribua exatamente com o valor final \(1\text{,}\) recuperando o formato clássico da união de conjuntos.
Exemplo2.1.18.
Determine quantos inteiros estão compreendidos entre \(1\) e \(10000\) inclusive, e são múltiplos de
exatamente dois dos números: \(2, 3\) e \(15\text{;}\)
pelo menos dois dos números: \(2, 3\) e \(15\text{.}\)
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*}
Figura2.1.20.
Exemplo2.1.21.
Sejam \(\mathcal{C}, \mathcal{O}, \mathcal{M}\) e \(\mathcal{P}\) os conjuntos dos anagramas da palavra COMPLEXA que possuem a letra C em primeiro lugar, a letra O em segundo lugar, a letra M em terceiro lugar e a letra P em quarto lugar, respectivamente.
Quantos são os anagramas de COMPLEXA que estão em exatamente dois dos conjuntos \(\mathcal{C}, \mathcal{O}, \mathcal{M}\) e \(\mathcal{P}\text{?}\)
Quantos são os anagramas de COMPLEXA que estão em pelo menos dois dos conjuntos \(\mathcal{C}, \mathcal{O}, \mathcal{M}\) e \(\mathcal{P}\text{?}\)
De acordo com a Proposição 2.1.16, a resposta do item a) é o valor de \(a_2\) e o do item b) é o valor de \(b_2\text{.}\) Note que o número total de anagramas da palavra COMPLEXA é \(8!=40320\text{,}\) que o valor de \(S_0\text{.}\) Usando as informações da solução do Exemplo 2.1.11, podemos completar os valores de \(S_1, S_2, S_3\) e \(S_4\text{:}\)
\(\displaystyle S_0 = 40320\)
\(\displaystyle S_1 = 20160\)
\(\displaystyle S_2 = 4320\)
\(\displaystyle S_3 = 480\)
\(\displaystyle S_4 = 24\)
Aplicando a Proposição 2.1.16, obtemos as respostas dos itens a) e b)
Escolha os valores dos campos, Palavra, Posições fixas e p, para determinar os valores de \(S_i\text{,}\)\(a_p\) e \(b_p\text{.}\) De acordo com o enunciado do exemplo anterior.
Figura2.1.23.
Exercícios2.1.4Exercícios
1.
(Veja [6.22]) Qual o número de permutações de \((1,2,3,4)\text{,}\) na qual, o número \(1\) não pode ocupar o segundo lugar, o número \(2\) não pode ocupar o quarto lugar e o número \(3\) não pode ocupar nem o primeiro nem o quarto lugar?
\begin{equation*}
\displaystyle B = \{ b\in \mathbb{N}~|~ b \text{ é múltiplo de } 2, \text{ ou } 3, \text{ ou } 15 \text{ e } 100\leq b\leq 1000\}
\end{equation*}
e
\begin{equation*}
\displaystyle B' = \{ b\in \mathbb{N}~|~ b \text{ é múltiplo de } 2, \text{ ou } 3, \text{ ou } 15 \text{ e } 1\leq b\leq 901\}.
\end{equation*}
Os conjuntos \(B\) e \(B'\) possuem a mesma cardinalidade?
A diagonal corta cada um dos \(20+32\) quadrados? A resposta é não. De fato, pode ocorrer de haver repetições na "mudança". Veja o seguinte exemplo bidimensional, num retângulo \(6 \times 9\text{.}\)
Note que há três repetições. Opa! \(mdc(6, 9) = 3\) e \((6, 9) = 3 \cdot (2, 3)\text{.}\) O que acontece é que se \(mdc(a, b) = d\text{,}\) ocorrem \(d\) blocos de repetições. Logo, devemos subtrair \(mdc(a, b)\text{.}\) A resposta é \(a + b - mdc(a, b)\text{.}\)
No nosso caso, a resposta é \(20+32-mdc(20,32)=20+32-4 = 48.\)
Tecnologia2.1.24.
Escolha os valores dos campos, m (número de linhas) e n (número de colunas) para determinar quantos quadrados unitários a diagonal do retângulo passa.
Figura2.1.25.
4.
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?
\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:
Sejam \(\mathcal{P}, \mathcal{R}\) e \(\mathcal{I}\) os conjuntos dos anagramas da palavra PRINCIPIO que possuem a letra P em primeiro lugar, a letra R em segundo lugar e a letra I em terceiro lugar, respectivamente.
Quantos são os anagramas de PRINCIPIO que estão em exatamente um dos conjuntos \(\mathcal{P}, \mathcal{R}\) e \(\mathcal{I}\text{?}\)
Quantos são os anagramas de PRINCIPIO que estão em pelo menos um dos conjuntos \(\mathcal{P}, \mathcal{R}\) e \(\mathcal{I}\text{?}\)
De acordo com a Proposição 2.1.16, a resposta do item a) é o valor de \(a_1\) e o do item b) é o valor de \(b_1\text{.}\) Note que o número total de anagramas da palavra PRINCIPIO é \(PR_{9}^{3,2}=30240\text{,}\) que o valor de \(S_0\text{.}\) Para calcular os valores de \(S_1, S_2, S_3\) e \(S_4\text{,}\) precisamos dos seguintes valores:
\(\displaystyle \#A_1 = 6720\)
\(\displaystyle \#A_2 = 3360\)
\(\displaystyle \#A_3 = 10080\)
\(\displaystyle \#A_1\cap A_2 = 840\)
\(\displaystyle \#A_1\cap A_3 = 2520\)
\(\displaystyle \#A_2\cap A_3 = 1260\)
\(\displaystyle \#A_1\cap A_2\cap A_3 = 360\)
Portanto,
\(\displaystyle S_0 = 30240\)
\(\displaystyle S_1 = 20160\)
\(\displaystyle S_2 = 4620\)
\(\displaystyle S_3 = 360\)
Aplicando a Proposição 2.1.16, obtemos as respostas dos itens a) e b)
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?
Calculando os valores de \(S_0, S_1, S_2\) e \(S_3\text{:}\)
\(\displaystyle S_0 = 8! = 40320\)
\(\displaystyle S_1 = 15120\)
\(\displaystyle S_2 = 2160\)
\(\displaystyle S_3 = 120\)
Queremos o número de permutações na qual, os valores 2, 3 e 4 não estão em suas posições originais. Então, precisamos calcular o valor de \(a_0\text{:}\)
Item b. Vamos contar o total de permutações e subtrair o número de permutações que possuem alguma letra na posição original. O total de permutações é \(PR_5^2 = \frac{5!}{2!} = 60.\) A resposta será dada por
Na qual, o conjunto \(A_I\) é o conjunto das permutações com a letra \(I\) na posição original.
Neste caso, vamos contar separadamente o número de permutações que tem alguma letra na posição original. Primeiro vamos contar 1 a 1, ou seja, fixamos a letra na posição original e calculamos o número de permutações das outras letras:
S: \(PR_4^2 = 12\)
A: \(P_4 = 24\)
G: \(PR_4^2 = 12\)
A: \(P_4 = 24\)
Z: \(PR_4^2 = 12\)
Assim, \(S_1 = 84.\)
Interseções 2 a 2, fixamos as letras nas posições originais e calculamos o número de permutações das outras letras:
(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?
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{.}\)
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
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.
Figura2.1.27.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,
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.
Figura2.1.28.Verificação das interseções.
11.
A Função Totiente de Euler, denotada por \(\phi(n)\text{,}\) conta a quantidade de números inteiros positivos menores ou iguais a \(n\) que são coprimos com \(n\) (ou seja, cujo único divisor comum com \(n\) é 1). Considere o número \(n = 300\text{.}\)
Escreva a fatoração em primos de 300.
Utilizando o Princípio da Inclusão-Exclusão, calcule \(\phi(300)\text{.}\)
Generalize o raciocínio do item anterior para deduzir a fórmula algébrica de \(\phi(n)\text{,}\) sabendo que a fatoração em primos de um número natural \(n\) é dada por \(n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}\text{.}\)
item a) A fatoração é \(300 = 2^2 \times 3 \times 5^2\text{.}\) Os divisores primos de 300 são 2, 3 e 5.
item b) Para que um número seja coprimo com 300, ele não pode ser múltiplo de 2, nem de 3, nem de 5. Seja \(\Omega = \{1, 2, \ldots, 300\}\text{.}\) Definimos:
\(A_2\text{:}\) múltiplos de 2 em \(\Omega\) (\(300/2 = 150\))
\(A_3\text{:}\) múltiplos de 3 em \(\Omega\) (\(300/3 = 100\))
\(A_5\text{:}\) múltiplos de 5 em \(\Omega\) (\(300/5 = 60\))
As interseções são calculadas pelos produtos dos primos:
item c) Seja \(\Omega = \{1, 2, \ldots, n\}\text{.}\) Para cada divisor primo \(p_i\) de \(n\text{,}\) defina \(A_i\) como o conjunto dos múltiplos de \(p_i\) em \(\Omega\text{.}\) A cardinalidade de cada conjunto individual é \(\#A_i = \frac{n}{p_i}\text{.}\)
A interseção de dois conjuntos \(A_i \cap A_j\) contém os múltiplos de \(p_i p_j\text{,}\) logo sua cardinalidade é \(\#(A_i \cap A_j) = \frac{n}{p_i p_j}\text{.}\) A lógica segue idêntica para interseções maiores.
Aplicando o Princípio da Inclusão-Exclusão para calcular a quantidade de elementos que não pertencem a nenhum \(A_i\) (ou seja, os números coprimos com \(n\)), temos:
Perceba que a longa expressão dentro dos parênteses grandes é exatamente o resultado do desenvolvimento do produto de binômios da forma \(\left(1 - \frac{1}{p_i}\right)\text{.}\) Portanto, a expressão pode ser fatorada na fórmula geral de Euler:
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?
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
\(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 é
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
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 é
(OMU 2024 - Prova Individual - Item b) Andrês decidiu visitar um museu com \(n\) exposições. Andrês e Marcelo são rivais. De quantas maneiras Andrês e Marcelo podem visitar exposições, de modo que eles nunca visitem uma mesma exposição, mas cada um visite pelo menos uma?
Considere que as exposições do museu estão numeradas de \(1\) até \(n\text{.}\) Podemos representar cada maneira de visitar o museu com uma \(n\)-úpla. Usando \(A, M\) e \(N\) como entradas da \(n\)-úpla, para indicar que Andrês, Marcelo e Nenhum deles, respectivamente, visitou a \(i\)-ésima exposição.
Podemos formar um total de \(3^n\)\(n\)-úplas dessa maneira. Depois, precisamos excluir as que não possuem o símbolo \(A\) ou que não possuem o símbolo \(M\text{.}\) Note que podem ser formadas \(2^n\)\(n\)-úplas com apenas os símbolos \(M\) e \(N\) (sem o símbolo A) e também podem ser formadas \(2^n\)\(n\)-úplas com apenas os símbolos \(A\) e \(N\) (sem o símbolo M). E pode ser formada somente 1 \(n\)-úpla com apenas o símbolo \(N\text{.}\)
Portanto, o número de maneiras de visitar o museu é \(3^n - 2^{n+1} + 1\text{.}\)
15.
(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.
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
Seis representantes estão participando de uma conferência em mesa redonda. No primeiro dia, eles se sentam em uma determinada ordem. De quantas maneiras diferentes eles podem se sentar no segundo dia de modo que ninguém tenha à sua direita a mesma pessoa que estava à sua direita no primeiro dia?
O problema consiste em encontrar o número de permutações circulares sem sucessões. Vamos numerar as pessoas de 1 a 6, na ordem em que sentaram no primeiro dia. Queremos evitar as 6 sucessões: \((1,2), (2,3), (3,4), (4,5), (5,6)\) e \((6,1)\text{.}\)
O total de permutações circulares sem restrições é \(P C_6 = (6-1)! = 5! = 120\text{.}\)
Seja \(A_i\) o conjunto das permutações em que a sucessão \(i\) ocorre. Pelo Princípio da Inclusão-Exclusão, a quantidade de arranjos onde nenhuma sucessão ocorre é:
onde \(S_k\) é a soma das cardinalidades das interseções de \(k\) conjuntos.
Para calcular \(S_k\text{,}\) escolhemos \(k\) sucessões dentre as 6 possíveis, o que pode ser feito de \(C_6^k\) maneiras. Ao obrigar que \(k\) sucessões ocorram, aglutinamos os 6 elementos em \(6-k\) blocos indivisíveis. A permutação circular desses \(6-k\) blocos é calculada por \((6-k-1)! = (5-k)!\text{.}\) Logo, \(S_k = C_6^k \times (5-k)!\text{.}\)
