Funções Geradoras

Uma função geradora exponencial (EGF) de uma sequência a₀, a₁, a₂, … é a série formal A(x) = Σ (aₙ/n!) xⁿ. O coeficiente de xⁿ é aₙ/n!, porque os n elementos contados são distintos.

Produto de EGFs, extração de aₙ e as séries eˣ e 1/(1−x) deste tópico — e partições de conjuntos e os números de Bell e Stirling no tópico seguinte — partem dessa série.

As páginas se agrupam em três blocos. O primeiro escreve A(x) e escolhe EGF ou geradora ordinária Σ aₙ xⁿ, conforme os objetos sejam distintos ou idênticos.

O segundo opera as séries. A soma junta classes rotuladas disjuntas do mesmo tamanho. O produto A(x)B(x) é a EGF de cₙ = Σ C(n,k) aₖ bₙ₋ₖ: escolhem-se k dos n rótulos para a primeira estrutura.

O terceiro extrai aₙ = n! [xⁿ] A(x) e reconhece formas fechadas: eˣ tem aₙ = 1, 1/(1−x) tem aₙ = n!, eᵏˣ tem cₙ = kⁿ.

Decidir EGF ou geradora ordinária pela distinção dos objetos está em Funções Geradoras Exponenciais.

O produto A(x)B(x) e a convolução binomial cₙ = Σ C(n,k) aₖ bₙ₋ₖ estão em Funções Geradoras Exponenciais. Sem o C(n,k), o produto é o da geradora ordinária.

Ler aₙ = n! [xⁿ] A(x) está em Funções Geradoras Exponenciais. A EGF 1/(1−x) devolve permutações (aₙ = n!); eˣ devolve conjuntos rotulados (aₙ = 1).

Contar funções de n rótulos em k tipos — eᵏˣ, cₙ = kⁿ — está em Funções Geradoras Exponenciais. A série (1−x)⁻ᵏ trata o caso em que os objetos são idênticos.