Resumo básico de análise combinatória

Esta é uma compilação das fórmulas e assuntos mais comuns em análise combinatória a nível básico/introdutório que eu já cobri no blog. A maioria está demonstrada e explicada em contexto nos seguintes posts, na ordem de aprendizado sugerida:

• Analisando a análise combinatória - Post introdutório com o Princípio Fundamental da Contagem, fórmulas básicas de arranjos, permutações e combinações. Como componente opcional, descreve também o Princípio da Casa dos Pombos.

• Questões resolvidas de Análise Combinatória - Apresenta a dedução de algumas fórmulas adicionais de análise combinatória nas últimas questões.

• Análise combinatória - Combinações com repetição - Demonstração da fórmula de combinações com repetição.

• Análise combinatória - Objetos em caixas - Aborda o assunto de "objetos em caixas", metáforas úteis para a resolução de problemas mais avançados em análise combinatória.

Outros posts em análise combinatória incluem Técnica de contagem: contagem por casos, Triângulo de Pascal e propriedades, Contando quadrados e retângulos e Recorrências e recursividade, que não estão inclusos aqui por tratarem de assuntos mais específicos, opcionais, ou fugirem ao escopo pretendido de outra maneira.

Princípio Fundamental da Contagem

Se um acontecimento ocorre em k etapas diferentes, com a primeira etapa podendo ocorrer de n1 maneiras diferentes, a segunda etapa podendo ocorrer de n2 maneiras diferentes, e assim sucessivamente, então o número total, n, de possibilidades para o acontecimento é:

n = n1 * n2 * ... * nk

Permutações

Uma permutação de n elementos é qualquer sequência formada por esses elementos, diferindo apenas na ordem. Por exemplo, as permutações de 123 são: {123, 132, 213, 231, 312, 321}. O número total de permutações é dado por n! (lê-se "n fatorial"), sendo que n! = n * (n - 1) * (n - 2) * ... * 1, e 0! = 1! = 1.

Permutações com repetição permitida

Se temos n elementos a serem permutados, e podemos repetir qualquer um deles (por exemplo, na hora de formar um número de 3 dígitos usando os algarismos 1, 2 e 3, algumas possibilidades são 111 e 223), então o número de permutações é dado por \(\mathbf{n^n}\).

Permutações com elementos repetidos

Dados n elementos com repetição do elemento a1 n1 vezes, a2 n2 vezes, ..., ak nk vezes, o total de permutações, desconsiderando a redundância causadas pelas repetições, é dado por:

\(\mathbf{\frac{n!}{n1!n2!...nk!}}\)

Permutações circulares

Em permutações circulares, importa apenas a posição relativa de cada elemento, ignorando rotações. Por exemplo, as duas configurações abaixo são equivalentes, apenas rotacionadas:

Neste caso, o número de permutações é dado por (n - 1)!

Arranjos

Arranjos são sequências formadas por p elementos dentre um total de n elementos, em que a ordem faz diferença. Por exemplo, combinar os algarismos 1, 2, 3 e 4 em um número de 2 dígitos distintos. A fórmula é \(\mathbf{A(n,p) = \frac{n!}{(n-p)!}}\), mas eu não recomendo decorar. É mais fácil e seguro utilizar o Princípio Fundamental da Contagem.

Combinações

Como arranjos, combinações são sequências formadas por p elementos dentre um total de n elementos, mas desta vez a ordem não importa. Um exemplo de combinação é decidir de quantas formas pode-se escolher 3 empregados dentre 10 concorrentes. A fórmula é dada por:

$$ \mathbf{C^n_p = \frac{A_{n,p}}{p!} = \frac{n!}{p!(n - p)!}} $$

Combinações com repetição

Em uma combinação de n elementos tomados de p a p em que é permitido repetir elementos, o número total de combinações é dado por:

$$ \mathbf{CR^n_p = C^{n + p - 1}_p} $$

Distribuição de objetos em caixas

Considerando o problema de combinar n objetos em k caixas, tanto objetos quanto caixas podem ser:

• Idênticos ou indistinguíveis: Há apenas um tipo de objeto ou caixa.

• Distintos ou distinguíveis: Há dois ou mais tipos diferentes de objetos ou caixas.

Objetos idênticos em caixas distintas

A fórmula básica para esse tipo de distribuição é \(\mathbf{C^{n - 1}_{k - 1}}\). Se considerarmos que algumas caixas podem ficar vazias, então aplicamos a seguinte fórmula: \(\mathbf{CR^{n + 1}_{k - 1}}\).

Objetos idênticos em caixas idênticas

A fórmula para determinar o número de distribuições de n objetos idênticos em k caixas idênticas é part(n, k), que equivale a descobrir o número de partições de n em k parcelas. Uma relação recursiva útil para calcular valores grandes é: part(n, k) = part(n - 1, k - 1) + part(n - k, k).

Objetos distintos em caixas distintas

O número de distribuições de n objetos distintos em k caixas distintas é \(\mathbf{k^n}\). Se, contudo, adicionarmos a restrição de que nenhuma caixa pode ficar vazia, ficamos com: \(\mathbf{\sum_{p = 0}^{k - 1} (-1)^p C^k_p (k - p)^n}\).

Objetos distintos em caixas idênticas

O número de distribuições possíveis para objetos distintos em caixas idênticas é dado por um número de Stirling da segunda ordem: B(n, k). Uma maneira de calcular esse valor recursivamente é:

B(n,k) = B(n - 1, k - 1) + k * B(n - 1, k)

Tal que:

B(n, n) = 1 (para n > 0)

B(n, 0) = 0 (para n >= 0)