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 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 if Neste caso, escrevemos 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.