Bancada de combinatória

Calculadora de combinações e permutações

Calcule nCr e nPr, repetições, estrelas e barras, permutações de multiconjuntos, distribuições, inclusão-exclusão, desarranjos e caminhos em grade.

Exemplo resolvido — Bancada de combinatória

Contagem exata	120
Aprox.	120
Dígitos	3
log10	2,0792

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Teoria da contagem — caso a caso

Duas perguntas de sim ou não classificam todo problema de contagem

Escolher (sem repetição) C(n,k) = n! / (k!(n − k)!)

Organizar (sem repetição) P(n,k) = n! / (n − k)!

Ordenado com repetição n^k

Escolher com repetição C(n + k − 1, k)

Escolher (sem repetição)

Fórmula: C(n,k) = n! / (k!(n − k)!)

Exemplo resolvido: Escolher 3 entre 10 pessoas. Como a ordem não importa, C(10,3) = 120 comitês.

Abrir este exemplo: escolha de comitê

Escolher (sem repetição). Seleção sem ordem: as fichas selecionadas formam um conjunto, não uma sequência. Escolher 3 pessoas entre 10: a ordem não importa. — Seleção sem ordem: as fichas selecionadas formam um conjunto, não uma sequência.

Organizar (sem repetição)

Fórmula: P(n,k) = n! / (n − k)!

Exemplo resolvido: Atribuir ouro, prata e bronze entre 10 finalistas. Como os lugares são distintos, P(10,3) = 720 pódios possíveis.

Abrir este exemplo: ordem do pódio

Organizar (sem repetição). Posições ordenadas: trocar posições cria um novo resultado. Pódio dos 3 primeiros entre 10: a ordem importa. — Posições ordenadas: trocar posições cria um novo resultado.

Ordenado com repetição

Fórmula: n^k

Exemplo resolvido: Criar um PIN de 4 dígitos usando 10 dígitos. A ordem importa e os dígitos podem se repetir: 10^4 = 10.000 PINs.

Abrir este exemplo: código PIN

Ordenado com repetição. Cada posição escolhe independentemente do mesmo conjunto. PIN de 4 dígitos: repetição permitida. — Cada posição escolhe independentemente do mesmo conjunto.

Escolher com repetição

Fórmula: C(n + k − 1, k)

Exemplo resolvido: Escolher 3 bolas entre 8 sabores, ignorando a ordem e permitindo repetições. C(10,3) = 120 multiconjuntos de sabores.

Abrir este exemplo: bolas de sorvete

Escolher com repetição. Estrelas e barras: os separadores codificam escolhas repetidas. 3 bolas entre 8 sabores: ordem ignorada, repetições permitidas. — Estrelas e barras: os separadores codificam escolhas repetidas.

Permutação de multiconjunto

Fórmula: N! / (n₁! · n₂! · … · n_r!)

Exemplo resolvido: MISSISSIPPI tem 11 letras: I×4, S×4, P×2 e M×1. Dividindo as trocas idênticas, 11!/(4!4!2!) = 34.650 arranjos.

Abrir este exemplo: MISSISSIPPI

Permutação de multiconjunto. Símbolos repetidos dividem o total de permutações pelas trocas de duplicados. Onze letras, quatro S, quatro I, dois P: 11! sobre 4!·4!·2! = 34.650. Sem as repetições teríamos 39.916.800. Os duplicados removem mais de 99,9% dos arranjos possíveis.. — Símbolos repetidos dividem o total de permutações pelas trocas de duplicados.

Bolas em caixas

Fórmula: Σ_i=0^m (−1)ⁱC(m,i)(m − i)ⁿ

Exemplo resolvido: Distribuir 6 tarefas distintas entre 3 pessoas identificadas, sem deixar ninguém sem tarefa. Inclusão–exclusão dá 3^6 − 3·2^6 + 3 = 540 atribuições.

Abrir este exemplo: distintas em caixas (sobrejetora)

Bolas em caixas. Visão de bolas e caixas para restrições de atribuição/distribuição. Atribuir 6 tarefas distintas a 3 trabalhadores, todos recebem pelo menos uma. — Visão de bolas e caixas para restrições de atribuição/distribuição.

Inclusão-exclusão

Fórmula: C(n,k) − C(b,k)

Exemplo resolvido: Escolher uma mão não ordenada de 5 cartas com pelo menos um Ás. C(52,5) − C(48,5) = 886.656 mãos.

Abrir este exemplo: pelo menos um Ás

Inclusão-exclusão. Representação da sobreposição de conjuntos para a contagem por soma-subtração. Mão de 5 cartas com pelo menos um Ás via contagem por complemento. — Representação da sobreposição de conjuntos para a contagem por soma-subtração.

Casos especiais

Fórmula: !n = n! Σ_i=0ⁿ (−1)ⁱ / i!

Exemplo resolvido: Atribuir 8 nomes no amigo secreto sem ninguém tirar a si mesmo. O número de desarranjos é !8 = 14.833.

Abrir este exemplo: amigo secreto

Casos especiais. Contagens clássicas com restrições: circular, desarranjo e caminhos em grade. Oito pessoas, sem que ninguém tire o próprio nome: 14.833 maneiras. Corresponde a 8! a dividir por e com o resultado arredondado. A contagem de desarranjos é sempre o número inteiro mais próximo de n!/e. O terceiro bloco de análise abaixo provém diretamente deste facto.. — Contagens clássicas com restrições: circular, desarranjo e caminhos em grade.

Referências (1)

The last case in the guide above is Secret Santa, and insight block 3 finds e hiding in it. That is the matching problem, and it is three centuries old: P. Gorroochurn, "Rencontres with Montmort (1708)", chapter 7 of Classic Problems of Probability, 54–61. Wiley, 2012 — the probability that nobody draws their own name tends to 1/e.

Prática

Verifique você mesmo

Preveja primeiro a resposta e depois use os controlos acima para confirmar. Revele a solução só depois de se ter comprometido com um palpite — é isso que torna isto prática.

Escolha 3 pessoas entre 10 para um comité. Depois escolha o 1.º, 2.º e 3.º lugares entre as mesmas 10. Igual n, igual k — os dois contagens diferem e, se sim, por que fator exatamente? Confirme com os dois primeiros modelos.

Mostrar a resposta

120 contra 720, um fator de 6. Uma única pergunta os separa, e não são os números: a ordem importa? Cada comité não ordenado de 3 pode alinhar-se em 3! = 6 pódios diferentes, portanto ordenar é sempre escolher multiplicado por k!. O fator é k! e nunca outra coisa, e é por isso que as duas fórmulas diferem exatamente nessa única divisão.
Um PIN de 4 dígitos retirado de 10 dígitos, e 4 bolas de gelado escolhidas entre 10 sabores em que um sabor pode repetir-se. Ambos permitem repetição. Preveja qual contagem é maior e confirme.

Mostrar a resposta

10,000 contra 715. A repetição é permitida em ambos, logo não é ela que os separa — é a ordem. O PIN é ordenado com repetição, n^k = 10⁴. As bolas são não ordenadas com repetição, C(n + k − 1, k) = C(13,4) = 715. Os dois modelos «com repetição» estão tão afastados como os dois sem ela, e por isso a pergunta «os elementos podem repetir-se?» nunca chega sozinha. São sempre precisas as duas.
Seis prémios distintos em três caixas distintas dão 729. Mude a variante para que cada caixa receba pelo menos um prémio e cai para 540. Para onde foram as 189 distribuições que faltam?

Mostrar a resposta

São exatamente as distribuições que deixam alguma caixa vazia, e contá-las exige uma soma alternada em vez de uma fórmula. A caixa vazia escolhe-se de 3 maneiras e o resto enche-se de 2⁶ = 64 maneiras: 3 × 64 = 192. Mas os 3 casos em que os seis prémios caem numa só caixa foram aí contados duas vezes, portanto subtraia 3. Restam 192 − 3 = 189 distribuições com caixa vazia, e 729 − 189 = 540. É o único modelo da bancada cuja resposta é uma soma alternada: o mais lento a calcular e o mais fácil de errar à mão.

Problemas resolvidos na íntegra

Escolher 3 em 10 e a resposta a escolher 7 5 passos
Escolher 3 em 10 dá 120 maneiras. Deduza-o a partir da contagem ordenada e, em seguida, descubra por que razão 120 é também a resposta para a escolha de 7.
1. Conte primeiro as seleções ordenadas, por serem mais simples: dez escolhas, depois nove, depois oito.
  
  $P (10, 3) = 10 \times 9 \times 8 = 720 = 3! (3 10)$
2. Isso conta cada conjunto de três várias vezes — uma por cada ordem em que os mesmos três poderiam surgir, o que equivale a 3! = 6.
3. Dividir dá 120, e a divisão por k! é toda a diferença entre uma permutação e uma combinação.
  
  $(3 10) = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = \frac{720}{6} = 120$
4. A simetria decorre do próprio significado de escolher. Escolher 3 para levar é o mesmo ato que escolher 7 para deixar, pelo que as duas contagens não podem diferir.
  
  $(3 10) = (7 10) = 120 (choosing 3 is choosing which 7 to omit)$
5. O log₁₀ de 2,0792 no painel é o complemento prático: três dígitos. Para n grandes, a contagem excede tudo o que se pode guardar, e o logaritmo é o que se mantém computável.
  
  $lo g_{10} 120 = 2.0792 ⟹ 3 digits$
Resposta

A ferramenta apresenta 120, 3 dígitos e log₁₀ = 2,0792. Vale a pena interiorizar a simetria porque reduz o trabalho a metade: ninguém deve calcular C(10, 7) do zero. E a linha inteira soma 2¹⁰ = 1024 — todos os subconjuntos de dez elementos, contados por tamanho —, o que é a verificação de sanidade mais rápida que alguma vez fará num cálculo binomial. A maior entrada é C(10, 5) = 252, pelo que o meio da linha contém cerca de um quarto de todos os subconjuntos, enquanto os dois extremos contêm um cada.

$(k n) = \frac{P ( n , k )}{k !} : order costs a factor of k! = 6$
As 2 598 960 maneiras de dar uma mão de cinco cartas para um flush 5 passos
Uma mão de cinco cartas pode ser distribuída de 2.598.960 maneiras. Construa esse valor a partir da distribuição ordenada e use-o depois para avaliar um flush. Trata-se de Escolher (sem repetição) com n = 52 e k = 5.
1. Distribua primeiro por ordem. A primeira carta tem 52 possibilidades, a seguinte 51, e assim sucessivamente até 48 — cinco fatores, ainda sem divisão.
  
  $P (52, 5) = 52 \times 51 \times 50 \times 49 \times 48 = 311875200$
2. Uma mão é um conjunto, e a contagem ordenada registou cada conjunto 120 vezes, uma por cada ordem em que as mesmas cinco cartas poderiam ter saído. Dividir por 5! é o único passo que transforma uma distribuição numa mão.
  
  $(5 52) = \frac{311 875 200}{5 !} = \frac{311 875 200}{120} = 2598960$
3. Conte agora os flushes dentro desse espaço: escolha o naipe de quatro formas e, em seguida, cinco das treze cartas desse naipe.
  
  $flushes = 4 (5 13) = 4 \times 1287 = 5148$
4. O que esclarece o que torna o flush raro. Não é o facto de 5.148 ser um número pequeno de mãos — é o facto de o espaço em que se insere ser quinhentas vezes maior.
  
  $P (flush) = \frac{5148}{2 598 960} = 0.00198 \approx \frac{1}{505}$
5. E esse espaço continua a ser suficientemente pequeno para ter uma dimensão física. Uma mão a cada segundo, sem parar, e todas as mãos distintas terão sido distribuídas no espaço de um mês.
  
  $\frac{2 598 960}{86 400} = 30.1 days, at one hand per second$
Resposta

A ferramenta apresenta 2.598.960, 7 dígitos e log₁₀ = 6,4148. A hierarquia das mãos no poker é esta aritmética e nada mais. Conte as sequências da mesma forma — dez valores iniciais, quatro naipes para cada uma das cinco cartas, 10 × 4⁵ = 10.240 — e existem duas vezes mais sequências do que flushes, que é exatamente por isso que um flush ganha a uma sequência. A ordem não foi concebida; foi contada.

$(5 52) = 2598960 P (flush) \approx \frac{1}{505}$
As 62 990 928 000 formas de uma palavra-passe de oito letras sem letras repetidas 5 passos
Uma palavra-passe de oito letras sem letras repetidas tem 62.990.928.000 formas. Calcule essa contagem, depois conte a mesma palavra-passe sem a regra e decida qual delas preferia estar a defender. Trata-se de Arranjar (sem repetição) com n = 26 e k = 8.
1. Preencha as posições da esquerda para a direita. A primeira aceita qualquer uma das 26 letras; a segunda aceita 25, porque a letra que usou já não está disponível.
  
  $P (26, 8) = \frac{26 !}{18 !} = 26 \times 25 \times 24 \times 23 \times 22 \times 21 \times 20 \times 19$
2. Oito fatores decrescentes, e esse produto é a resposta completa. Trata-se de um arranjo em vez de uma combinação, porque a ordem das letras é a palavra-passe.
  
  $= 62990928000$
3. Agora elimine a regra. Cada posição volta a ser independente e cada posição dispõe de todas as 26 letras, pelo que a contagem é uma simples potência.
  
  $2 6^{8} = 208827064576 (repeats allowed)$
4. A comparação é o essencial: proibir repetições mantém 30,2% das sequências. Uma regra que parece um reforço eliminou sete em cada dez sequências.
  
  $\frac{62 990 928 000}{208 827 064 576} = 0.302$
5. No tempo de um atacante, a mil milhões de tentativas por segundo, os dois espaços correspondem a um minuto e a três minutos e meio. Nenhum serve de defesa — e a regra tornou o mais curto ainda mais curto.
  
  $1 0^{9} guesses/s : 63 s vs 209 s$
Resposta

Com n = 26, k = 8 e o modelo definido para Arranjar (sem repetição), a ferramenta apresenta 62.990.928.000, 11 dígitos e log₁₀ = 10,7993. Cada regra de composição reduz o espaço, sem exceção, porque uma regra só pode proibir. Se ela justifica a sua existência depende de algo que esta aritmética não consegue ver: se as sequências que proíbe são aquelas que as pessoas escolhem com muito mais frequência do que ao acaso. Proibir uma palavra-passe notória custa uma sequência. Proibir todas as letras repetidas custa 145.836.136.576 delas.

