Combinatorial Species

Get Combinatorial Species essential facts below. View Videos or join the Combinatorial Species discussion. Add Combinatorial Species to your Like2do.com topic list for future reference or share this resource on social media.

## Definition of species

## Software

## See also

## Notes

## References

## External links

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Combinatorial Species

This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. (June 2018) (Learn how and when to remove this template message) |

This article needs attention from an expert in mathematics. (June 2018) |

In combinatorial mathematics, the theory of **combinatorial species** is an abstract, systematic method for analysing discrete structures in terms of generating functions. Examples of discrete structures are (finite) graphs, permutations, trees, and so on; each of these has an associated generating function which counts how many structures there are of a certain size. One goal of species theory is to be able to analyse complicated structures by describing them in terms of transformations and combinations of simpler structures. These operations correspond to equivalent manipulations of generating functions, so producing such functions for complicated structures is much easier than with other methods. The theory was introduced, carefully elaborated and applied by the Canadian group of people around André Joyal.

This section does not cite any sources. (June 2018) (Learn how and when to remove this template message) |

Any structure — an instance of a particular species — is associated with some set, and there are often many possible structures for the same set. For example, it is possible to construct several different graphs whose node labels are drawn from the same given set. At the same time, any set could be used to build the structures. The difference between one species and another is that they build a different set of structures out of the same base set.

This leads to the formal definition of a *combinatorial species*. Let be the category of finite sets, with the morphisms of the category being the bijections between these sets. A species is a functor

For a set *A* the set *F*[*A*] is called the set of *F*-structures on *A*, or the set of structures of species *F* on *A*. Further, by the definition of a functor, if ? is a bijection between sets *A* and *B*, then *F*[?] is a bijection between the sets of *F*-structures *F*[*A*] and *F*[*B*], called *transport of F-structures along ?*.^{[1]}

For example, the "species of permutations" maps each finite set *A* to the set of all permutations of *A*, and each bijection from *A* to another set *B* naturally induces a bijection from the set of all permutations of *A* to the set of all permutations of *B*. Similarly, the "species of partitions" can be defined by assigning to each finite set the set of all its partitions, and the "power set species" assigns to each finite set its power set.

There is a standard way of illustrating an instance of any structure, regardless of its nature. The adjacent diagram shows a structure on a set of five elements: arcs connect the structure (red) to the elements (blue) from which it is built.

The choice of as the category on which species operate is important. Because a bijection can only exist between two sets when they have the same size, the number of elements in *F*[*A*] depends only on the size of *A*. (This follows from the formal definition of a functor.^{[]}) Restriction to finite sets means that |*F*[*A*]| is always finite, so it is possible to do arithmetic with such quantities. In particular, the *exponential generating series* *F*(*x*) of a species *F* can be defined:

where is the size of *F*[*A*] for any set *A* having *n* elements.

Some examples:

- The species of sets (traditionally called
*E*, from the French "*ensemble*", meaning "set") is the functor which maps*A*to {*A*}. Then , so . - The species
*S*of permutations, described above, has . . - The species
*T*_{2}of pairs (2-tuples) is the functor taking a set*A*to*A*^{2}. Then and .

Operations with species are supported by SageMath^{[2]} and, using a special package, also by Haskell.^{[3]}^{[4]}

**^**Federico G. Lastaria, An invitation to Combinatorial Species. (2002)**^**Sage documentation on combinatorial species.**^**Haskell package species.**^**Brent A., Yorgey (2010). "Species and functors and types, oh my!". ACM: 147-158. doi:10.1145/1863523.1863542. ISBN 978-1-4503-0252-4.

- André Joyal,
*Une théorie combinatoire des séries formelles*, Advances in Mathematics 42:1-82 (1981). - Labelle, Jacques.
*Quelques espèces sur les ensembles de petite cardinalité.*, Ann. Sc. Math. Québec 9.1 (1985): 31-58. - J. Labelle and Y.N. Yeh,
*The Relation Between Burnside Rings and Combinatorial Species*, Journal of Combinatorial Theory Series A 50, (1989) 269-284 - Yves Chiricota,
*Classification des espèces moléculaires de degré 6 et 7*, Ann. Sci. Math. Québec 17 (1993), no. 1, 1 l-37. - François Bergeron, Gilbert Labelle, Pierre Leroux,
*Théorie des espèces et combinatoire des structures arborescentes*, LaCIM, Montréal (1994). English version:*Combinatorial Species and Tree-like Structures*, Cambridge University Press (1998). - Kerber, Adalbert (1999), Applied finite group actions, Algorithms and Combinatorics, 19 (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-65941-9, MR 1716962, OCLC 247593131

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Top US Cities

United States

Like2do.com was developed using defaultLogic.com's knowledge management platform. It allows users to manage learning and research. Visit defaultLogic's other partner sites below: