Combinatòria enumerativa

La combinatoria enumerativa és un àrea de la combinatòria que tracta de la cantitat de maneres en que es poden formar certs patrons. Dos eixemples d'este tipo de problema són contar combinacions i contar permutació. De manera més general, donada una colecció infinita de conjunts finitos Si indexats pels número natural, la combinatoria enumerativa busca descriure una funció de conteo que conta el número d'objectes en Sn per a cada n. Encara que contar el número d'elements en un conjunt és un problema matemàtic prou ampli, molts dels problemes que sorgixen en les aplicacions tenen una descripció combinatòria relativament simple.

Les funcions més simples són les fòrmules tancades, que es poden expressar  com una composició de funcions elementals com factorials, potència, etc. Per eixemple, com es mostra a continuació, el número de diferents ordenaments possibles d'un mall de n cartes és f(n) = n!. El problema de trobar una fòrmula tancada es coneix com a enumeració algebraica, i en freqüència implica derivar una relació de recurrencia o funció generadora i usar açò per a aplegar a la forma tancada desijada.

A sovint, una fòrmula tancada complicada proporciona poca informació sobre el comportament de la funció de conteo a mida que creix el número d'objectes contats. En estos casos, una aproximació asintòtica simple pot ser preferible. Una funció g(n) és una aproximació asintòtica a $f(n)$  si $f(n)/g(n)\to 1$. En este cas escrivim $n\to \mathrm{\infty }$.

Funcions Generatrices

Les funcions generadores s'usen per a descriure famílies d'objectes combinatòries. F denota la família d'objectes i F(x) és la seua funció generadora. Llavors:

$F(x)=\sum _{n=0}^{\mathrm{\infty }}{f}_n{x}^n$

on $f_n$ denota la cantitat d'objectes combinatoris de tamany n. Per lo tant, el número d'objectes combinatoris de tamany n està donat pel coeficient de $x^n$. Es desenrollarà ara una operació comuna en famílies d'objectes combinatoris i el seu efecte sobre la funció generadora. La funció de generació exponencial també s'usa a voltes. En este cas, tindria la forma

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

Una volta determinat, la funció generadora proporciona l'informació donada pels enfocaments anteriors. Ademés, les diverses operacions naturals en les funcions de generació tals com la suma, la multiplicació, la diferenciació, etc., tenen una importància combinatòria, açò permet estendre els resultats d'un problema combinatori per a resoldre uns atres.

Unió

Donades dos famílies combinatòries,$ℱ$ i $𝒢$ en funcions generadores F(x) i G(x) respectivament, l'unió disjunta de les dos famílies,

($ℱ\cup 𝒢$) té la funció generadora F(x) + G(x).

Parells

Per a dos famílies combinatòries, com les anteriors, el producte cartesiano (parell) de les dos famílies ($ℱ\times 𝒢$)té la funció generadora F(x)G(x).

Seqüències

Una seqüència generalisa l'idea del parell com es va definir anteriorment. Les seqüències són productes cartesianos arbitraris d'un objecte combinatori en si mateixa. Formalment:

$\text{Seq}(ℱ)=ϵ\cup ℱ\cup ℱ\times ℱ\cup ℱ\times ℱ\times ℱ\cup \cdots$

Per a posar lo anterior en paraules: una seqüència buida o una seqüència d'un element o una seqüència de dos elements o una seqüència de tres elements, etc. La funció generadora seria:

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

Estructures combinatòries

Les operacions anteriors ara es poden usar per a enumerar objectes combinatoris comuns, inclosos arbres (binarios i plans), camins Dyck i cicles. Una estructura combinatòria està composta d'àtoms. Per eixemple, en arbres, els àtoms series els nodos. Els àtoms que componen l'objecte poden estar etiquetats o no etiquetats. Els àtoms no etiquetats són indistinguibles entre sí, mentres que els àtoms marcats són distints. Per lo tant, per a un objecte combinatori que consistix en àtoms etiquetats, es pot formar un nou objecte simplement intercanviant dos o més àtoms.

Arbres i arbres binarios

Els arbres són eixemples d'una estructura combinatòria no etiquetada. Els arbres consistixen en nodos units per arestes de tal manera que no hi ha cicles. En general, hi ha un nodo cridat raïl, que no té nodo primari. En els arbres,cada nodo pot tindre un número arbitrari de fills. En els arbres binarios, un cas especial és que cada nodo pot tindre dos o cap fill.$𝒫$ denota la família de tots els arbres. Llavors esta família es pot definir recursivamente de la següent manera:

$𝒫=\{\bullet \}\times \text{Seq}(𝒫)$

En este cas $\{\bullet \}$ representa la família d'objectes que consistix en un nodo. Açò té la funció generadora x. P(x) denota la funció generadora $𝒫$ . Posant la descripció anterior en paraules: Un arbre consistix en un nodo al com està unit un número arbitrari de subárboles, cada u dels quals és també un arbre. En utilisar l'operació en famílies d'estructures combinatòries desenrollades anteriorment, açò es traduïx en una funció de generació recursiva:

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

Despuix de resoldre per a P(x):

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

Ara es pot determinar una fòrmula explícita per a la cantitat d'arbres plans de tamany n extraent el coeficient de $x^n$.

$\begin{array}{cc}{p}_n& =[x^n]P(x)=[x^n]\frac{1-\sqrt{1-4x}}{2}\\ & =[x^n]\frac{1}{2}-[x^n]\frac{1}{2}\sqrt{1-4x}\\ & =-\frac{1}{2}[x^n]\sum _{k=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{\frac{1}{2}}{k})(-4x{)}^k\\ & =-\frac{1}{2}(\genfrac{}{}{0ex}{}{\frac{1}{2}}{n})(-4{)}^n\\ & =\frac{1}{n}(\genfrac{}{}{0ex}{}{2n-2}{n-1})\end{array}$

Nota: La notació [$x^n$] f(x) es referix al coeficient de $x^n$ en f(x). l'expansió en série de la raïl quadrada es basa en la generalisació de Newton del teorema binomial. Per a aplegar des de la quarta a quinta llínea, es necessiten manipulacions que utilisen el coeficient binomial generalisat.

L'expressió en l'última llínea és igual al (n-1)-ésimo número de Catalan. Per lo tant, pn = cn - 1.