$P (26, 8) = 0.302 \times 2 6^{8} : forbidding repeats deletes 69.8% of the strings$
Três tentativas num multibanco para um PIN de quatro dígitos 5 passos
Um PIN de quatro dígitos tem 10.000 valores. Calcule quanto valem três tentativas num caixa automático e quanto custa realmente o conselho habitual de evitar dígitos repetidos. Trata-se de Ordenado com repetição com n = 10 e k = 4.
1. Quatro posições, dez dígitos em cada uma, e nada as liga — o dígito que acabou de utilizar continua disponível para a posição seguinte.
  
  $10 \times 10 \times 10 \times 10 = 1 0^{4} = 10000$
2. Três tentativas contra um PIN escolhido de forma uniforme equivalem, portanto, a três hipóteses em dez mil. O limite de três tentativas não é uma melhoria relativamente a palpites ilimitados; contra este espaço, é toda a defesa.
  
  $3 attempts : \frac{3}{10 000} = 0.03%$
3. Aplique agora a regra de não repetição de dígitos: dez escolhas, depois nove, depois oito, depois sete.
  
  $no repeated digit : 10 \times 9 \times 8 \times 7 = 5040$
4. A regra mantém 5.040 PINs e destrói 4.960. Metade do espaço desaparece — e a metade eliminada incluía o 1111 juntamente com tudo o resto.
  
  $\frac{5040}{10 000} = 0.504$
5. Dois dígitos adicionais não são dois palpites adicionais. Cada dígito multiplica por dez, pelo que um PIN de seis dígitos representa um espaço cem vezes maior.
  
  $six digits : 1 0^{6} = 1000000 = 100 \times 1 0^{4}$
Resposta

A ferramenta apresenta 10.000 para n = 10, k = 4. Ambos os factos se confirmam em simultâneo: o espaço é minúsculo e um PIN é normalmente suficiente de qualquer forma — porque o limite de três tentativas concede ao atacante 0,03% do espaço em vez da totalidade. Mude a ameaça e a resposta inverte-se. Um ficheiro roubado de PINs não tem limite de tentativas, e dez mil candidatos são trabalho para uma fração de segundo, razão pela qual a segurança de um PIN nunca assenta no próprio PIN.

$n^{k} = 1 0^{4} = 1000010 \times 9 \times 8 \times 7 = 5040$
Três bolas de oito sabores e três pessoas entre dez 5 passos
Três bolas de entre oito sabores, com repetição permitida, dá 120 — o mesmo número que escolher três pessoas de entre dez. Mostre que tal não é uma coincidência. Isto é Escolha com repetição com n = 8 e k = 3.
1. Escreva o pedido como uma fila de símbolos: uma estrela para cada bola, uma barra para cada passagem ao sabor seguinte. Três bolas de entre oito sabores necessitam de três estrelas e sete barras.
  
  $3 scoops ⋆ ⋆ ⋆ and 7 bars ∣ ∣ ∣ ∣ ∣ ∣ ∣$
2. Cada disposição desses dez símbolos é um pedido, e cada pedido é uma disposição. Por isso, a questão passa a ser apenas saber quais 3 das 10 posições contêm estrelas — o que é a pergunta do problema 1 com substantivos diferentes.
  
  $(3 3 + 7) = (3 10) = 120$
3. Proíba as repetições e a contagem desce para 56. A permissão para repetir um sabor vale 64 pedidos adicionais, mais do que duplicando o menu.
  
  $(3 8) = 56 (no repeats allowed)$
4. Agora faça com que a ordem também importe, de modo que baunilha-baunilha-menta difira de menta-baunilha-baunilha: oito escolhas independentes, três vezes seguidas.
  
  $8^{3} = 512 (ordered, repeats allowed)$
5. A razão entre esses dois valores é 4,27, e não 3! = 6. Um cone com uma bola repetida tem menos ordenações distintas do que um com três bolas diferentes, pelo que dividir por 3! é precisamente o passo que não pode dar aqui.
  
  $\frac{512}{120} = 4.27 \neq = 3! = 6$
Resposta

A ferramenta apresenta 120, 3 dígitos e log₁₀ = 2,0792 — a mesma leitura do problema 1, a partir de uma pergunta diferente. O método das estrelas e barras é uma tradução e não uma fórmula: transforma a repetição em posição, onde já sabe o que fazer. A armadilha que arma é o passo 5. Assim que as repetições são permitidas, as ordenações deixam de ser intercambiáveis e nenhum fator único faz a conversão entre a contagem ordenada e a não ordenada.

$(k n + k - 1) : k stars, n - 1 bars$
As 34 650 palavras distintas de MISSISSIPPI com quatro S a evitarem-se 5 passos
As letras de MISSISSIPPI formam 34 650 palavras distintas. Deduza o resultado e, em seguida, responda a uma pergunta mais difícil para a qual a ferramenta não tem campo: com que frequência os quatro S evitam ficar juntos? Isto é Permutação de multiconjunto com contagens 1, 4, 4, 2.
1. Comece por fingir que todas as letras são distinguíveis — identifique os S de S₁ a S₄. É então uma simples permutação de onze objetos.
  
  $11! = 39916800$
2. Agora remova os rótulos. Os quatro S podem ser permutados de 4! maneiras sem alterar o que está escrito, sucedendo o mesmo com os quatro I e os dois P, pelo que cada palavra visível foi contada 1 152 vezes.
  
  $\frac{11 !}{1 ! 4 ! 4 ! 2 !} = \frac{39 916 800}{1152} = 34650$
3. O que dá diretamente uma probabilidade: baralhe as onze peças e uma disposição em 34 650 escreve o nome do estado.
  
  $P (a shuffle spells MISSISSIPPI) = \frac{1}{34 650} = 0.0000289$
4. Para a pergunta mais difícil, posicione primeiro as outras sete letras — M, quatro I, dois P — e conte as suas disposições. Isso deixa oito intervalos, incluindo as duas extremidades, e cada S tem de ocupar um intervalo diferente.
  
  $\frac{7 !}{1 ! 4 ! 2 !} = 105, (4 8) = 70$
5. Multiplique e divida: 7 350 das 34 650 palavras mantêm os S separados, o que equivale a 21,2%.
  
  $\frac{105 \times 70}{34 650} = \frac{7350}{34 650} = 0.2121 = \frac{7}{33}$
Resposta

A ferramenta apresenta 34 650, 5 dígitos e log₁₀ = 4,5397. O método dos intervalos nos passos 4 e 5 vale mais do que a resposta em si. É o procedimento geral para qualquer condição do tipo sem dois destes juntos: coloque os elementos não restringidos primeiro e depois escolha intervalos para os elementos restringidos. A adjacência é uma condição que nenhum fatorial consegue expressar, e os intervalos convertem-na numa escolha de posições — que é a única coisa que todas as fórmulas nesta página já sabem contar.

$\frac{n !}{n _{1} ! n _{2} ! \dots} : divide by the orderings you cannot see$
Seis tarefas distintas entregues a três trabalhadores sem ninguém ficar inativo 5 passos
Seis tarefas distintas atribuídas a três trabalhadores sem que ninguém fique inativo dá 540 atribuições. Deduza o resultado removendo os casos maus em vez de contar os bons. Isto é Bolas em caixas, objetos distintos, todas as caixas usadas, com n = 6 e m = 3.
1. Ignore a exigência no início. Cada tarefa escolhe independentemente um de três trabalhadores, pelo que a contagem sem restrições é uma potência — e é muito mais fácil do que a contagem com restrições.
  
  $3^{6} = 729 (no restriction)$
2. Agora subtraia as atribuições que deixam alguém sem nada: escolha o trabalhador inativo de três maneiras e, em seguida, dê todas as seis tarefas aos outros dois.
  
  $one worker idle : (1 3) 2^{6} = 3 \times 64 = 192$
3. Essa subtração foi longe demais. Uma atribuição que utilize apenas um trabalhador foi subtraída duas vezes, uma por cada colega que deixou inativo, pelo que essas três regressam.
  
  $two idle, added back : (2 3) 1^{6} = 3$
4. A alternância de subtração e adição é a inclusão-exclusão, e a soma alternada é o que a linha da fórmula da ferramenta mostra.
  
  $729 - 192 + 3 = 540$
5. Assim, três quartos de todas as atribuições acabam por utilizar toda a gente. Divida por 3! para tornar os trabalhadores intercambiáveis e obtém S(6, 3) = 90, o número de Stirling de segundo tipo — as mesmas partições, contadas sem nomes.
  
  $\frac{540}{729} = 0.7407, S (6, 3) = \frac{540}{3 !} = 90$
Resposta

A ferramenta apresenta 540, 3 dígitos e log₁₀ = 2,7324. O passo 3 é onde este problema é habitualmente perdido. O instinto dita que subtrair os casos maus é o método, mas não é: a subtração sobre conjuntos sobrepostos ultrapassa sempre a marca, e os termos de correção não são decorativos. O 90 no passo 5 é o mesmo objeto sob outro ângulo — com trabalhadores nomeados há 540 atribuições, sem nomes 90 partições, e a diferença entre eles é exatamente as 3! maneiras de atribuir os nomes.

$i = 0 \sum m (- 1)^{i} (i m) (m - i)^{n} = 540 = 3! S (6, 3)$
Doze fichas idênticas em quatro caixas rotuladas sem nenhuma vazia 5 passos
Doze fichas idênticas em quatro caixas rotuladas sem nenhuma vazia é 165. Chegue lá pagando a restrição à partida. Este é o problema Bolas em caixas, objetos idênticos, nenhuma caixa vazia, com n = 12 e m = 4.
1. A exigência é que cada caixa receba pelo menos uma, por isso satisfaça-a imediatamente: coloque uma ficha em cada caixa e não pense mais nisso. Restam oito fichas e agora não há qualquer regra.
  
  $pay the floor first : 12 - 4 = 8 units still free$
2. Distribuir itens idênticos livremente é o método das estrelas e barras — oito estrelas, três barras para separar quatro caixas — e a contagem é a escolha de que posições as barras ocupam.
  
  $(4 - 1 8 + 4 - 1) = (3 11) = 165$
