Distribuição

Uma distribuição de n objetos em k caixas é uma alocação: cada objeto vai para alguma caixa. O número de modos depende de os objetos terem nome e de as caixas terem rótulo.

Classificar o caso, contar ocupações (x₁,…,xₖ) e o coeficiente n!/(k₁!⋯kₘ!) deste tópico — e combinações com repetição e funções geradoras nos tópicos seguintes — partem dessa alocação.

As páginas se agrupam em três blocos. O primeiro decide qual fórmula cabe: kⁿ para funções, C(n+k−1, k−1) para ocupações de idênticos, S(n,k) para blocos sem nome, ou partição do inteiro n.

O segundo monta a bijeção: n estrelas e k−1 barras para as soluções de x₁+⋯+xₖ = n com xᵢ ≥ 0, e a troca yᵢ = xᵢ−1 quando nenhuma caixa pode ficar vazia.

O terceiro encadeia binomiais: escolhe k₁ dos n para o grupo 1, k₂ dos restantes para o grupo 2, e assim por diante, com os grupos já nomeados.

Problemas Básicos de Distribuição escolhe entre kⁿ, C(n+k−1, k−1), S(n,k) e partição do inteiro. A prova de que as soluções não negativas são C(n+k−1, k−1) está em Método de Estrelas e Barras.

Balas idênticas em potes rotulados, tamanhos livres, estão em Método de Estrelas e Barras. Cartas ou pessoas distintas em times nomeados de tamanhos k₁,…,kₘ estão em Coeficientes Multinomiais.

Cada objeto distinguível escolhendo uma de k caixas rotuladas, sem tamanhos prescritos, é kⁿ em Problemas Básicos de Distribuição. Os mesmos objetos com as quantidades já fixas por caixa são o multinomial em Coeficientes Multinomiais.

O recorte por teto xᵢ ≤ c está em Problemas Básicos de Distribuição. A troca yᵢ = xᵢ−1 que produz C(n−1, k−1) está em Método de Estrelas e Barras.