Ir ao conteúdo principal

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

Ricardo Machado, Gabriel Guedes

Seção 1.5 Permutações com Repetições

Quando estamos contando o número de permutações, precisamos levar em consideração se todos os elementos são distintos ou não, pois a permutação de dois elementos idênticos não gera uma nova permutação. Veja o exemplo a seguir.

Exemplo 1.5.1.

Quantos são os anagramas da palavra SAGEMATH?
Solução.
Observe que a palavra SAGEMATH possui 8 letras, mas a letra A aparece duas vezes, o restante aparece apenas uma vez. Podemos imaginar, por enquanto, que a palavra é assim
\begin{equation*} SA_1GEMA_2TH \end{equation*}
com \(A_1\neq A_2\text{,}\) nesse caso teríamos um total de
\begin{equation*} P_8 = 8! \end{equation*}
permutações.
Agora vamos resolver o problema das repetições. Observe que para cada permutação, trocar os A's de lugar não muda o anagrama. Portanto, precisamos dividir do total de permutações, o número de maneiras de ordenar os A's, como se fossem elementos distintos. Dessa forma, a resposta é
\begin{equation*} \frac{P_8}{P_2}=20160. \end{equation*}

Definição 1.5.2.

O número de permutações com repetição de \(n\) objetos, onde há: \(\beta_1\) cópias idênticas de \(b_1\text{,}\) \(\beta_2\) cópias idênticas de \(b_2\text{,}\) e assim por diante, até \(\beta_k\) cópias idênticas de \(b_k\) satisfazendo a condição:
\begin{equation*} \beta_1 + \beta_2 + \cdots + \beta_k = n, \end{equation*}
é denotado por:
\begin{equation*} PR_n^{\beta_1, \beta_2, \ldots, \beta_k}. \end{equation*}

Tecnologia 1.5.3.