3. Abandone a regra de não haver caixas vazias e o mesmo método dá 455, porque todas as doze fichas ficam livres.
  
  $without the floor : (3 12 + 4 - 1) = (3 15) = 455$
4. Assim, o mínimo de uma por caixa custa quase dois terços das distribuições: 165 das 455 sobrevivem-lhe.
  
  $\frac{165}{455} = 0.363$
5. Se as fichas forem distinguíveis, a contagem salta para 16.777.216. A identidade é cara — cinco ordens de grandeza, para doze objetos.
  
  $distinct units instead : 4^{12} = 16777216$
Resposta

A ferramenta apresenta 165, 3 dígitos e log₁₀ = 2,2175. O Passo 1 é o passo generalizável: um limite inferior para cada parte pode ser pago antecipadamente, porque pagá-lo deixa um problema com a mesma estrutura e um n menor. Eleve o mínimo para três em cada uma e resta doze menos doze, pelo que a resposta é um. Não funciona no sentido inverso, e essa assimetria é toda a razão pela qual no máximo duas por caixa é uma questão mais difícil do que pelo menos uma.

$(m - 1 n - 1) : a floor of one is a constant, not a new formula$
As 886 656 mãos de cinco cartas que contêm pelo menos um ás 5 passos
886.656 mãos de cinco cartas contêm pelo menos um ás. Conte as mãos que não contêm e subtraia — depois reconstrua o mesmo número pelo caminho longo como verificação. Este é o problema de Inclusão-Exclusão, pelo menos um, com n = 52, k = 5 e 48 cartas que não são ases.
1. Contar diretamente as mãos com pelo menos um ás significa dividir em um, dois, três e quatro ases. Contar o complemento é um único cálculo, por isso comece por aí.
  
  $(5 52) = 2598960$
2. Uma mão sem nenhum ás é constituída por cinco cartas retiradas das 48 que não são ases.
  
  $(5 48) = 1712304 (not one ace)$
3. Subtraia, e todas as mãos restantes contêm um ás — porque uma mão ou não tem nenhum ou tem algum, sem nada pelo meio.
  
  $2598960 - 1712304 = 886656$
4. Assim, um terço de todas as mãos tem pelo menos um ás, o que é muito mais do que a frase quatro ases em cinquenta e duas cartas sugere.
  
  $P = \frac{886 656}{2 598 960} = 0.3412$
5. Agora a verificação. Conte exatamente um ás, exatamente dois, exatamente três e exatamente quatro, e depois some. Quatro cálculos separados, e o total coincide até ao último dígito.
  
  $4 (4 48) + 6 (3 48) + 4 (2 48) + (1 48) = 778320 + 103776 + 4512 + 48 = 886656$
Resposta

A ferramenta apresenta 886.656, 6 dígitos e log₁₀ = 5,9478. O Passo 5 não é decorativo. Pelo menos um é a expressão mais frequentemente calculada como 4 × C(48, 4) = 778.320 — escolhe-se um ás, depois preenche-se à volta — e esse número está errado porque uma mão com dois ases é produzida duas vezes pela receita, uma a partir de cada um dos seus ases. O complemento nunca pode cometer esse erro, razão pela qual é o primeiro recurso sempre que uma pergunta diz pelo menos um.

$∣ A ∣ = N - ∣ A^{c} ∣ : count the easy side and subtract$
Quarenta, trinta e cinco e vinte e oito membros em três clubes 5 passos
Quarenta, trinta e cinco e vinte e oito membros em três clubes não são 103 pessoas. Encontre o número real de pessoas e, em seguida, divida-o entre quem pertence a um clube, a dois ou aos três. Este é o problema de Inclusão-Exclusão, união de três conjuntos, com sobreposições aos pares de 12, 10 e 9 e uma sobreposição tripla de 4.
1. Somando as três listas, qualquer pessoa em dois clubes foi contada duas vezes e qualquer pessoa nos três foi contada três vezes, pelo que 103 é um limite superior e nada mais.
  
  $40 + 35 + 28 = 103$
2. Subtraia cada sobreposição aos pares. Alguém em exatamente dois clubes está agora contado corretamente — mas alguém nos três clubes foi contado três vezes e subtraído três vezes, pelo que desapareceu completamente.
  
  $103 - (12 + 10 + 9) = 103 - 31 = 72$
3. Adicione novamente a sobreposição tripla para os restaurar. Isso é a totalidade da inclusão-exclusão para três conjuntos: somar os simples, subtrair os pares, somar o triplo.
  
  $72 + ∣ A \cap B \cap C ∣ = 72 + 4 = 76$
4. A união não diz como essas 76 pessoas estão distribuídas, mas os mesmos três dados de entrada também respondem a isso. Pondere os pares por dois e o triplo por três para eliminar todos os que têm mais de uma afiliação.
  
  $exactly one = 103 - 2 (31) + 3 (4) = 53$
5. O resto segue-se: 19 pessoas pertencem a exatamente dois clubes, e os três grupos voltam a somar 76.
  
  $exactly two = 31 - 3 (4) = 19, 53 + 19 + 4 = 76$
