Ir ao conteúdo principal

Matemática Discreta: notas de aula

Ricardo Machado

Seção 6.6 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 6.6.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 6.6.2.

Quando permutamos uma lista de objetos, na qual, nem todos os elementos são distintos, precisamos considerar que permutar dois elementos idênticos não gera uma nova permutação. Este tipo de permutação é chamado de permutação com repetição.

Tecnologia 6.6.3.

Obtendo a lista com todas as permutações com repetições dos elementos \(1, 1, 1, 2, 2\text{:}\)

Definição 6.6.4.

O número de permutações de \(n\) objetos, com um objeto repetido \(r_1\) vezes, outro objeto repetido \(r_2\) vezes, até o "último" objeto repetido \(r_k\) vezes, com
\begin{equation*} r_1+r_2+\cdots+r_k=n \end{equation*}
é denotado por:
\begin{equation*} PR_n^{r_1, r_2, \ldots, r_k}. \end{equation*}
Considere os \(n\) objetos da seguinte forma:
\begin{equation*} \underbrace{A_1A_1\ldots A_1}_{r_1 \text{ vezes}} \underbrace{A_2A_2\ldots A_2}_{r_2 \text{ vezes}}\ldots\underbrace{A_kA_k\ldots A_k}_{r_k \text{ vezes}} \end{equation*}
observe que \(r_1+r_2+\cdots+ r_k = n.\) Para encontrar o número de formas de permutar esses elementos, vamos quebrar em \(k\) etapas. Na primeira etapa, vamos escolher \(r_1\) posições, dentre \(n\text{,}\) para colocar \(A_1: C_n^{r_1}\text{.}\) Na segunda etapa, vamos escolher \(r_2\) posições, dentre \(n-r_1\text{,}\) para colocar \(A_2: C_{n-r_1}^{r_2}\text{.}\) \(\ldots\) Na \(k\)-ésima etapa, vamos escolher \(r_k\) posições, dentre \(n-r_1-r_2-\cdots-r_{k-1}=r_k\text{,}\) para colocar \(A_k: C_{r_k}^{r_k}\text{.}\) Portanto,
\begin{equation*} PR_n^{r_1, r_2, \ldots, r_k} =~ C_n^{r_1}\times C_{n-r_1}^{r_2} \times \cdots \times C_{r_k}^{r_k} \\ \end{equation*}
Calculando cada \(C_x^y\)
\begin{equation*} PR_n^{r_1, r_2, \ldots, r_k} = \frac{n!}{r_1!\underbrace{(n-r_1)!}_{x_1}}\cdot\frac{\overbrace{(n-r_1)!}^{x_1}}{r_2!\underbrace{(n-r_1-r_2)!}_{x_2}}\cdots\frac{\overbrace{r_k!}^{x_k}}{r_k!\underbrace{(r_k-r_k)!}_{=1}} \end{equation*}
E cancelando os \(x_i's\text{,}\) obtemos
\begin{equation*} PR_n^{r_1, r_2, \ldots, r_k}= \frac{n!}{r_1!\times r_2!\times\cdots\times r_k!}. \end{equation*}

Tecnologia 6.6.6.

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, r_1 = 3, r_2=2, r_3=2, r_4=1, r_5=1\) e \(r_6=1\text{.}\)
Para entender essa implementação e aprender mais sobre o SageMath veja a referência [10.5].

Exemplo 6.6.7.

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 6.6.8.

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 6.6.9.

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*}

Exercícios Exercícios

1.

(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

2.

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

3.

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

4.

De quantos modos podem ser pintados 15 objetos iguais usando 6 cores diferentes?
Resposta.
15504

5.

Quantas são as opções que temos de colocar 10 bolinhas \((\bullet)\) e 7 barras \((~|~)\) em sequência?
Resposta.
19448

6.

(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*}

7.

Um bar vende três tipos de cerveja: Antártica, Brahma e Devassa. De quantos modos uma pessoa pode comprar 7 garrafas de cerveja?
Resposta.
36
Solução.
O número de soluções deste problema é o mesmo que o número de solução inteiras, não negativas da equação:
\begin{equation*} x_1 + x_2 + x_3 = 7. \end{equation*}
Portanto a resposta é
\begin{equation*} PR_9^{7, 2} = 36. \end{equation*}

8.

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.

9.

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*}

10.

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*}

11.

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 6.6.10. 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*}

12.

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*}
<Anterior^TopPróximo>
Feito com PreTeXt
Powered by Runestone