Combinatória enumerativa

Combinatória enumerativa é uma área de combinatória que lida com o número de maneiras que certos padrões podem ser formados. Dois exemplos desse tipo de problema estão contando combinações e contando permutações. De modo mais geral, dado um conjunto infinito de conjuntos finitos {Si} indexado pelos números naturais, combinatória enumerativa procura descrever a função de contagem que conta o número de objetos em Sn para cada n. Apesar de contar o número de elementos em um conjunto é um problema matemático bastante amplo, muitos dos problemas que surgem em aplicações têm uma descrição relativamente simples combinatória. A maneira 'twelvefold' fornece uma estrutura unificada para a contagem de permutações, combinações e partições.

As mais simples são tais funções fórmulas fechadas, que podem ser expressas como uma composição de funções elementares, tais como factoriais, poderes, e assim por diante. Por exemplo, como mostrado abaixo, o número de diferentes ordenamentos possíveis de um baralho de cartas n é f (n) = n!. Muitas vezes, não há forma fechada está inicialmente disponível. Nestes casos, muitas vezes primeiro derivar uma relação de recorrência, em seguida resolver a recorrência para chegar à forma fechada desejado.

Finalmente, f(n) pode ser expressa por uma série de potências formal, chamada de função geradora, que é mais comumente ou a função geradora ordinária

$\sum _{n\geq 1}f(n)x^{n}$

ou a função geradora exponencial

Muitas vezes, uma fórmula fechada complicado rende pouco de conhecimento sobre o comportamento da função de contagem como o número de objetos contados cresce. Nestes casos, uma simples aproximação assintótica pode ser preferível. Uma função g(n) é uma aproximação assintótica para $f(n)$ if $f(n)/g(n)\rightarrow 1$ Neste caso, escrevemos $n\rightarrow \infty$ Uma vez determinada, a função geradora produz a informação dada pelas abordagens anteriores. Além disso, as várias operações sobre as funções naturais, tais como a adição, a multiplicação, diferenciação, etc gerando, tem um significado combinatória, o que permite uma a estender os resultados a partir de um problema combinatório de modo a resolver os outros.

Gerando Funções

Gerando funções são usadas para descrever famílias de objetos combinatórios. Deixar ${\mathcal {F}}$ denotam a família de objectos e F(x) ser a sua função de geração. Então:

$F(x)=\sum _{n=0}^{\infty }f_{n}x^{n}$

Onde $f_{n}$ indica o número de objetos combinatórios de tamanho n. O número de objetos combinatórios de tamanho n é, por conseguinte, dada pelo coeficiente de $x^{n}$. Alguns operação comum na família de objetos combinatórias e seu efeito sobre a função geradora vai agora ser desenvolvidas. A função geradora exponencial também é usado às vezes. Neste caso, ele teria a forma:

$F(x)=\sum _{n=0}^{\infty }{\frac {f_{n}}{n!}}x^{n}$

União

Dadas duas famílias combiatórias, ${\mathcal {F}}$ e ${\mathcal {G}}$ funções h geração F(x) e G(x), respectivamente, a união das duas famílias (${\mathcal {F}}\cup {\mathcal {G}}$) gera F(x) + G(x).

Pares

Para duas famílias combinatória como acima, o produto cartesiano (par) das duas famílias (${\mathcal {F}}\times {\mathcal {G}}$) gera a função F(x)G(x).

Sequências

Uma sequência generaliza a ideia do par, tal como definido acima. Seqüências são produtos cartesianos arbitrárias de um objeto combinatória com ele mesmo. Formalmente:

${\mbox{Seq}}({\mathcal {F}})=\epsilon \ \cup \ {\mathcal {F}}\ \cup \ {\mathcal {F}}\times {\mathcal {F}}\ \cup \ {\mathcal {F}}\times {\mathcal {F}}\times {\mathcal {F}}\ \cup \cdots$

Para colocar isso em palavras: uma seqüência vazia ou uma seqüência de um elemento ou de uma seqüência de dois elementos, ou uma seqüência de três elementos, etc A função geradora seria:

$1+F(x)+[F(x)]^{2}+[F(x)]^{3}+\cdots ={\frac {1}{1-F(x)}}$

Estruturas combinatórias

As operações acima pode agora ser usado para enumerar os objetos combinatórios comuns, incluindo árvores (binárias e plano), caminhos Dyck e ciclos. Uma estrutura combinatória é composta de átomos. Por exemplo, com os átomos de árvores seriam os nodos. Os átomos que compõem o objeto pode ser rotulado ou sem rótulos. Átomos não marcados são indistinguíveis uns dos outros, enquanto que os átomos marcados são distintos. Portanto, para um objecto combinatória consiste em átomos marcados um novo objecto pode ser formada, simplesmente trocando dois ou mais átomos.

Árvores binárias e planas

Árvores binárias e planas são exemplos de uma estrutura combinatória sem rótulo. Árvores consistem de nós ligados por arestas, de tal maneira que não há ciclos. Existe geralmente um chamado nó de raiz, o qual não tem o nó pai. Em árvores de avião cada nó pode ter um número arbitrário de filhos. Em árvores binárias, um caso especial de plátanos, cada nó pode ter duas ou sem filhos. Seja denotar a família de todos os plátanos. Então, essa família pode ser definida recursivamente da seguinte forma:

${\mathcal {P}}=\{\bullet \}\times {\mbox{Seq}}({\mathcal {P}})$

Neste caso $\{\bullet \}$ representa a família de objectos, constituídos por um nó. Este tem a função gerar x. Seja P (x) denota a função geradora${\mathcal {P}}$

Colocar a descrição acima em palavras: Uma árvore plano consiste em um nó ao qual está ligado um número arbitrário de sub-árvores, cada um dos quais é também um plátano. Usando a operação em famílias de estruturas combinatórias desenvolvidas mais cedo isso se traduz em uma função geradora recursiva:

$P(x)=x{\frac {1}{1-P(x)}}$

Depois de resolver para P(x):

$P(x)={\frac {1-{\sqrt {1-4x}}}{2}}$

Uma fórmula explícita para o número de árvores planas de tamanho n pode agora ser determinada por extração do coeficiente de xⁿ.

${\begin{aligned}p_{n}&=[x^{n}]P(x)=[x^{n}]{\frac {1-{\sqrt {1-4x}}}{2}}\\[6pt]&=[x^{n}]{\frac {1}{2}}-[x^{n}]{\frac {1}{2}}{\sqrt {1-4x}}\\[6pt]&=-{\frac {1}{2}}[x^{n}]\sum _{k=0}^{\infty }{{\frac {1}{2}} \choose k}(-4x)^{k}\\[6pt]&=-{\frac {1}{2}}{{\frac {1}{2}} \choose n}(-4)^{n}\\[6pt]&={\frac {1}{n}}{2n-2 \choose n-1}\end{aligned}}$

Nota: A notação [xⁿ] f(x) refere-se ao coeficiente de xⁿ em f(x). A expansão da série da raiz quadrada é baseada em generalização do teorema binomial de Newton. Para começar a partir do quarto para o quinto manipulações de linha utilizando o coeficiente binomial generalizada é necessário.

A expressão na última linha é igual a (n − 1)^th ésimo número catalã. Portanto p_n = c_n−1.