Combinações

Uma combinação C(n,k) é um subconjunto de k elementos escolhidos entre n: a ordem não importa e nenhum elemento se repete. A fórmula n!/(k!(n−k)!) divide as P(n,k) filas pelas k! permutações internas de cada subconjunto.

Produto por tipos, complemento, bloco proibido e a expansão (a+b)ⁿ deste tópico — e estrelas e barras, multinomial e funções geradoras nos tópicos seguintes — partem desse C(n,k).

As páginas se agrupam em três blocos. O primeiro escolhe um comitê: calcula C(n,k), multiplica C(n₁,k₁)C(n₂,k₂) quando cada grupo já tem tamanho fixo, e passa ao complemento para pelo menos um de um tipo ou para o bloco que não pode entrar inteiro.

O segundo conta multiconjuntos: r itens a partir de n tipos, um tipo pode repetir, a ordem não cria escolha nova. Cada escolha é um vetor (x₁,…,xₙ) com x₁+⋯+xₙ = r e xᵢ ≥ 0; a conta é C(n+r−1, r).

O terceiro escreve (a+b)ⁿ como soma e lê o coeficiente de cada monômio. Daí vêm a linha n do triângulo de Pascal e a soma C(n,0)+⋯+C(n,n) = 2ⁿ.

Combinações sem Repetição exige k elementos distintos de um universo de n; se k > n a conta é 0. Combinações com Repetição permite repetir tipo e calcula C(n+r−1, r) para r unidades sobre n tipos.

Combinações sem Repetição define C(n,k) = P(n,k)/k! e calcula o comitê com tamanhos fixos, complemento ou bloco proibido. Teorema Binomial lê o mesmo C(n,k) como coeficiente de aⁿ⁻ᵏbᵏ na expansão de (a+b)ⁿ.

Marcar um elemento e escrever C(n,k) = C(n−1,k−1)+C(n−1,k) está em Combinações sem Repetição. Ler a mesma regra em (a+b)ⁿ = (a+b)(a+b)ⁿ⁻¹ está em Teorema Binomial.