Uma senha de 4 dígitos permite repetição: o código 1111 é válido. Quantas senhas de 4 dígitos existem? \(10^4 = 10{.}000\). Esse é o conceito de arranjo com repetição.
No artigo sobre permutações com repetição, vimos como contar ordenações de um multiconjunto fixo — onde os elementos repetidos já estão dados. Agora o cenário muda: temos \(n\) tipos de elementos disponíveis e \(r\) posições a preencher, podendo usar qualquer tipo em cada posição, quantas vezes quisermos.
Por que arranjos com repetição? #
Contar sequências ordenadas com repetição é uma das operações mais recorrentes em computação e matemática:
- Sistemas de armazenamento digital: o número de valores que \(r\) bits podem representar é \(AR(2, r) = 2^r\) — base do cálculo de capacidade de memória, endereçamento e espaços de estado em hardware.
- Criptografia e senhas: senhas de comprimento \(r\) sobre um alfabeto de \(n\) símbolos (com repetição) totalizam \(n^r\) possibilidades — a fórmula que dimensiona a resistência a ataques de força bruta.
- Bioinformática: sequências de DNA de comprimento \(r\) com as 4 bases (A, T, C, G) formam \(AR(4, r) = 4^r\) sequências — ponto de partida para estimar a diversidade de sequências num genoma.
- Protocolos de rede: endereços IPv4 são sequências de 32 bits — \(AR(2, 32) = 2^{32} \approx 4{,}3\) bilhões de endereços possíveis.
- Sistemas de numeração: a quantidade de padrões representáveis com \(r\) dígitos na base \(b\) é \(AR(b, r) = b^r\), unificando binário, decimal e hexadecimal numa única fórmula.
Da permutação com repetição ao arranjo com repetição #
O diagrama abaixo expande a árvore de decisão dos artigos anteriores, acrescentando o ramo que cobre elementos com repetição e seleção parcial:
flowchart TD
A["n tipos de elementos"] --> B{"Repetição
permitida?"}
B -->|"Não — todos distintos"| C{"Usar todos?"}
C -->|"Sim"| D["Permutação Simples
P_n = n!"]
C -->|"Não — escolher r"| E{"Ordem importa?"}
E -->|"Sim"| F["Arranjo Simples
A(n,r) = n!/(n-r)!"]
E -->|"Não"| G["Combinação Simples
C(n,r) = n!/(r!(n-r)!)"]
B -->|"Sim — com repetição"| H{"Usar todos?"}
H -->|"Sim — multiconjunto fixo"| I["Permutação com Repetição
n!/(n₁!·n₂!·…·nₖ!)"]
H -->|"Não — escolher r posições"| J["Arranjo com Repetição
AR(n,r) = nʳ"]
Arranjo com Repetição #
Um arranjo com repetição de \(n\) elementos tomados \(r\) a \(r\) é uma sequência ordenada de \(r\) elementos em que cada elemento pode ser escolhido mais de uma vez:
$$AR(n, r) = n^r$$Justificativa: cada uma das \(r\) posições tem \(n\) escolhas independentes. Pelo Princípio Multiplicativo: \(\underbrace{n \times n \times \cdots \times n}_{r} = n^r\).
Diferença fundamental: no arranjo simples, \(r \leq n\). No arranjo com repetição, \(r\) pode ser maior que \(n\) — podemos preencher mais posições do que o número de tipos disponíveis, pela repetição.
Leitura por Produto Cartesiano #
Se \(A = \{a_1, \ldots, a_n\}\), os arranjos com repetição de \(n\) elementos tomados \(r\) a \(r\) correspondem aos elementos de:
$$\underbrace{A \times A \times \cdots \times A}_{r \text{ fatores}}$$e portanto há \(|A|^r = n^r\) arranjos. Em Python, itertools.product(A, repeat=r)
gera exatamente esse conjunto.
Exemplos Resolvidos #
Senhas de 2 símbolos entre 8 disponíveis #
Enunciado: Uma fechadura usa símbolos de um alfabeto de 8 caracteres. Quantas senhas de 2 símbolos existem se a repetição é permitida? E sem repetição?
Solução: Com repetição, cada posição tem 8 escolhas independentes:
$$AR(8, 2) = 8^2 = \mathbf{64}$$Isso inclui pares repetidos como (A, A). Sem repetição — arranjo simples — a 2ª posição exclui o símbolo já usado: \(A(8,2) = 8 \times 7 = 56\). A diferença de 8 corresponde exatamente aos 8 pares do tipo (Xᵢ, Xᵢ).
Python: itertools.product para arranjos com repetição
itertools.product para arranjos com repetição
itertools.product(iterable, repeat=r) gera todos os arranjos com repetição
de \(r\) elementos de um iterável — exatamente \(n^r\) tuplas:
from itertools import product, permutations
simbolos = "ABCDEFGH" # 8 símbolos
# AR(8, 2) = 8^2 = 64: todos os pares com repetição permitida
arranjos = list(product(simbolos, repeat=2))
print(len(arranjos)) # 64
print(arranjos[:4]) # [('A', 'A'), ('A', 'B'), ('A', 'C'), ('A', 'D')]
# A(8, 2) = 56: sem repetição
sem_rep = list(permutations(simbolos, 2))
print(len(sem_rep)) # 56A diferença entre product(S, repeat=r) e permutations(S, r) é exatamente
a diferença entre arranjo com e sem repetição: o primeiro permite que o mesmo
símbolo apareça em mais de uma posição; o segundo, não.
Sequências de 3 dígitos de \(\{1,2,3,4,5\}\) #
Enunciado: Quantas sequências de 3 dígitos podem ser formadas com os elementos de \(\{1,2,3,4,5\}\), podendo repetir?
Solução: Como a repetição é permitida, cada posição é preenchida independentemente das demais — a escolha para a 1ª posição não restringe as opções da 2ª nem da 3ª. Pelo Princípio Multiplicativo:
$$AR(5, 3) = \underbrace{5 \times 5 \times 5}_{3\text{ posições}} = 5^3 = \mathbf{125}$$Sequências como (3, 3, 3) ou (1, 5, 1) são válidas — e estão todas contadas.
Placas de veículo (3 letras + 4 dígitos, com repetição) #
Enunciado: Quantas placas de veículo distintas podem ser formadas no formato de 3 letras seguidas de 4 dígitos, com repetição permitida?
Solução: As escolhas de letras e dígitos são independentes entre si. Pelo Princípio Multiplicativo:
$$AR(26, 3) \times AR(10, 4) = 26^3 \times 10^4 = 17{.}576 \times 10{.}000 = \mathbf{175{.}760{.}000}$$Paleta de cores RGB #
Enunciado: Monitores e imagens digitais representam cores como combinações de três canais: vermelho (R), verde (G) e azul (B). No padrão de 8 bits por canal (o chamado true color), cada canal aceita intensidades de 0 a 255 — 256 valores possíveis. Quantas cores distintas podem ser representadas? E num display de 4 bits por canal, onde cada canal vai de 0 a 15?
Solução: Os três canais são escolhidos independentemente; há repetição (dois canais podem ter a mesma intensidade, como R = G = 128 para cinza). Pelo Princípio Multiplicativo:
| Formato | Intensidades por canal | Total de cores |
|---|---|---|
| 8 bits por canal (true color) | 256 (0–255) | \(AR(256, 3) = 256^3 = 16{.}777{.}216\) |
| 4 bits por canal | 16 (0–15) | \(AR(16, 3) = 16^3 = 4{.}096\) |
A diferença entre os dois formatos é enorme: dobrar o número de bits por canal multiplica o número de intensidades por 16 (de 16 para 256) e eleva o total de cores à terceira potência — passando de pouco mais de 4 mil para quase 17 milhões de cores.
Python: enumerando cores e contando com itertools.product
itertools.product
itertools.product(range(n), repeat=3) gera todas as tríades (R, G, B) com
intensidades de 0 a n−1 — exatamente os \(n^3\) arranjos com repetição de
3 posições sobre um alfabeto de \(n\) símbolos:
from itertools import product
# Contagem por fórmula
for bits_por_canal in [4, 8]:
n = 2 ** bits_por_canal # intensidades por canal
total = n ** 3 # AR(n, 3)
print(f"{bits_por_canal} bits/canal: {n} intensidades → {total:,} cores")
# 4 bits/canal: 16 intensidades → 4.096 cores
# 8 bits/canal: 256 intensidades → 16.777.216 cores
# Gerando as primeiras cores de uma paleta de 4 bits (n=16)
paleta_4bits = list(product(range(16), repeat=3))
print(len(paleta_4bits)) # 4096
print(paleta_4bits[:4]) # [(0,0,0), (0,0,1), (0,0,2), (0,0,3)]
# Em CSS, cores são escritas como #RRGGBB em hexadecimal
def para_hex(r, g, b):
return f"#{r:02X}{g:02X}{b:02X}"
print(para_hex(255, 128, 0)) # #FF8000 (laranja)
print(para_hex(0, 0, 0)) # #000000 (preto)Para o formato de 8 bits por canal, materializar a lista completa ocuparia memória considerável (16 milhões de tríades). A fórmula \(256^3\) dá o total em tempo constante — é quando a combinatória substitui a enumeração.
Comparação: Arranjo Simples vs. com Repetição #
A tabela abaixo resume as diferenças essenciais entre os dois tipos de arranjo:
| Tipo | Repetição? | \(r > n\) permitido? | Fórmula |
|---|---|---|---|
| Arranjo simples | Não | Não | \(\dfrac{n!}{(n-r)!}\) |
| Arranjo com repetição | Sim | Sim | \(n^r\) |
Aplicação: Representação Computacional de Números #
Todo sistema de ponto flutuante armazena um número como uma sequência de posições, cada uma preenchida com um símbolo de um alfabeto fixo. Quantos números distintos o sistema pode representar é, portanto, uma contagem de arranjos com repetição — a base do alfabeto elevada ao número de posições.
O que varia entre sistemas é a base usada: computadores modernos usam base 2 (binário), seguindo o padrão IEEE 754; calculadoras científicas das décadas de 1970 e 1980 usavam base 10 (decimal), armazenando cada algarismo diretamente em BCD (Binary Coded Decimal — Decimal Codificado em Binário). A vantagem do BCD é que o número exibido no visor é idêntico ao número armazenado, evitando os erros de conversão decimal ↔ binário que afetam o IEEE 754 (como o famoso \(0{,}1 + 0{,}2 \neq 0{,}3\)). O custo é o espaço: o BCD ocupa mais memória do que o binário puro para a mesma faixa de valores.
Os dois exemplos a seguir ilustram essa diferença.
Para um mergulho completo no padrão IEEE 754 e nos erros de arredondamento em binário, veja o artigo Por dentro do IEEE 754 e o artigo sobre conversão de bases para números reais.
Intel 8087 — ponto flutuante binário de 32 bits:
O coprocessador 8087 (1980) armazena números de 32 bits seguindo o padrão que viria a ser formalizado como IEEE 754. Cada uma das 32 posições é um bit — alfabeto de 2 símbolos (0 ou 1). O número total de padrões distintos é:
$$AR(2, 32) = 2^{32} = 4{.}294{.}967{.}296 \text{ padrões de bits}$$(Nem todos correspondem a números “úteis” — alguns bits codificam o sinal, o expoente e a mantissa, e certos padrões representam valores especiais como infinito e NaN (Not a Number — Não é um Número). O arranjo conta os padrões; a interpretação deles é tarefa do padrão IEEE 754.)
Calculadora HP-11C — ponto flutuante decimal:
A HP-11C (1981) usa BCD: cada posição armazena um algarismo decimal (0–9), não um bit. O formato de armazenamento tem três partes independentes:
| Componente | Posições | Alfabeto | Contagem |
|---|---|---|---|
| Sinal da mantissa e do expoente | 2 (um cada) | \(\{+, -\}\) → 2 símbolos | \(AR(2,2) = 2^2 = 4\) |
| Expoente (característica) | 2 algarismos decimais | \(\{0,\ldots,9\}\) → 10 símbolos | \(AR(10,2) = 10^2 = 100\) |
| Mantissa normalizada | 9 algarismos | 1º \(\in\) 1–9; demais \(\in\) 0–9 | \(9 \times 10^8\) |
A mantissa é normalizada: o 1º algarismo é sempre não nulo (1–9), pois um zero à esquerda seria redundante — o número poderia ser reescrito com um expoente menor. Isso reduz as opções do 1º dígito de 10 para 9, exatamente como na contagem de números de 3 algarismos que excluem os com zero à esquerda.
O total de configurações distintas é:
$$4 \times 10^2 \times 9 \times 10^8 = 36 \times 10^{10} = 3{.}600{.}000{.}000{.}000$$Tabela-Resumo #
| Conceito | Resultado |
|---|---|
| Arranjos com repetição de \(n\) tipos tomados \(r\) a \(r\) | \(AR(n, r) = n^r\) |
| Arranjo simples (sem repetição) | \(A(n,r) = \dfrac{n!}{(n-r)!}\) |
| \(r\) pode exceder \(n\)? | Sim, no arranjo com repetição; não, no simples |
| Produto cartesiano \(A \times \cdots \times A\) (\(r\) fatores) | \( |
Exercícios #
Os exercícios a seguir aplicam a fórmula \(AR(n,r) = n^r\) em diferentes contextos: contagem direta, contagem com restrições de posição e o método do complemento. Estão ordenados do mais simples ao mais complexo.
Exercício 1 — Números de 3 dígitos de \(\{2,3,5,8,9\}\) com repetição
(a) Total. (b) Menores que 800. (c) Múltiplos de 5. (d) Pares. (e) Ímpares.
(a) Sem restrição, cada posição pode ser qualquer dos 5 elementos:
$$AR(5,3) = 5^3 = \mathbf{125}$$(b) Para o número ser menor que 800, o algarismo das centenas deve ser menor que 8. No conjunto \(\{2,3,5,8,9\}\), os elementos menores que 8 são \(\{2,3,5\}\) — 3 opções. As outras duas posições permanecem livres (5 opções cada):
$$3 \times 5 \times 5 = 3 \times 25 = \mathbf{75}$$(c) Um múltiplo de 5 termina em 0 ou 5. Do conjunto \(\{2,3,5,8,9\}\), só o 5 satisfaz essa condição — a unidade fica fixada. As outras duas posições têm 5 opções cada:
$$5 \times 5 \times 1 = \mathbf{25}$$(d) Um número par termina em dígito par. Os pares no conjunto são \(\{2,8\}\) — 2 opções para a unidade. As outras duas posições têm 5 opções cada:
$$5 \times 5 \times 2 = \mathbf{50}$$(e) Por complemento em relação ao total: pares + ímpares = 125. Alternativamente, os ímpares no conjunto são \(\{3,5,9\}\) — 3 opções para a unidade:
$$5 \times 5 \times 3 = \mathbf{75}$$Verificação: \(50 + 75 = 125\) ✓
Exercício 2 — Palavras de 5 letras com A mas não como inicial
Com alfabeto de 26 letras e repetição permitida, quantas palavras de 5 letras contêm A, mas não como letra inicial?
Contar diretamente “tem A em pelo menos uma das posições 2–5” exigiria tratar muitos casos sobrepostos. A estratégia do complemento aninhado é mais limpa:
Defina dois conjuntos:
- \(U\) = palavras sem A na 1ª posição: a 1ª posição tem 25 opções (qualquer letra exceto A); as outras 4 posições aceitam qualquer das 26 letras. Logo \(|U| = 25 \times 26^4\).
- \(B\) = palavras sem A em nenhuma posição: todas as 5 posições têm 25 opções. Logo \(|B| = 25^5\).
Note que \(B \subset U\): toda palavra sem A em parte alguma também não tem A na 1ª posição. A diferença \(|U| - |B|\) dá exatamente as palavras sem A na 1ª posição mas com A em alguma das posições 2–5 — que é o que o enunciado pede:
$$|U| - |B| = 25 \times 26^4 - 25^5 = 25(26^4 - 25^4) = \mathbf{1{.}658{.}775}$$
Exercício 3 — Números de 5 algarismos que contêm o dígito 2
(a) Que contêm o dígito 2. (b) Que não contêm o dígito 2.
Total de números de 5 algarismos: o 1º algarismo não pode ser zero (senão o número teria menos de 5 dígitos), então tem 9 opções (1–9); cada um dos outros 4 algarismos tem 10 opções (0–9):
$$9 \times 10^4 = \mathbf{90{.}000}$$(b) Sem o dígito 2: retiramos o 2 do alfabeto disponível. O 1º algarismo não pode ser 0 nem 2, sobrando \(\{1,3,4,5,6,7,8,9\}\) — 8 opções. Cada um dos outros 4 algarismos pode ser qualquer dígito exceto 2, ou seja, \(\{0,1,3,4,5,6,7,8,9\}\) — 9 opções cada:
$$8 \times 9^4 = 8 \times 6{.}561 = \mathbf{52{.}488}$$(a) Contar diretamente os números com pelo menos um dígito 2 exigiria somar muitos casos sobrepostos. Pelo complemento:
$$90{.}000 - 52{.}488 = \mathbf{37{.}512}$$
Exercício 4 — Anagramas com e sem repetição
Com \(\{a,b,c,d,e\}\), quantos “anagramas” de 3 letras existem: (a) Com letras distintas. (b) Com pelo menos 2 letras iguais.
(a) Com letras distintas, nenhuma posição pode repetir a letra já usada — é um arranjo simples:
$$A(5,3) = 5 \times 4 \times 3 = \mathbf{60}$$(b) Contar diretamente exigiria tratar separadamente “exatamente 2 iguais” e “as 3 iguais”. O complemento é mais direto: \(AR(5,3)\) conta todas as sequências de 3 letras com repetição permitida; \(A(5,3)\) conta exatamente as que têm letras todas distintas. A diferença são as que têm ao menos 2 letras iguais:
$$AR(5,3) - A(5,3) = 125 - 60 = \mathbf{65}$$Próximos passos #
Arranjos com repetição contam sequências ordenadas onde elementos se repetem. A limitação que permanece é a ordem: e quando ela não importa mas a repetição é permitida? Esse cenário — selecionar um subconjunto de \(r\) elementos com reposição entre \(n\) tipos disponíveis, sem levar em conta a sequência — leva às combinações com repetição, tema do próximo artigo da série.
