Enumerative combinatorics

Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infinite collection of finite sets {S_i} indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in S_n for each n. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description. The twelvefold way provides a unified framework for counting permutations, combinations and partitions.

The simplest such functions are closed formulas, which can be expressed as a composition of elementary functions such as factorials, powers, and so on. For instance, as shown below, the number of different possible orderings of a deck of n cards is f(n) = n!. Often, no closed form is initially available. In these cases, we frequently first derive a recurrence relation, then solve the recurrence to arrive at the desired closed form.

Finally, f(n) may be expressed by a formal power series, called its generating function, which is most commonly either the ordinary generating function

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

or the exponential generating function

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

Often, a complicated closed formula yields little insight into the behavior of the counting function as the number of counted objects grows. In these cases, a simple asymptotic approximation may be preferable. A function $g(n)$ is an asymptotic approximation to $f(n)$ if $f(n)/g(n)\rightarrow 1$ as $n\rightarrow \infty$. In this case, we write $f(n)\sim g(n).\,$

Once determined, the generating function yields the information given by the previous approaches. In addition, the various natural operations on generating functions such as addition, multiplication, differentiation, etc., have a combinatorial significance; this allows one to extend results from one combinatorial problem in order to solve others.

Generating functions

Generating functions are used to describe families of combinatorial objects. Let ${\mathcal {F}}$ denote the family of objects and let F(x) be its generating function. Then:

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

Where $f_{n}$ denotes the number of combinatorial objects of size n. The number of combinatorial objects of size n is therefore given by the coefficient of $x^{n}$. Some common operation on families of combinatorial objects and its effect on the generating function will now be developed. The exponential generating function is also sometimes used. In this case it would have the form:

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

Union

Given two combinatorial families, ${\mathcal {F}}$ and ${\mathcal {G}}$ with generating functions F(x) and G(x) respectively, the union of the two families (${\mathcal {F}}\cup {\mathcal {G}}$) has generating function F(x) + G(x).

Pairs

For two combinatorial families as above the Cartesian product (pair) of the two families (${\mathcal {F}}\times {\mathcal {G}}$) has generating function F(x)G(x).

Sequences

A sequence generalizes the idea of the pair as defined above. Sequences are arbitrary Cartesian products of a combinatorial object with itself. Formally:

${\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$

To put the above in words: An empty sequence or a sequence of one element or a sequence of two elements or a sequence of three elements, etc. The generating function would be:

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

Combinatorial structures

The above operations can now be used to enumerate common combinatorial objects including trees (binary and plane), Dyck paths and cycles. A combinatorial structure is composed of atoms. For example, with trees the atoms would be the nodes. The atoms which compose the object can either be labeled or unlabeled. Unlabeled atoms are indistinguishable from each other, while labelled atoms are distinct. Therefore, for a combinatorial object consisting of labeled atoms a new object can be formed by simply swapping two or more atoms.

Binary and plane trees

Binary and plane trees are examples of an unlabeled combinatorial structure. Trees consist of nodes linked by edges in such a way that there are no cycles. There is generally a node called the root, which has no parent node. In Plane trees each node can have an arbitrary number of children. In binary trees, a special case of plane trees, each node can have either two or no children. Let ${\mathcal {P}}$ denote the family of all plane trees. Then this family can be recursively defined as follows:

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

In this case $\{\bullet \}$ represents the family of objects consisting of one node. This has generating function x. Let P(x) denote the generating function ${\mathcal {P}}$ Putting the above description in words: A plane tree consists of a node to which is attached an arbitrary number of subtrees, each of which is also a plane tree. Using the operation on families of combinatorial structures developed earlier this translates to a recursive generating function:

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

After solving for P(x):

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

An explicit formula for the number of plane trees of size n can now be determined by extracting the coefficient of 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}}$

Note: The notation [xⁿ] f(x) refers to the coefficient of xⁿ in f(x). The series expansion of the square root is based on Newton's generalization of the binomial theorem. To get from the fourth to fifth line manipulations using the generalized binomial coefficient is needed.

The expression on the last line is equal to the (n − 1)^th Catalan number. Therefore p_n = c_n−1.

See also

• Combinatorial principles
• Algebraic combinatorics
• Asymptotic combinatorics
• Combinatorial explosion
• Inclusion-exclusion principle
• Method of distinguished element
• Combinatorial species
• Sieve theory
• Pólya enumeration theorem

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

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

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.