Definition of Species
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 and bijections (the collection of all finite sets, and invertible functions between them). A species is a functor
given a set A, it yields the set F of F-structures on A. A functor also operates on bijections. If φ is a bijection between sets A and B, then F is a bijection between the sets of F-structures F and F, called transport of F-structures along φ.
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 diagram below 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 depends only on the size of A. (This follows from the formal definition of a functor.) Restriction to finite sets means that |F| 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 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 T2 of pairs (2-tuples) is the functor taking a set A to A2. Then and .
Read more about this topic: Combinatorial Species
Famous quotes containing the words definition of, definition and/or species:
“No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
—Florence Nightingale (1820–1910)
“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)
“If there is a species which is more maltreated than children, then it must be their toys, which they handle in an incredibly off-hand manner.... Toys are thus the end point in that long chain in which all the conditions of despotic high-handedness are in play which enchain beings one to another, from one species to another—cruel divinities to their sacrificial victims, from masters to slaves, from adults to children, and from children to their objects.”
—Jean Baudrillard (b. 1929)