Contagem com Restrições em Análise Combinatória: Regras, Posições e Complemento

O que muda quando há restrições

Em muitos problemas de contagem, não basta “aplicar uma fórmula”: existe uma condição que proíbe certas configurações (sem repetição, sem adjacências, com posições fixas, com pelo menos um elemento de um tipo etc.). A estratégia é transformar a restrição em um plano de contagem organizado, escolhendo uma destas abordagens (ou combinando mais de uma):

• Contagem direta por casos: dividir em situações mutuamente exclusivas e somar.
• Método do complemento: contar o total sem restrição e subtrair o que é proibido.
• Fixação de posições: reservar posições para certos elementos e contar o restante.
• Construção por blocos: quando elementos devem ficar juntos, tratá-los como uma “unidade”.

Como organizar uma solução (roteiro)

• 1) Declare o universo: o que seria contado sem restrição? (tamanho do conjunto de possibilidades).
• 2) Traduza a restrição em linguagem de contagem: “não pode repetir”, “não pode ser adjacente”, “tem que estar na posição i”, “pelo menos um” etc.
• 3) Escolha a estratégia: casos, complemento, posições, blocos (ou combinação).
• 4) Defina variáveis e casos: descreva cada caso com clareza (ex.: quantidade de letras, quantidade de dígitos, posição do elemento).
• 5) Garanta exclusividade: casos não podem se sobrepor.
• 6) Garanta cobertura: a união dos casos deve ser exatamente o universo permitido.

Contagem direta por casos (somar situações)

Use quando a restrição naturalmente cria categorias: “exatamente dois”, “no máximo k”, “começa com vogal ou consoante”, “tem 0, 1 ou 2 repetições” etc. A soma funciona porque os casos são disjuntos.

Exemplo 1: seleção com condições (pelo menos um / exatamente dois / no máximo k)

Uma turma tem 5 alunos do grupo A e 7 do grupo B. Quantas comissões de 4 pessoas podem ser formadas com:

• (a) pelo menos 1 do grupo A
• (b) exatamente 2 do grupo A
• (c) no máximo 2 do grupo A

(b) Exatamente 2 do grupo A (caso único):

• Escolher 2 de A: C(5,2)
• Escolher 2 de B: C(7,2)
• Total: C(5,2)·C(7,2)

(c) No máximo 2 do grupo A (casos disjuntos: 0, 1 ou 2 de A):

Continue em nosso aplicativo e ...

• Ouça o áudio com a tela desligada
• Ganhe Certificado após a conclusão
• + de 5000 cursos para você explorar!

ou continue lendo abaixo...

Baixar o aplicativo

• 0 de A e 4 de B: C(5,0)·C(7,4)
• 1 de A e 3 de B: C(5,1)·C(7,3)
• 2 de A e 2 de B: C(5,2)·C(7,2)
• Total: C(5,0)·C(7,4)+C(5,1)·C(7,3)+C(5,2)·C(7,2)

(a) Pelo menos 1 do grupo A pode ser por casos (1,2,3,4 de A) ou por complemento (ver seção de complemento). Por casos:

• 1 de A e 3 de B: C(5,1)·C(7,3)
• 2 de A e 2 de B: C(5,2)·C(7,2)
• 3 de A e 1 de B: C(5,3)·C(7,1)
• 4 de A e 0 de B: C(5,4)·C(7,0)
• Total: soma dos quatro termos

Método do complemento (total − proibido)

É especialmente eficiente quando “o proibido” é mais simples de contar do que “o permitido”. A estrutura é:

• Total sem restrição
• Menos (casos que violam a regra)

Exemplo 2: comissão com pelo menos um (complemento)

Retomando a comissão de 4 pessoas (5 de A, 7 de B): contar com pelo menos 1 de A.

• Total de comissões de 4 dentre 12: C(12,4)
• Proibido: nenhuma pessoa de A (ou seja, 4 de B): C(7,4)
• Permitido: C(12,4) − C(7,4)

Observe como o complemento evita somar vários casos quando a restrição é “pelo menos um”.

Exemplo 3: senhas sem repetição (com restrição de repetição)

Considere senhas de 6 caracteres formadas por dígitos (0–9) e letras maiúsculas (26), totalizando 36 símbolos. Quantas senhas têm todos os caracteres distintos?

Passo a passo (contagem direta por posições):

• 1ª posição: 36 opções
• 2ª posição: 35 (não pode repetir a anterior)
• 3ª posição: 34
• …
• 6ª posição: 31

Total: 36·35·34·33·32·31.

Se a pergunta fosse “quantas têm pelo menos uma repetição?”, o complemento seria natural:

• Total sem restrição: 36^6
• Sem repetição: 36·35·34·33·32·31
• Com repetição (pelo menos uma): 36^6 − 36·35·34·33·32·31

Fixação de posições (posições específicas e restrições de lugar)

Quando certos elementos precisam ocupar posições determinadas (ou proibidas), a ideia é “travar” essas posições e contar o restante. Isso reduz o problema a preencher lacunas.