Obtendo a lista com todas as permutações com repetições dos elementos \(1, 1, 1, 2, 2\text{:}\)
Considere os \(n\) objetos da seguinte forma:
\begin{equation*} \underbrace{b_1b_1\ldots b_1}_{\beta_1 \text{ vezes}} \underbrace{b_2b_2\ldots b_2}_{\beta_2 \text{ vezes}}\ldots\underbrace{b_kb_k\ldots b_k}_{\beta_k \text{ vezes}} \end{equation*}
observe que \(\beta_1+\beta_2+\cdots+ \beta_k = n.\) Para encontrar o número de formas de permutar esses elementos, vamos quebrar em \(k\) etapas. Na primeira etapa, vamos escolher \(\beta_1\) posições, dentre \(n\text{,}\) para colocar \(b_1: C_n^{\beta_1}\text{.}\) Na segunda etapa, vamos escolher \(\beta_2\) posições, dentre \(n-\beta_1\text{,}\) para colocar \(b_2: C_{n-\beta_1}^{\beta_2}\text{.}\) \(\ldots\) Na \(k\)-ésima etapa, vamos escolher \(\beta_k\) posições, dentre \(n-\beta_1-\beta_2-\cdots-\beta_{k-1}=\beta_k\text{,}\) para colocar \(b_k: C_{\beta_k}^{\beta_k}\text{.}\) Portanto,
\begin{equation*} PR_n^{\beta_1, \beta_2, \ldots, \beta_k} =~ C_n^{\beta_1}\times C_{n-\beta_1}^{\beta_2} \times \cdots \times C_{\beta_k}^{\beta_k} \\ \end{equation*}
Calculando cada \(C_x^y\)
\begin{equation*} PR_n^{\beta_1, \beta_2, \ldots, \beta_k} = \frac{n!}{\beta_1!\underbrace{(n-\beta_1)!}_{x_1}}\cdot\frac{\overbrace{(n-\beta_1)!}^{x_1}}{\beta_2!\underbrace{(n-\beta_1-\beta_2)!}_{x_2}}\cdots\frac{\overbrace{\beta_k!}^{x_k}}{\beta_k!\underbrace{(\beta_k-\beta_k)!}_{=1}} \end{equation*}
E cancelando os \(x_i's\text{,}\) obtemos
\begin{equation*} PR_n^{\beta_1, \beta_2, \ldots, \beta_k}= \frac{n!}{\beta_1!\times \beta_2!\times\cdots\times \beta_k!}. \end{equation*}

Tecnologia 1.5.5.

Obtendo o número de permutações com repetições no Sage. Da linha 1 até a linha 5 temos uma implementação de uma função para efetuar esse cálculo. Na linha 6, a função está sendo usada para o caso \(n=10, \beta_1 = 3, \beta_2=2, \beta_3=2, \beta_4=1, \beta_5=1\) e \(\beta_6=1\text{.}\)
Para entender essa implementação e aprender mais sobre o SageMath veja a referência [6.7].

Exemplo 1.5.6.

Quantos são os anagramas da palavra MATEMATICA?
Solução.
Temos uma palavra com 10 letras. Das 10 letras, temos 3 A's, 2 M's e 2 T's e as outras aparecem uma única vez, portanto o número de anagramas desta palavra é
\begin{equation*} PR_{10}^{3, 2, 2} = 151200. \end{equation*}

Exemplo 1.5.7.

Quantos são os anagramas da palavra MATEMATICA que começam por vogal?
Solução.
Se o anagrama começa por vogal, temos as possibilidades, A ou E ou I.
Começando com A, temos um total de \(PR_9^{2, 2, 2}\) anagramas, começando com E, temos um total de \(PR_9^{3, 2, 2}\) anagramas e começando com I, temos um total de \(PR_9^{3, 2, 2}\) anagramas. Portanto a resposta é
\begin{equation*} PR_9^{2, 2, 2} + 2\times PR_9^{3, 2, 2} = 75600. \end{equation*}
Este cálculo pode ser efetuado no Sage da seguinte maneira:

Exemplo 1.5.8.

De quantos modos podemos dividir 12 pessoas em três grupos de quatro pessoas cada?
Solução.
Use os números de 1 à 12 para representar as pessoas. Desta forma, a posição de cada permutação dos dígitos:
\begin{equation*} 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3 \end{equation*}
serve para representar quem está no grupo 1, no grupo 2 e no grupo 3, respectivamente. Assim pela ordem que está escrito, os números que estão no grupo 1 são: \(1, 2, 3, 4\text{,}\) no grupo 2 são \(5, 6, 7, 8\) e no grupo 3 são \(9, 10, 11, 12\text{.}\)
Desta forma, usando permutação com repetição para
\begin{equation*} 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3\text{,} \end{equation*}
o número de maneiras de dividir 12 pessoas em três grupos, levando em consideração a ordem dos grupos é
\begin{equation*} PR_{12}^{4, 4, 4} = \frac{12!}{4!4!4!}. \end{equation*}
Como a ordem dos grupos não é importante, estamos contando a mais. Assim, precisamos dividir tudo pelo número de maneiras de ordenar os 3 grupos que é 3!. Portanto a resposta é
\begin{equation*} \frac{12!}{4!4!4!3!} = 5775. \end{equation*}

Exemplo 1.5.9.

Quantos são os anagramas da palavra REPÚBLICA nos quais as vogais aparecem em ordem alfabética?
Solução.
A palavra REPÚBLICA possui 9 letras distintas. As vogais são E, U, I, A (4 vogais). O problema exige que, independentemente de onde as vogais estejam no anagrama, elas apareçam na ordem A, E, I, U, lidas da esquerda para a direita.
O truque para resolver problemas de ordem relativa é tratar os elementos que possuem ordem fixa como se fossem letras idênticas. Imagine que substituímos todas as vogais por uma letra genérica, digamos, X. A palavra se torna:
\begin{equation*} RXPXBLXCX \end{equation*}
Ao permutarmos as letras dessa nova palavra, as posições dos X's estarão perfeitamente definidas. Como os X's são idênticos, a ordem entre eles não importa na contagem. Após embaralhar, basta ir da esquerda para a direita e substituir o primeiro X por A, o segundo por E, o terceiro por I e o quarto por U.
Portanto, o número de anagramas com essa propriedade é exatamente o número de permutações de 9 letras com 4 repetições (os X's):
\begin{equation*} PR_9^{4} = \frac{9!}{4!} = 15120. \end{equation*}

Exemplo 1.5.10.

Usando os algarismos 1, 2, 2, 3, 3, 3, quantos números ímpares de 6 dígitos podem ser formados?
Solução.
Para que o número seja ímpar, ele deve terminar obrigatoriamente com um algarismo ímpar. Dentre os algarismos disponíveis, o último dígito pode ser 1 ou 3. Precisamos dividir o problema nestes dois casos:
1º Caso (termina em 1): Fixando o 1 na última posição, restam os algarismos 2, 2, 3, 3, 3 para preencher as 5 primeiras posições. O número de maneiras de organizá-los é:
\begin{equation*} PR_5^{2, 3} = \frac{5!}{2!3!} = 10. \end{equation*}
2º Caso (termina em 3): Fixando um 3 na última posição, restam os algarismos 1, 2, 2, 3, 3 para as 5 primeiras posições. O número de maneiras de organizá-los é:
\begin{equation*} PR_5^{2, 2} = \frac{5!}{2!2!1!} = 30. \end{equation*}
Pelo Princípio Aditivo, somamos as possibilidades dos dois casos mutuamente exclusivos:
\begin{equation*} 10 + 30 = 40. \end{equation*}

Exemplo 1.5.11.

João comprou 8 bombons idênticos e deseja distribuí-los entre seus 3 sobrinhos. De quantas maneiras ele pode fazer essa distribuição, sabendo que é permitido que algum sobrinho fique sem nenhum bombom?
Solução.
Este é um problema clássico de distribuição de objetos idênticos. Para resolvê-lo, vamos aplicar o Princípio da Bijeção, transformando a ação de distribuir bombons em uma ação de formar anagramas.
Vamos representar cada bombom por uma bolinha (\(\bullet\)) e usar barras verticais (\(|\)) para separar a quantidade de bombons que vai para cada sobrinho. Como são 3 sobrinhos, precisamos de apenas 2 barras para dividir as bolinhas em 3 partes (o que fica à esquerda da primeira barra vai para o 1º sobrinho, o que fica entre as barras vai para o 2º, e o que fica à direita da segunda barra vai para o 3º).
Veja como essa bijeção funciona na prática. Cada distribuição corresponde a uma única sequência de símbolos e vice-versa:
  • A sequência \(\bullet \bullet \bullet ~|~ \bullet ~|~ \bullet \bullet \bullet \bullet\) significa que o primeiro sobrinho recebeu 3 bombons, o segundo recebeu 1 e o terceiro recebeu 4.
  • A sequência \(|~ \bullet \bullet \bullet \bullet \bullet \bullet \bullet \bullet ~|\) significa que o primeiro e o terceiro sobrinhos não receberam nada (0 bombons), e o segundo recebeu todos os 8.
Como estabelecemos uma correspondência um-para-um (bijeção) entre as distribuições possíveis e os anagramas formados por 8 bolinhas e 2 barras, basta contarmos a quantidade de anagramas. No total, são 10 símbolos com repetições. O número de maneiras é dado por:
\begin{equation*} PR_{10}^{8, 2} = \frac{10!}{8!2!} = 45. \end{equation*}

Exercícios Exercícios

1.

Um byte, em um computador, é uma sequência de 8 algarismos formada apenas com \(0's\) e \(1's\text{.}\) Determine quantos bytes existem formados com três \(1's\) e cinco \(0's\text{.}\)
Resposta.
\(56\)
Solução.
\(PR_{8}^{3,5} = 56\)

2.

Quantos são os anagramas da palavra:
  1. PRECEDENTE;
  2. PROPONENTE;
  3. FOTOSSINTETIZANTES.
Resposta.
  1. \(\displaystyle 151200\)
  2. \(\displaystyle 226800\)
  3. \(\displaystyle 2778808032000\)
Solução.
  1. \(\displaystyle PR_{10}^{4}=151200\)
  2. \(\displaystyle PR_{10}^{2,2,2,2}=226800\)
  3. \(PR_{18}^{2, 4, 3, 2, 2, 2}=2778808032000\text{.}\)

3.

Quantos são os anagramas da palavra ESTATISTICA em que todas as letras T aparecem juntas (em um único bloco)?
Resposta.
45360
Solução.
A palavra ESTATISTICA possui 11 letras no total, com as seguintes repetições: S(2), T(3), A(2), I(2). As letras E e C aparecem apenas uma vez.
Como as 3 letras T devem ficar juntas, nós as agrupamos e as tratamos como se fossem um único "super elemento" ou bloco indissociável: (TTT).
Agora, em vez de 11 letras, precisamos permutar 9 "elementos": o bloco (TTT) e as letras E, S, S, A, A, I, I, C.
Dentre esses 9 elementos que vamos embaralhar, temos repetições: a letra S aparece 2 vezes, a letra A aparece 2 vezes e a letra I aparece 2 vezes. Portanto, o número de anagramas é dado por uma permutação com repetição:
\begin{equation*} PR_9^{2,2,2} = \frac{9!}{2!2!2!} = \frac{362880}{2 \times 2 \times 2} = 45360. \end{equation*}
Note que não precisamos calcular a permutação dos T's dentro do bloco (TTT), pois, como as letras são idênticas, trocá-las de lugar entre si não gera um anagrama diferente.

4.

Com relação aos anagramas da palavra OPERADOR:
  1. Quantos têm as vogais em ordem alfabética, mesmo não estando juntas?
  2. Quantos têm as vogais e as consoantes intercaladas?
Resposta.
  1. 840
  2. 288
Solução.
item a. O total de anagramas da palavra OPERADOR é \(PR_8^{2,2}\text{,}\) pois a palavra possui duas letras O, duas letras R, as outras são distintas. Para contar apenas os anagramas que têm as vogais em ordem alfabética, mesmo não estando juntas, precisamos dividir pelo número de maneiras de ordenar as vogais. Portanto a resposta é
\begin{equation*} \frac{PR_8^{2,2}}{PR_4^2} = 840. \end{equation*}
item b. Note que são 4 vogais e 4 consoantes, portanto os anagramas podem começar por vogal ou consoante. Fixando as vogais e deixando um espaço após cada vogal (para colocar as consoantes depois), a partir a primeira vogal temos \(PR_4^2\) maneiras de ordenar as 4 vogais e \(PR_4^2\) maneiras de ordenar as 4 consoantes nos espaços deixados. Como também podemos começar por consoantes, a resposta é
\begin{equation*} PR_4^2\cdot PR_4^2 \cdot 2 = 288. \end{equation*}

5.

Quantos números de 8 dígitos, maiores que 50.000.000, podem ser formados usando apenas os algarismos 1, 2, 5, 5, 5, 7, 7, 7?
Resposta.
840
Solução.
Basta contar o número de permutações com repetições dos algarismos, começando com 5 ou 7:
\begin{equation*} PR_7^{3,2} + PR_7^{3,2} = 2\cdot PR_7^{3,2} = 2\cdot 420 = 840. \end{equation*}

6.

De quantos modos podemos colocar em fila 6 letras A, 6 letras B, 5 letras C e 4 letras D, de modo que não haja duas letras C juntas?
Resposta.
10406235840
Solução.
Inicialmente, podemos calcular o número de maneiras de colocar em fila todas as letras A, B e D: \(PR_{16}^{6,6,4}\text{.}\) Depois, podemos deixar essas letras separadas por um espaço, começando por um espaço antes da primeira letra e terminando com um espaço depois da última letra:
\begin{equation*} \_A\_A\_\cdots \_D\_D\_. \end{equation*}
Agora, precisamos escolher 5 espaços, dentre os 17 disponíveis, para colocar as letras C. Isto pode ser feito de \(C_{17, 5}\) maneiras. Portanto, a resposta é
\begin{equation*} PR_{16}^{6,6,4} \cdot C_{17,5} = 10406235840. \end{equation*}

7.

Em um sistema de coordenadas tridimensional (3D), uma partícula parte da origem \((0,0,0)\) e precisa chegar ao ponto \((3, 2, 4)\text{.}\) A cada passo, ela só pode se deslocar 1 unidade no sentido positivo do eixo X, eixo Y ou eixo Z. Quantos trajetos diferentes a partícula pode fazer?
Resposta.
1260
Solução.
Para ir de \((0,0,0)\) até \((3, 2, 4)\) usando apenas os sentidos positivos, a partícula precisará dar, em qualquer ordem: 3 passos na direção X, 2 passos na direção Y e 4 passos na direção Z. O total de passos será sempre \(3 + 2 + 4 = 9\text{.}\)
Cada trajeto corresponde a um "anagrama" formado por 3 letras X, 2 letras Y e 4 letras Z (por exemplo, XXYZZXYZY). O número de trajetos é dado por:
\begin{equation*} PR_9^{3, 2, 4} = \frac{9!}{3!2!4!} = 1260. \end{equation*}

8.

(OPEMAT 2016 - nível 2) A figura abaixo representa o mapa de uma cidade. Cada aresta representa uma rua e cada vértice representa um cruzamento. Quantos são os trajetos de comprimento mínimo ligando o ponto A ao ponto B?
Resposta.
1743
Solução.
Observe que são 8 movimentos para direita e 6 movimentos para baixo, mas o mapa possui um "buraco". Inicialmente, podemos completar o mapa da cidade com um cruzamento onde tem um "buraco" e rotular este cruzamento por ponto C. Agora, podemos calcular todos os caminhos deste mapa modificado: \(PR_{14}^{8,6}\text{.}\) Depois, subtraimos deste valor o número total de caminhos que passam por C: \(PR_9^{5,4}\cdot PR_{5}^{3,2}\text{.}\) Portanto, a resposta é
\begin{equation*} PR_{14}^{8,6} - PR_9^{5,4}\cdot PR_{5}^{3,2} = 3003 - 126\cdot 10 = 1743. \end{equation*}

9.

(OBM 2011 - 2ª fase do nível 3)
Uma sequência de letras, com ou sem sentido, é dita alternada quando é formada alternadamente por consoantes e vogais. Por exemplo, EZEQAF, MATEMÁTICA, LEGAL e ANIMADA são palavras alternadas, mas DSOIUF, DINHEIRO e ORDINÁRIO não são. Quantos anagramas da palavra FELICIDADE (incluindo a palavra FELICIDADE) são sequências alternadas?
Resposta.
3600
Solução.
As consoantes de FELICIDADE são F, L, C, D, D e as vogais são E, I, I, A, E. Como são 5 vogais e 5 consoantes, cada anagrama alternado terá cada consoante em posição ímpar ou em posição par. Organizando as consoantes em posições ímpares, ficamos com a seguinte organização
\begin{equation*} \text{F_L_C_D_D_} \end{equation*}
Na qual, os espaços \(\verb|_|\) serão ocupados por vogais. Assim, temos um total de \(PR_5^2\) maneiras de ordenar essas consoantes. Para ordenar as vogais, temos \(PR_5^{2, 2}\) maneiras, pois temos no total 5 letras, sendo duas letras E, duas letras I e uma letra A.
Como podemos alterar as vogais com as consoantes, o número de anagramas alternados de FELICIDADE é
\begin{equation*} PR_5^2\times PR_5^{2, 2} \times 2 = 60 \times 30 \times 2 = 3600. \end{equation*}

10.

De quantos formas 12 estudantes podem ser divididos e colocados em 3 salas, sendo 4 na primeira, 5 na segunda e 3 na terceira?
Resposta.
27720
Solução.
Pense na seguinte lista:
\begin{equation*} L= [1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3]. \end{equation*}
Para cada permutação da lista \(L\text{,}\) podemos distribuir os estudantes nas salas da seguinte maneira. Use a posição do número para indicar a pessoa e o número para indicar a sala. Desta forma, a resposta é:
\begin{equation*} PR_{12}^{4, 5, 3} = 27720. \end{equation*}
Por exemplo, a permutação identidade, que é a apresentada na lista \(L\) indica que a 1ª, a 2ª a 3ª e a 4ª pessoa deve ficar na sala 1. A 4ª, a 5ª, a 6ª, a 7ª, e a 8ª pessoa deve ficar na sala 2 e assim por diante.

11.

De quantos modos 8 pessoas podem ocupar duas salas distintas, devendo cada sala conter pelo menos 3 pessoas?
Resposta.
182
Solução.
Observe que temos 3 casos para distribuir as pessoas nas duas salas.
1º caso: 3 pessoas na sala 1 e 5 pessoas na sala 2. Neste caso temos um total de \(PR_8^{3, 5}\) soluções.
2º caso: 4 pessoas na sala 1 e 4 pessoas na sala 2. Neste caso temos um total de \(PR_8^{4, 4}\) soluções.
3º caso: 5 pessoas na sala 1 e 3 pessoas na sala 2. Neste caso temos um total de \(PR_8^{5, 3}\) soluções.
Portanto a resposta é
\begin{equation*} PR_8^{3, 5} + PR_8^{4, 4} + PR_8^{5, 3} = 182. \end{equation*}

12.

Um baralho tem 52 cartas. De quantos modos podemos distribuí-las entre 4 jogadores, de modo que cada um receba 13 cartas?
Resposta.
53644737765488792839237440000
Solução.
Pense em uma lista composta por 13 números 1, 13 números 2, 13 números 3 e 13 números 4. O número de permutações com repetições desta lista é o número de modos de distribuir as 52 duas cartas entre os 4 jogadores, com cada um recebendo 13 cartas.
A justificativa é a seguinte. Para cada elemento da lista permutada, use a posição do elemento para pegar a carta que deve estar em uma pilha ou ordenada, e use o número para indicar a pessoa, sendo o número 1 indicando a primeira pessoa e assim por diante. A resposta é:
\begin{equation*} PR_{52}^{13, 13, 13, 13} = 53644737765488792839237440000. \end{equation*}

13.

(Enem 2019 - Modificado) Uma empresa confecciona e comercializa um brinquedo formado por uma locomotiva, pintada na cor preta, mais 12 vagões de iguais formato e tamanho, numerados de 1 a 12. Dos 12 vagões, 4 são pintados na cor vermelha, 3 na cor azul, 3 na cor verde e 2 na cor amarela. O trem é montado utilizando-se uma locomotiva e 12 vagões, ordenados crescentemente segundo suas numerações, conforme ilustrado na figura.
De acordo com as possíveis variações nas colorações dos vagões, qual a quantidade de trens que podem ser montados?
Resposta.
277200
Solução.
Basta contar o número de maneiras de permutar as corres, sendo 4 vermelhos, 3 azuis, 3 verdes e 2 amarelos. Logo, o número de trens que podem ser montados é
\begin{equation*} PR_{12}^{4,3,3,2} = 277200. \end{equation*}

14.

Quantos números de 6 algarismos podem ser formados utilizando-se exclusivamente os algarismos 0, 0, 1, 1, 2 e 3?
Resposta.
120
Solução.
Precisamos permutar os 6 algarismos disponíveis, com repetições de dois 0's e dois 1's. O total de permutações irrestritas é \(PR_6^{2,2}\text{.}\) No entanto, um número não pode começar com o algarismo 0.
Para descontar os casos inválidos, fixamos um 0 na primeira posição. Restam os algarismos 0, 1, 1, 2, 3 para as 5 posições seguintes. O número de permutações inválidas é \(PR_5^{2}\) (pois apenas o 1 se repete duas vezes no que sobrou).
Portanto, a resposta é o total de permutações menos as inválidas:
\begin{equation*} PR_6^{2,2} - PR_5^{2} = 180 - 60 = 120. \end{equation*}

15.

Um navio possui um mastro vertical e dispõe de 7 bandeiras para emitir sinais: 3 vermelhas (idênticas), 2 brancas (idênticas) e 2 azuis (idênticas). Um sinal é formado hasteando-se exatamente 6 dessas bandeiras, uma abaixo da outra. Quantos sinais diferentes podem ser emitidos?
Resposta.
210
Solução.
Como o navio tem 7 bandeiras mas só vai hastear 6, exatamente 1 bandeira ficará de fora. Precisamos dividir o problema em 3 casos, dependendo da cor da bandeira que não será usada:
Caso 1 (Fica de fora uma vermelha): Serão hasteadas 2 vermelhas, 2 brancas e 2 azuis. O número de sinais é \(PR_6^{2,2,2} = 90\text{.}\)
Caso 2 (Fica de fora uma branca): Serão hasteadas 3 vermelhas, 1 branca e 2 azuis. O número de sinais é \(PR_6^{3,2,1} = 60\text{.}\)
Caso 3 (Fica de fora uma azul): Serão hasteadas 3 vermelhas, 2 brancas e 1 azul. O número de sinais é \(PR_6^{3,2,1} = 60\text{.}\)
Pelo Princípio Aditivo, o total de sinais distintos é \(90 + 60 + 60 = 210\text{.}\)

16.

Dez pessoas, entre elas Ana, Beto e Carlos, estão em uma fila. De quantas maneiras diferentes essa fila pode ser formada de modo que Ana esteja sempre à frente de Beto, e Beto esteja sempre à frente de Carlos? (Eles não precisam estar lado a lado, apenas respeitar essa ordem relativa de chegada).
Resposta.
604800
Solução.
Este problema impõe uma ordem fixa a três pessoas específicas (Ana, Beto, Carlos). Para resolvê-lo, tratamos temporariamente Ana, Beto e Carlos como se fossem pessoas "idênticas", substituindo-os por um curinga (digamos, X).
A fila será composta por três curingas X e pelas 7 outras pessoas distintas. O número de permutações dessa configuração é:
\begin{equation*} PR_{10}^{3} = \frac{10!}{3!} = 604800. \end{equation*}
Para cada uma dessas 604800 disposições, existe apenas uma única maneira válida de substituir os curingas de volta pelas pessoas originais: o primeiro X encontrado na fila (de frente para trás) será obrigatoriamente a Ana, o segundo X será o Beto e o terceiro X será o Carlos. Portanto, a resposta é 604800.

17.

Quantos anagramas da palavra PARALELOGRAMO começam e terminam com a mesma letra?
Resposta.
14968800
Solução.
A palavra tem 13 letras no total: A(3), R(2), L(2), O(2), P(1), E(1), G(1), M(1). Para começar e terminar com a mesma letra, essa letra precisa se repetir na palavra original pelo menos duas vezes. As únicas candidatas para as extremidades são A, R, L e O.
Calculamos os casos separadamente, isolando a letra escolhida nas pontas e permutando as 11 letras restantes no miolo do anagrama:
Começam e terminam com A: Retirando dois A's, restam 11 letras com as repetições R(2), L(2), O(2) e A(1). Total: \(PR_{11}^{2,2,2} = 4989600\text{.}\)
Começam e terminam com R: Retirando dois R's, restam 11 letras com as repetições A(3), L(2), O(2). Total: \(PR_{11}^{3,2,2} = 3326400\text{.}\)
Começam e terminam com L: Retirando dois L's, restam 11 letras com as repetições A(3), R(2), O(2). Total: \(PR_{11}^{3,2,2} = 3326400\text{.}\)
Começam e terminam com O: Retirando dois O's, restam 11 letras com as repetições A(3), R(2), L(2). Total: \(PR_{11}^{3,2,2} = 3326400\text{.}\)
Pelo Princípio Aditivo, somamos tudo:
\begin{equation*} 4989600 + 3326400 + 3326400 + 3326400 = 14968800. \end{equation*}

18.

No mapa abaixo estão esboçadas as ruas de um bairro. As ruas verticais são paralelas entre si e é igual a distância entre ruas consecutivas; o mesmo acontece com as ruas horizontais. Calcule o número de formas de sair de A e chegar até B percorrendo a menor distância possível.
Resposta.
735
Solução.
Podemos separar os caminhos que saem de A e chegam em B em tipos disjuntos.
Figura 1.5.12. Mapa da solução.
1º tipo: De A para X e de X para B. Nesse caso temos \(PR_7^{4, 3}\) caminhos de A para X e \(PR_5^{4, 1}\) caminhos de X para B. No total temos
\begin{equation*} PR_7^{4, 3} \times PR_5^{4, 1} \end{equation*}
caminhos do 1º tipo.
2º tipo: De A para Y e de Y para B. Nesse caso temos \(PR_8^{5, 3}\) caminhos de A para Y e \(PR_5^{3, 2}\) caminhos de Y para B. No total temos
\begin{equation*} PR_8^{5, 3} \times PR_5^{3, 2} \end{equation*}
caminhos do 2º tipo.
Como os caminhos do 1º e 2º tipos são disjuntos a resposta é
\begin{equation*} PR_7^{4, 3}\times PR_5^{4, 1} + PR_8^{5, 3}\times PR_5^{3, 2} = 735. \end{equation*}

19.

João vai comprar algo que custa \(55\) centavos em uma máquina automática e dispõe de \(8\) moedas de \(5\) centavos do mesmo modelo e \(5\) moedas de \(10\) centavos também do mesmo modelo. Assim, sendo \(n\) o número de diferentes sequências de moedas que ele pode inserir de modo a totalizar os 55 centavos, determine o valor de \(n\text{.}\)
Resposta.
\(133\)
Solução.
João pode escolher os valores das moedas de \(4\) maneiras, em cada caso, existem várias maneiras de ordenar as moedas escolhida:
  1. \(5\) moedas de \(10\) centavos e \(1\) de \(5\) centavos, totalizando \(PR_{6}^{5, 1}\) ordens possíveis;
  2. \(4\) moedas de \(10\) centavos e \(3\) de \(5\) centavos, totalizando \(PR_{7}^{4, 3}\) ordens possíveis;
  3. \(3\) moedas de \(10\) centavos e \(5\) de \(5\) centavos, totalizando \(PR_{8}^{5, 3}\) ordens possíveis;
  4. \(2\) moedas de \(10\) centavos e \(7\) de \(5\) centavos, totalizando \(PR_{9}^{7, 2}\) ordens possíveis.
Portanto, a resposta é
\begin{equation*} PR_{6}^{5, 1} + PR_{7}^{4, 3}+ PR_{8}^{5, 3}+ PR_{9}^{7, 2}=133. \end{equation*}

20. (Caminhos de Delannoy).

Diremos que uma partícula faz um caminho de Delannoy se estando no ponto \((a,b)\) ela pode se deslocar para os pontos:
  1. Leste: \((a+1,b)\text{,}\) abreviado por L;
  2. Norte: \((a,b+1)\text{,}\) abreviado por N;
  3. Nordeste: \((a+1,b+1)\text{,}\) abreviado por D de diagonal.
Calcule o número de caminhos de Delannoy da origem até o ponto \(C(m,n)\text{.}\)
Dica.
Tecnologia 1.5.13.
Digite uma sequência de L's, N's e D's e clique no botão "Update" para obter o respectivo caminho no reticulado.
Figura 1.5.14. Um caminho de Delannoy no reticulado.
Resposta.
Puponha que \(m\leq n\text{,}\) se não for, permute \(m\) e \(n\text{.}\) A resposta é:
\begin{equation*} \sum_{k=0}^{m}PR^{m-k,n-k,k}_{m+n-k}. \end{equation*}
Solução.
Para contar o total de caminhos até um ponto \(C(m,n)\text{,}\) vamos considerar o \(m\lt n\text{.}\) Quando consideramos \(m\lt n\) isso fará com que no máximo podemos fazer \(m\) movimentos diagonias (para o caso \(m>n\) o número máximo de movimentos diagonais é \(n\)). Assim, teremos um total de \(m+1\) casos para analisarmos:
Caso 1: Contaremos todos os caminhos sem movimentos na direção nordeste, ou seja teremos que contar todas as permutações da palavra \(LLLL\ldots LNNNN\ldots N\text{,}\) onde a letra \(L\) aparece \(m\) vezes e a letra \(N\) aparece \(n\) vezes, totalizando \(m+n\) elementos. Assim obtemos,
\begin{equation*} PR^{m,n}_{m+n}. \end{equation*}
Caso 2: Contaremos todos os caminhos onde faremos apenas um movimento na direção nordeste, assim, queremos contar as permutações da palavra \(DLL\ldots LNN\ldots N\text{,}\) onde a letra \(L\) aparece \(m-1\) vezes, a letra \(N\) aparece \(n-1\) vezes, e a letra \(D\) uma vez, totalizando \(m+n-1\) elementos. Assim teremos,
\begin{equation*} PR^{m-1,n-1,1}_{m+n-1}. \end{equation*}
Caso 3: Contaremos todos os caminhos onde faremos dois movimentos diagonais (ou na direção nordeste) e \(m-2\) movimentos na direção leste e \(n-2\) movimentos na direção norte. Assim contaremos o número de permutações da palavra \(DDLLL\ldots LNNN\ldots N\text{,}\) onde a letra \(L\) aparece \(m-2\) vezes e a letra \(N\) \(n-2\) vezes. Teremos o total de,
\begin{equation*} PR^{m-2,n-2,2}_{m+n-2}. \end{equation*}
Os casos seguirão, aumentando o número de movimentos diagonais, e assim chegaremos ao caso \(m+1\text{,}\) então:
Caso \(m+1\text{:}\) Contaremos todos os caminhos onde fazemos \(m\) movimentos diagonais. Teremos então que contar todas as permutações da palavra \(DDD\ldots DNN\ldots N\text{,}\) onde a letra \(D\) aparece \(m\) vezes e a letra \(N\) aparece \(n-m\) vezes, totalizando \(m+(n-m)\) elementos. Obtendo assim,
\begin{equation*} PR^{0,n-m,m}_{m+(n-m)}. \end{equation*}
Pelo princípio aditivo, devemos somar todos os casos para que o número total de caminhos possíveis seja encontrado. Portanto,
\begin{equation*} PR^{m,n,0}_{m+n}+PR^{m-1,n-1,1}_{m+n-1}+\cdots+PR^{0,n-m,m}_{m+(m-n)}. \end{equation*}
Que pode ser reescrito como:
\begin{equation*} \sum_{k=0}^{m}PR^{m-k,n-k,k}_{m+n-k}. \end{equation*}
<Anterior^TopPróximo>
Feito com PreTeXt
Powered by Runestone