Resposta

A ferramenta apresenta 76, 2 dígitos e log₁₀ = 1,8808. Os sinais alternados são uma correção e não uma regra mnemónica: cada termo corrige o excesso do anterior, e alterna porque cada correção excede no sentido oposto. É também por isso que a fórmula cresce tão rapidamente — quatro conjuntos precisam de quinze termos, e n conjuntos precisam de 2ⁿ − 1. Muito antes de isso ser prático, o complemento no problema 9 é o instrumento preferível.

$∣ A \cup B \cup C ∣ = Σ_{1} - Σ_{2} + Σ_{3} = 76$
Oito pessoas a tirar nomes para o Amigo Secreto sem ninguém ficar com o próprio nome 5 passos
Oito pessoas tiram nomes no Amigo Secreto e 14 833 das 40 320 extrações possíveis deixam todos sem o seu próprio nome. Deduza essa contagem e, em seguida, pergunte quantas pessoas habitualmente tiram o seu próprio nome. Isto é Casos especiais, desarranjo, com n = 8.
1. Um desarranjo é uma permutação sem ponto fixo. A inclusão-exclusão sobre os oito eventos esta pessoa tirou o seu próprio nome origina uma soma alternada.
  
  $! n = n! i = 0 \sum n \frac{( - 1 ) ^{i}}{i !}$
2. Essa soma corresponde aos primeiros nove termos da série de e⁻¹, e tudo o que ela omite é inferior a 1/9! = 2,8 × 10⁻⁶.
  
  $8! = 40320, i = 0 \sum 8 \frac{( - 1 ) ^{i}}{i !} = 0.367882$
3. Efetue os cálculos e arredonde: 14 833 extrações nas quais ninguém fica com o seu próprio nome.
  
  $! 8 = 40320 \times 0.367882 = 14833$
4. Em fração, isto é 0,36788, face a e⁻¹ = 0,367879 — uma concordância até às cinco casas decimais, para oito pessoas, que quase não se altera em grupos maiores.
  
  $P = \frac{14 833}{40 320} = 0.36788 \approx e^{- 1} = 0.367879$
5. Agora uma questão diferente, e mais simples. Cada pessoa tira o seu próprio nome com probabilidade 1/n, e os valores esperados somam-se quer os eventos sejam independentes quer não, pelo que o número esperado de auto-extrações é exatamente 1 — para oito pessoas, e para oitocentas.
  
  $E [self-draws] = i = 1 \sum n \frac{1}{n} = n \times \frac{1}{n} = 1$
Resposta

A ferramenta apresenta 14 833, 5 dígitos e log₁₀ = 4,1712. O passo 5 explica o passo 4. Se o número médio de auto-extrações é 1 independentemente do tamanho do grupo, a probabilidade de não obter nenhuma também não pode depender muito do tamanho do grupo — e para uma contagem de eventos raros com média 1, essa probabilidade é e⁻¹. A constante não é aqui uma curiosidade. É a resposta a qual é a probabilidade de zero quando a média é um, uma questão que surge constantemente fora da combinatória.

$\frac{! n}{n !} \to e^{- 1}, E [self-draws] = 1 for every n$
Rotas mais curtas através de uma grelha 7 × 5 com uma célula bloqueada 5 passos
442 caminhos mais curtos atravessam uma grelha 7 × 5 quando uma célula está bloqueada. Conte todos os caminhos, conte os que passam pela célula bloqueada e subtraia. Em seguida, encontre a célula que causaria mais impacto. Isto é Casos especiais, caminho numa grelha, com 7 passos para este, 5 passos para norte e o bloqueio em (3, 2).
1. Cada caminho mais curto tem doze passos de comprimento, sete dos quais para este e cinco para norte, numa determinada ordem. Assim, um caminho não é mais do que uma escolha de quais os passos que são para este.
  
  $(7 7 + 5) = (7 12) = 792$
2. Um caminho que passa pela célula bloqueada é composto por dois caminhos independentes colados nessa célula: do canto à célula, e da célula ao canto oposto. Multiplique, porque cada primeira metade se combina com cada segunda metade.
  
  $through (3, 2) : (3 5) (4 7) = 10 \times 35 = 350$
3. Subtraia, e o que resta são exatamente os caminhos que evitam a célula.
  
  $792 - 350 = 442$
4. Essa única célula transportava 44% de todo o tráfego — um bloqueio elimina quase metade dos caminhos.
  
  $\frac{350}{792} = 0.442$
5. Mas não é a pior célula para perder. A célula a um passo para este a partir do início transporta 462 caminhos, 58% deles, porque todos os caminhos que começam com um passo para este têm de passar por ela.
  
  $through (1, 0) : (1 1) (6 11) = 462 = 0.583 of all paths$
Resposta

