Análise Combinatória

Na combinação, a ordem não importa — escolher {A, B} é o mesmo que escolher {B, A}: C(n,p) = n! ÷ [p!·(n−p)!]. No arranjo, a ordem importa — AB é diferente de BA: A(n,p) = n! ÷ (n−p)!. A permutação é o caso em que se ordenam todos os elementos: P(n) = n!. As três não são independentes. O arranjo e a combinação contam exatamente os mesmos grupos; o arranjo apenas conta cada grupo várias vezes, uma para cada ordem possível dentro dele. Daí a relação A(n,p) = C(n,p) × p!. Com n = 5 e p = 2: a combinação dá 10 e o arranjo dá 20, e a razão entre eles é 2! = 2, as duas ordens de cada par. Com p = 3, a razão seria 3! = 6. É por isso que o arranjo é sempre maior ou igual à combinação — e por isso trocar um pelo outro multiplica a resposta por p!, um erro que cresce rápido: com p = 5, o resultado sai 120 vezes maior.

Antes de qualquer conta, responda: trocar a ordem dos escolhidos gera um resultado diferente? Se sim, é arranjo. Pódio de ouro, prata e bronze: primeiro e segundo lugar não são intercambiáveis. Senha, placa, ordem de apresentação. Se não, é combinação. Comissão de três pessoas, cartas de uma mão de pôquer, dezenas de um bilhete de loteria: o conjunto é o mesmo qualquer que seja a ordem em que você o escreveu. Se é para ordenar todos os elementos, é permutação — um arranjo de n tomados n a n, já que A(n,n) = n! ÷ 0! = n!. Curiosamente, o exemplo mais citado no dia a dia usa o nome errado: o "segredo" de um cadeado de combinação depende totalmente da ordem, então é um arranjo, não uma combinação.

As três fórmulas clássicas assumem que cada elemento é usado no máximo uma vez. Quando a repetição é permitida, as contas mudam. Para escolher p elementos entre n com repetição e com ordem importando, o total é simplesmente n^p. Uma senha numérica de 4 dígitos tem 10⁴ = 10.000 possibilidades — e não A(10,4) = 5.040, que seria o número de senhas com todos os dígitos diferentes. Outro caso comum é permutar elementos repetidos. A palavra BANANA tem 6 letras, mas apenas 6! ÷ (3!·2!·1!) = 720 ÷ 12 = 60 anagramas distintos, porque trocar dois As entre si não produz palavra nova. A regra é dividir n! pelo fatorial da quantidade de cada elemento repetido.

A simetria C(n,p) = C(n, n−p) diz que escolher quem entra é o mesmo que escolher quem fica de fora. Isso transforma contas impraticáveis em triviais: C(60,54) é idêntico a C(60,6). A soma de todas as combinações de um conjunto é uma potência de dois: C(n,0) + C(n,1) + … + C(n,n) = 2ⁿ. Faz sentido, porque escolher um subconjunto é decidir, para cada elemento, se ele entra ou não — n decisões binárias. Um conjunto de 5 elementos tem 32 subconjuntos, incluindo o vazio e ele mesmo. E há a relação de Pascal, C(n,p) = C(n−1, p−1) + C(n−1, p), que constrói o triângulo de Pascal: cada número é a soma dos dois acima. Ela permite obter combinações apenas somando, sem calcular fatoriais gigantes — o que também evita estouro numérico em programação.

Contagem combinatória cresce em uma velocidade difícil de intuir, e alguns números concretos ajudam a calibrar. Um aperto de mão entre todos os presentes em uma sala de 10 pessoas dá C(10,2) = 45 apertos. Com 30 pessoas, já são 435. Uma aposta simples da Mega-Sena escolhe 6 dezenas entre 60, sem que a ordem importe: C(60,6) = 50.063.860 combinações possíveis. É a definição exata de uma chance em cinquenta milhões. E um baralho comum de 52 cartas tem 52! ordens possíveis — cerca de 8 × 10⁶⁷, um número de 68 dígitos. Para comparação, desde o Big Bang passaram-se algo da ordem de 10¹⁷ segundos. É por isso que se costuma dizer que um embaralhamento bem feito quase certamente produz uma sequência que nunca existiu antes.