Ir ao conteúdo principal

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

Ricardo Machado, Gabriel Guedes, Luiz Manoel

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{:}\)

Demonstração.

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 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\)

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.

Refaça o exercício anterior com as seguintes condições:
  1. A palavra começa com vogal;
  2. A palavra começa e termina com consoante.

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

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

6.

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

7.

(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

8.

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

9.

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.

10.

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

11.

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

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*}
AnteriorTopPróximo