A ferramenta apresenta 442, 3 dígitos e log₁₀ = 2,6454. O passo 5 contraria a intuição visual. A célula bloqueada parece causar mais danos perto do meio, onde os caminhos parecem agrupar-se; a aritmética mostra que as células perto de um canto transportam mais, porque a contagem através de uma célula é o produto de dois coeficientes binomiais e, perto de um canto, um deles cobre quase toda a grelha. Contar caminhos através de cada nó, em vez de olhar para o mapa, é também como se mede a redundância numa rede real.

$(a a + b) - (x x + y) (a - x ( a - x ) + ( b - y )) = 442$

Pela equipa 42Math · Atualizado 2026-08-17

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Estatística e Finanças →

Problemas de exemplo

escolha de comitê - Escolher 3 pessoas entre 10: a ordem não importa
mão de 5 cartas - Uma mão de poker resulta em 2.598.960 combinações. A ferramenta imprime a grandeza desse número ao lado: 7 algarismos, log₁₀ 6,4148. Depois, recusa-se a listá-las por o espaço de resultados ser demasiado vasto para enumeração. Essa recusa resume a questão. A fórmula entrega a contagem sem nunca construir o conjunto.
aposta de loteria - Seis números entre quarenta e nove, ignorando a ordem: 13.983.816 apostas. Comprar uma por semana demoraria um quarto de milhão de anos até cobrir todas. Eis a forma honesta de interpretar as probabilidades.
ordem do pódio - Pódio dos 3 primeiros entre 10: a ordem importa
senha com caracteres distintos - Oito letras sem repetições geram 62.990.928.000 combinações. Sessenta e três mil milhões resultantes de apenas vinte e seis símbolos. Proibir repetições tem aqui um custo surpreendentemente baixo, porque oito é pequeno em relação a vinte e seis.
organizar todos - Ordenar todos os oito. Aqui k é igual a n e a resposta é simplesmente 8! = 40.320. A fórmula geral das permutações reduz-se a um fatorial de forma exata quando ninguém fica de fora.
código PIN - PIN de 4 dígitos: repetição permitida
código de produto - Seis caracteres de trinta e seis letras e algarismos, permitindo repetições: 2.176.782.336. São dois mil milhões de códigos a partir de uma etiqueta de seis caracteres. É exatamente por isto que os números de série são curtos.
bolas de sorvete - 3 bolas entre 8 sabores: ordem ignorada, repetições permitidas
bolas idênticas - Doze bolas idênticas para cinco caixas distinguíveis é um problema de estrelas e barras: C(16, 4) = 1.820. Os elementos idênticos tornam a contagem menor, não maior. A troca de duas bolas entre si nada altera.
BALLOON - A palavra BALLOON tem sete letras, incluindo dois L e dois O. Fica 7! sobre 2!·2! = 1.260 em vez de 5.040. Cada par repetido divide o total a meio.
MISSISSIPPI - Onze letras, quatro S, quatro I, dois P: 11! sobre 4!·4!·2! = 34.650. Sem as repetições teríamos 39.916.800. Os duplicados removem mais de 99,9% dos arranjos possíveis.
distintas em caixas (qualquer) - Seis tarefas distintas para três trabalhadores sem qualquer restrição. A atribuição de cada tarefa é independente, logo 3⁶ = 729. Este é o cenário fácil. A verdadeira complexidade surge no caso seguinte, onde todos recebem pelo menos uma.
distintas em caixas (sobrejetora) - Atribuir 6 tarefas distintas a 3 trabalhadores, todos recebem pelo menos uma
idênticas em caixas (qualquer) - Doze elementos idênticos em quatro caixas, permitindo caixas vazias: C(15, 3) = 455. Compare o resultado com a versão de elementos distintos acima. Tornar os itens idênticos constitui a maior redução isolada em toda a combinatória.
idênticas em caixas (não vazias) - Os mesmos doze elementos em quatro caixas, sem deixar nenhuma vazia: C(11, 3) = 165. Atribui-se primeiro um elemento a cada caixa. Depois, distribuem-se os oito restantes livremente. É exatamente por isto que a mesma fórmula funciona com números mais pequenos.
pelo menos um Ás - Mão de 5 cartas com pelo menos um Ás via contagem por complemento
união de três conjuntos - Três clubes de 40, 35 e 28 com membros em comum totalizam 76 pessoas, e não 103. Subtrai-se cada par uma vez e volta-se a adicionar o trio. As pessoas que pertencem aos três clubes foram removidas uma vez a mais.
mesa redonda - Sentar 7 pessoas em uma mesa redonda: rotações são equivalentes
amigo secreto - Oito pessoas, sem que ninguém tire o próprio nome: 14.833 maneiras. Corresponde a 8! a dividir por e com o resultado arredondado. A contagem de desarranjos é sempre o número inteiro mais próximo de n!/e. O terceiro bloco de análise abaixo provém diretamente deste facto.
caminho em grade - Caminhos mais curtos numa grelha com um quadrado bloqueado. O processo passa por contar cada trajeto e subtrair os que atravessam a quadrícula bloqueada. É a totalidade do princípio da inclusão-exclusão na sua forma mais elementar.