Combinatória: A Matemática de Contar sem Contar

A Lotaria Primitiva portuguesa pede que escolhas 6 números de 1 a 49. A probabilidade de acertar no jackpot é 1 em 13 983 816. Nunca ninguém listou as 13 milhões de possibilidades — mas qualquer pessoa com combinatória calcula esse número em segundos.

A combinatória é a arte de contar possibilidades sem as enumerar explicitamente. Está em todo o lado: criptografia, biologia molecular (quantas proteínas diferentes se podem formar com 20 aminoácidos?), redes sociais (quantas amizades possíveis em 1000 pessoas?), algoritmos de ordenação, e muito mais.

Princípio Fundamental da Contagem

Se uma decisão tem m possibilidades e outra tem n possibilidades, o número de formas de tomar as duas decisões é m × n.

Generalização: Se temos k decisões independentes com $n_{1}, n_{2}, \dots, n_{k}$ possibilidades, o total é $n_{1} \times n_{2} \times \dots \times n_{k}$ .

Exemplo — Senha de 4 dígitos:

Cada dígito: 10 possibilidades (0–9)
Total: 10 × 10 × 10 × 10 = 10 000 senhas

Exemplo — Senha 8 chars (maiúsculas + minúsculas + dígitos):

26 + 26 + 10 = 62 caracteres possíveis por posição
Total: 62⁸ = 218 340 105 584 896 ≈ 2,2 × 10¹⁴ senhas

É por isto que senhas mais longas são exponencialmente mais seguras.

Factorial

Para contar ordenações de n elementos distintos:

n! = n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1

Convenção: 0! = 1 (existe exatamente 1 forma de ordenar 0 elementos — não fazer nada).

| n | n! | |---|-----| | 0 | 1 | | 1 | 1 | | 2 | 2 | | 3 | 6 | | 4 | 24 | | 5 | 120 | | 10 | 3 628 800 | | 20 | 2,43 × 10¹⁸ |

ℹNota

O factorial cresce mais depressa do que qualquer polinómio ou exponencial de base fixa. Com 20 pessoas numa sala, existem mais de 2 quadrilhões de ordens possíveis em que podem sentar-se.

Permutações

Permutações de n elementos: número de formas de ordenar todos os n elementos = n!

Permutações de n elementos, tomados p de cada vez: escolher e ordenar p elementos de n:

P_{n}^{p} = A_{n}^{p} = \frac{n !}{( n - p )!}

Exemplo: Em quantas ordens podem 10 atletas ocupar os 3 lugares do pódio?

P_{10}^{3} = \frac{10 !}{7 !} = 10 \times 9 \times 8 = 720

Combinações

Combinações diferem das permutações porque a ordem não importa: apenas queremos saber quais elementos, não em que sequência.

C_{n}^{p} = (p n) = \frac{n !}{p ! ( n - p )!}

Lê-se: "n choose p" ou "combinações de n, p a p".

Exemplo — Lotaria Primitiva: Escolher 6 números de 49, sem importar a ordem:

C_{49}^{6} = \frac{49 !}{6 ! \times 43 !} = \frac{49 \times 48 \times 47 \times 46 \times 45 \times 44}{6 !} = 13983816

Triângulo de Pascal e Binómio de Newton

As combinações aparecem naturalmente no Triângulo de Pascal: cada entrada é a soma das duas acima.

Row 0: 1 Row 1: 1 1 Row 2: 1 2 1 Row 3: 1 3 3 1 Row 4: 1 4 6 4 1

A linha n contém os coeficientes $(0 n), (1 n), \dots, (n n)$ .

Binómio de Newton:

(a + b)^{n} = k = 0 \sum n (k n) a^{n - k} b^{k}

Exemplo: $(x + 1)^{4} = x^{4} + 4 x^{3} + 6 x^{2} + 4 x + 1$