Exemplo 4: permutações com elementos em posições específicas

Quantas permutações dos 8 símbolos {A,B,C,D,E,F,G,H} satisfazem: A na 1ª posição e B na 8ª posição?

Passo a passo:

• Fixe A na posição 1 e B na posição 8 (não há escolha nessas posições).
• Restam 6 símbolos para preencher 6 posições livres.
• Total: 6!

Exemplo 5: posição proibida (derivando casos simples)

Quantas permutações de {1,2,3,4,5} têm o número 1 em uma posição par?

Passo a passo:

• Posições pares disponíveis: 2 e 4 (2 escolhas).
• Escolha a posição do 1: 2 maneiras.
• Permute os outros 4 números nas 4 posições restantes: 4! maneiras.
• Total: 2·4!

Note que aqui a restrição vira uma escolha inicial (posição do elemento) seguida de preenchimento livre.

Construção por blocos (elementos juntos)

Quando a restrição exige que certos elementos fiquem adjacentes, trate o conjunto como um “bloco” temporário. Depois, ajuste pela ordem interna do bloco.

Exemplo 6: dois elementos devem ficar juntos

Quantas permutações de {A,B,C,D,E,F} têm A e B juntos (em qualquer ordem)?

Passo a passo:

• Forme o bloco (AB) (ainda sem decidir a ordem interna).
• Agora há 5 unidades para permutar: o bloco + C, D, E, F.
• Permutações das 5 unidades: 5!
• Ordem interna do bloco: 2 (AB ou BA).
• Total: 2·5!

Exemplo 7: três elementos juntos (com ordem interna)

Quantas permutações de {A,B,C,D,E,F,G} têm A, B e C consecutivos (em qualquer ordem)?

• Bloco (ABC) + D, E, F, G: total de 5 unidades.
• Arranjos das unidades: 5!
• Ordem interna do bloco: 3!
• Total: 5!·3!

Adjacências proibidas (evitar vizinhança)

Restrições do tipo “X não pode ficar ao lado de Y” podem ser tratadas por:

• Complemento: total − (casos em que ficam juntos).
• Construção com lacunas: posicionar um grupo e inserir o outro em espaços permitidos (muito útil quando há vários elementos iguais ou muitos proibidos).

Exemplo 8: evitar adjacência usando complemento

Quantas permutações de {A,B,C,D,E,F} têm A e B não adjacentes?

Passo a passo:

• Total de permutações: 6!
• Conte as permutações com A e B juntos (bloco): 2·5!
• Não adjacentes: 6! − 2·5!

Exemplo 9: sequência binária sem adjacência proibida (lacunas)

Quantas sequências de comprimento 7 com símbolos 0 e 1 têm exatamente 3 uns e nenhum par de uns consecutivos?

Passo a passo (lacunas):

• Para evitar adjacência, coloque primeiro os zeros. Se há 3 uns, então há 4 zeros (porque o comprimento é 7).
• Escreva os 4 zeros: 0 0 0 0. Isso cria 5 lacunas onde uns podem ser inseridos (antes do primeiro zero, entre zeros, e após o último): _ 0 _ 0 _ 0 _ 0 _.
• Para não haver uns consecutivos, cada lacuna pode receber no máximo 1 um.
• Escolha 3 lacunas dentre 5 para colocar os uns: C(5,3).

Total: C(5,3).

Combinando técnicas: casos + posições + complemento

Problemas reais frequentemente pedem uma combinação. O segredo é manter a estrutura: definir universo, definir casos disjuntos, e checar cobertura.

Exemplo 10: senha com condição “exatamente dois dígitos” e sem repetição

Senhas de 5 caracteres usando letras maiúsculas (26) e dígitos (10). Exigir: exatamente 2 dígitos e nenhum caractere se repete. Quantas senhas existem?

Passo a passo:

• 1) Escolha as posições dos 2 dígitos entre 5: C(5,2).
• 2) Preencha as 2 posições de dígitos sem repetição: 10·9.
• 3) Preencha as 3 posições de letras sem repetição: 26·25·24.
• 4) Multiplique (decisões independentes após fixar posições): C(5,2)·(10·9)·(26·25·24).

Os casos aqui são implícitos: a escolha das posições garante “exatamente 2 dígitos”; não há sobreposição entre escolhas diferentes de posições, e toda senha válida tem um único conjunto de posições de dígitos, garantindo cobertura.

Checklist de verificação (para evitar erros comuns)

• Casos realmente disjuntos? Se uma configuração puder cair em dois casos, você vai contar em dobro.
• Casos cobrem tudo? Se faltar um caso possível, você subconta.
• Complemento bem definido? O “proibido” deve ser exatamente o conjunto que viola a regra, nem maior nem menor.
• Blocos com ordem interna? Se o bloco pode permutar internamente, multiplique por essa quantidade.
• Fixação de posições antes de preencher: primeiro escolha/garanta as posições restritas, depois conte o preenchimento das lacunas.