Fatorial, arranjos e combinações

Fatorial e combinações

Quantas senhas de quatro dígitos diferentes existem? De quantas formas cinco amigos podem sentar em cinco cadeiras? Perguntas como essas são de contagem, e a ferramenta básica é o fatorial.

O fatorial

O fatorial de n, escrito n!, é o produto de todos os inteiros de 1 até n. Assim, 5! = 5 · 4 · 3 · 2 · 1 = 120. Ele conta as maneiras de ordenar n objetos distintos. Os cinco amigos podem sentar de 120 formas diferentes.

Por convenção, 0! = 1, porque existe exatamente uma maneira de organizar zero objetos.

O fatorial cresce muito depressa: 10! = 3.628.800 e 20! já tem 19 algarismos. Por isso a aula usa números inteiros exatos, e não aproximações em ponto flutuante.

Arranjos e combinações

Muitas vezes a ordem não importa. Em uma loteria em que você escolhe 6 números entre 60, o que importa é o conjunto, não a sequência. Quando a ordem importa, contam-se os arranjos:

P(n, k) = n! / (n − k)!

Quando a ordem não importa, contam-se as combinações:

C(n, k) = n! / (k! (n − k)!)

Para a loteria de 6 em 60, isso dá cerca de 50 milhões de possibilidades (exatamente 50.063.860). A chance de acertar um jogo específico é, portanto, muito pequena, e é por isso que os prêmios são tão grandes.

A relação entre as duas é simples: cada combinação de k elementos pode ser ordenada de k! formas, então P(n, k) = k! · C(n, k).

Triângulo de Pascal

Os coeficientes C(n, k) aparecem no triângulo de Pascal, em que cada número é a soma dos dois de cima. Na aula, a linha n e a coluna k da combinação escolhida ficam destacadas. Essa regra vale porque, para escolher k objetos entre n, ou o primeiro objeto entra na escolha (e sobram k − 1 para escolher entre n − 1), ou não entra (e k são escolhidos entre n − 1). Somando, C(n, k) = C(n − 1, k − 1) + C(n − 1, k).

Os coeficientes também são os do binômio (a + b)ⁿ, que é uma das ideias mais úteis da álgebra: (a + b)² = a² + 2ab + b², com coeficientes 1, 2, 1, da linha 2 do triângulo.

Combinações com repetição

Se os objetos podem ser escolhidos mais de uma vez, como em uma compra de três bolinhos entre cinco sabores, o número de maneiras é C(n + k − 1, k). A aula mostra essa contagem junto das outras, e o painel usa a convenção de que 0 objetos têm uma única escolha.

Aproximação de Stirling

Para valores grandes de n, o fatorial pode ser estimado por n! ≈ √(2πn) (n/e)ⁿ, a fórmula de Stirling. A aula compara a estimativa com o valor exato e mostra o erro relativo, que diminui conforme n cresce. Ela é usada em física estatística e na análise de algoritmos.

Aplicações

• Probabilidade: a chance de um evento é contagem de casos favoráveis dividida pelo total, e o total costuma ser uma combinação.
• Criptografia e senhas: o número de senhas possíveis é uma contagem de arranjos.
• Estatística: amostras e permutações de testes usam contagens desse tipo.

Curiosidade

O triângulo de Pascal é muito mais antigo que Pascal. Matemáticos da Índia, da Pérsia e da China já o conheciam séculos antes do tratado de Blaise Pascal, escrito em 1654, que o usou para resolver problemas de probabilidade de jogos de azar.

Perguntas de revisão

1. Quantas maneiras existem de ordenar 4 objetos distintos?

Resposta: 24 (4! = 4 · 3 · 2 · 1).

1. Quando a ordem não importa, qual conta se usa?

Resposta: a combinação C(n, k).