Namespaces
Variants
Actions

Difference between revisions of "User:Richard Pinch/sandbox-17"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Start article: Combinatorial species)
 
m (better)
 
(4 intermediate revisions by the same user not shown)
Line 2: Line 2:
 
A class of finite labelled stuctures closed under relabelling.  A contravariant [[functor]] from the [[category]] $\mathcal B$ of finite sets and bijections to the category $\mathcal F$ of finite sets and functions.  A species $R$ thus determines the following data.   
 
A class of finite labelled stuctures closed under relabelling.  A contravariant [[functor]] from the [[category]] $\mathcal B$ of finite sets and bijections to the category $\mathcal F$ of finite sets and functions.  A species $R$ thus determines the following data.   
  
*For a finite set $V$, a finite set $R[V]$, thought of as the $R$-structures with labels in $V$.   
+
*For a finite set $V$, a finite set $R[V]$, thought of as the $R$-structures with labels in $V$.  We write $R[n]$ for $R[\{1,\ldots,n\}]$.
We write $R[n]$ for $R[\{1,\ldots,n\}]$.
+
*For a bijection $f: V \rightarrow W$, a map $R[f] : R[V] \rightarrow R[W]$, with the properties that $R[\mathrm{id}_V] = \mathrm{id}_{R[V]}$ and $R[f\circ g] = R[f] \circ R[g]$.
*For a bijection $f: V \rightarrow W$, a map $R[f] : R[V] \rightarrow R[W]$, with the properties  
 
that $R[\mathrm{id}_V] = \mathrm{id}_{R[V]}$ and $R[f\circ g] = R[f] \circ R[g]$.
 
  
 
The ''(exponential) generating function'' of $R$ is the [[formal power series]]
 
The ''(exponential) generating function'' of $R$ is the [[formal power series]]
 
$$
 
$$
R(x) = \sum_{n=0}^\infty \frac{|R[n]|}{n!} x^n
+
R(x) = \sum_{n=0}^\infty |R[n]|\, \frac{x^n}{n!}
 +
$$
 +
 
 +
Some special examples.
 +
$$
 +
\mathbf{0} : V \mapsto \emptyset
 +
$$
 +
$$
 +
\mathbf{1} : V \mapsto \left\lbrace{ \begin{array}{cl} \{\emptyset\} & \text{if } V = \emptyset \\ \emptyset & \text{otherwise} \end{array} }\right.
 +
$$
 +
$$
 +
\mathbf{X} : V \mapsto \left\lbrace{ \begin{array}{cl} \{v\} & \text{if } V = \{v\} \\ \emptyset & \text{otherwise} \end{array} }\right.
 +
$$
 +
 
 +
The generating functions of these species are $0$, $1$ and $x$ respectively.  A species is ''connected'' if $|R[1]| = 1$.
 +
 
 +
A [[natural transformation]] between species $H \rightarrow R$ is a family of maps $H[V] \rightarrow R[V]$ compatible with relabelling. 
 +
 
 +
Further examples.  ''Lists'' and ''permutations'' both have generating function $\frac{1}{1-x}$.  They are not isomorphic. 
 +
 
 +
Operations.  The ''sum'' of two species $A+B$ is the [[disjoint union]] $(A+B)[V] = A[V] \sqcup B[V]$.  The ''product'' of two species
 +
is given by a sum over partitions
 +
$$
 +
(A.B)[V] = \sum_{V = V_1 \sqcup V_2} A[V_1] \times B[V_2]
 
$$
 
$$

Latest revision as of 11:01, 26 July 2021

Combinatorial species

A class of finite labelled stuctures closed under relabelling. A contravariant functor from the category $\mathcal B$ of finite sets and bijections to the category $\mathcal F$ of finite sets and functions. A species $R$ thus determines the following data.

  • For a finite set $V$, a finite set $R[V]$, thought of as the $R$-structures with labels in $V$. We write $R[n]$ for $R[\{1,\ldots,n\}]$.
  • For a bijection $f: V \rightarrow W$, a map $R[f] : R[V] \rightarrow R[W]$, with the properties that $R[\mathrm{id}_V] = \mathrm{id}_{R[V]}$ and $R[f\circ g] = R[f] \circ R[g]$.

The (exponential) generating function of $R$ is the formal power series $$ R(x) = \sum_{n=0}^\infty |R[n]|\, \frac{x^n}{n!} $$

Some special examples. $$ \mathbf{0} : V \mapsto \emptyset $$ $$ \mathbf{1} : V \mapsto \left\lbrace{ \begin{array}{cl} \{\emptyset\} & \text{if } V = \emptyset \\ \emptyset & \text{otherwise} \end{array} }\right. $$ $$ \mathbf{X} : V \mapsto \left\lbrace{ \begin{array}{cl} \{v\} & \text{if } V = \{v\} \\ \emptyset & \text{otherwise} \end{array} }\right. $$

The generating functions of these species are $0$, $1$ and $x$ respectively. A species is connected if $|R[1]| = 1$.

A natural transformation between species $H \rightarrow R$ is a family of maps $H[V] \rightarrow R[V]$ compatible with relabelling.

Further examples. Lists and permutations both have generating function $\frac{1}{1-x}$. They are not isomorphic.

Operations. The sum of two species $A+B$ is the disjoint union $(A+B)[V] = A[V] \sqcup B[V]$. The product of two species is given by a sum over partitions $$ (A.B)[V] = \sum_{V = V_1 \sqcup V_2} A[V_1] \times B[V_2] $$

How to Cite This Entry:
Richard Pinch/sandbox-17. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-17&oldid=51760