[skip-to-content]

Seção 1.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 1.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 1.6.2.

O número de permutações com repetições envolvendo \(n\) objetos, dos quais existem \(\beta_1\) objetos iguais a \(b_1\text{,}\) \(\beta_2\) objetos iguais a \(b_2\text{,}\) e assim por diante, até um elemento \(b_k\) que figura \(\beta_k\) vezes, no qual, \(\beta_1+\beta_2+\cdots+\beta_k=n\) é denotado por

\begin{equation*} PR_n^{\beta_1, \beta_2, \ldots, \beta_k}. \end{equation*}
Tecnologia 1.6.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.6.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.5].

Exemplo 1.6.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.6.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.6.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*}

Exercícios 1.6.1 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.

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. 1680
  2. 576
Solução

item a. O total de anagramas da palavra OPERADOR é \(PR_8^2\text{,}\) pois a palavra possui duas letras O, 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}{PR_4^2} = 1680. \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 \(P_4\) 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 P_4 \cdot 2 = 576. \end{equation*}
4.

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

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

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

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

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.6.9. 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*}
13.

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*}
14. (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.6.10.

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