Definiție combinatorică

O definiție combinatorică este o descriere a unui obiect combinatoric în limbajul specific teoriei speciilor, pornind în principal de la specii fundamentale cum ar fi Ens, Cyc sau Lin cărora li se aplică diferite operații de compunere specifice.

Anumite specii (constructibile) posedă o funcție generatoare exponențială ( expresia unei serii exponențiale convergente ) care are drept coeficienți a_n numărul de realizări ale speciei respective, pentru o cardinalitate n dată.

Pornind de la definiția combinatorică a unei specii ( constructibile ) se poate scrie imediat funcția generatoare exponențială care furnizează răspunsul la întrebarea ”Câte obiecte de tipul respectiv există pentru un n dat” prin citirea coeficienților seriei aferente.

În cazul în care seria generatoare este divergentă, aceasta poate fi înlocuită cu o serie formală, ai cărei coeficienți pot fi obținuți prin alte metode, cum ar fi iterarea.

Mai mult decât o algebră booleană, care răspunde prin 0 sau 1 (fals sau adevărat) la anumite întrebări, algebra speciilor furnizează numărul exact de obiecte cerut.

Exemple

Mulțime

Unica specie care are o singură realizare pentru fiecare cardinalitate.

„Ensemble” ( Mulțime )

Ens

$ens(x)=e^{x}\,$

1, 1, 1, 1, 1, 1, 1, 1, 1,... Șirul A000012 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

Partiție

Se spune că primul exemplu de calcul cu specii a fost dat la concursul de matematică nord-american Putnam, la o problemă legată de numărul de partiții.

„Une partition est un ensemble d'ensembles non-vides.” ( O partiție este o mulțime de mulțimi nevide. )

Part = Ens ( Ens₊ )

$part(x)=e^{e^{x}-1}$

1, 1, 2, 5, 15, 52, 203, 877, 4140,... Șirul A000110 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

Partiție ordonată

Numărul de partiții ordonate se mai numește și „numărul lui Bell”.

„Une partition ordonée est une sequence d'ensembles non-vides.” (O partiție ordonată este o secvență de mulțimi nevide)

Partiție ordonată = Lin ( Ens₊ )

$partitieordonata(x)={\frac {1}{1-(e^{x}-1)}}={\frac {1}{2-e^{x}}}\,$

1, 1, 3, 13, 75, 541, 4683, 47293, 545835,...Șirul A000670 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

Permutare

„Une permutation est un ensemble de cycles.” (O permutare este un ansamblu de cicluri)

Perm = Ens ( Cyc )

$perm(x)=e^{log{\frac {1}{1-x}}}={\frac {1}{1-x}}$

1, 1, 2, 6, 24, 120, 720, 5040, 40320,... Șirul A000142 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

Singleton

Specia care are o singură realizare, pentru cardinalitatea unu.

„Singleton” ( Singleton )

X = Ens₁

$x=x\,$

0, 1, 0, 0, 0, 0, 0, 0, 0,... Șirul A063524 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

Vezi și

• Funcție iterată

Bibliografie

• Dumitriu, Anton (1977), History of Logic, Tunbridge Wells, Eng.: Abacus Press 
• André Joyal, „Une théorie combinatoire des séries formelles”, Advances in Mathematics 42:1-82 (1981).
• Bergeron, F.; Labelle, G.; Leroux, P. (1998), Combinatorial Species and Tree-like Structures, Cambridge, New York, Melbourne: Cambridge University Press, ISBN 0-521-57323-8