A species approach to Rota's twelvefold way
Anders Claesson

Bio-energy Transport as a Phonon Dressed Vibrational Exciton in Protein Molecules
    Theja N. De Silva^1,2 and Peighton Bolt^1
    December 30, 2023
=================================================================================



empty


  An introduction to Joyal's theory of combinatorial species is given
  and through it an alternative view of Rota's twelvefold way emerges.


introduction


§ INTRODUCTION


0.135

    < g r a p h i c s >


0.86
In how many ways can n balls be distributed into k urns? If there
are no restrictions given, then each of the n balls can be freely
placed into any of the k urns and so the answer is clearly k^n.
But what if we think of the balls, or the urns, as being identical
rather than distinct?
What if we have to place at least one ball, or can
place at most one ball, into each urn?



The twelve cases resulting from
exhaustively considering these options are collectively referred to as
the twelvefold way, an account of which can be found in Section 1.4 of
Richard Stanley's <cit.> excellent Enumerative Combinatorics, Volume 1. He
attributes the idea of the twelvefold way to Gian-Carlo Rota and its name to
Joel Spencer.


Stanley presents the twelvefold way in terms of counting functions,
f:U→ V, between two finite sets. If we think of U as a set of
balls and V as a set of urns, then requiring that each urn contains
at least one ball is the same as requiring that f is surjective, and
requiring that each urn contain at most one ball is the same as
requiring that f is injective. To say that the balls are identical, or
that the urns are identical, is to consider the equality of such
functions up to a permutation of the elements of U, or up to a
permutation of the elements of V.

We provide a uniform treatment of the twelvefold way, as well as some
extensions of it, using Joyal's theory of combinatorial species, and in
doing so we will endeavor to give an accessible introduction to this
beautiful theory. Section <ref> contains this
introduction to species and it is based on two articles of
Joyal <cit.> and the book Combinatorial species and
tree-like structures by Bergeron, Labelle, and
Leroux <cit.>. In Section <ref> we give
the species interpretation of the twelvefold way.

combinatorial-species


§ COMBINATORIAL SPECIES


Before defining what a
combinatorial species is we shall consider simple graphs as a motivating
example.

A simple undirected (labeled) graph is a pair (U,E), where U is
a set of vertices and E is a set of edges, which are 2-element
subsets of U. For instance, the graph with vertex set
U = {a,b,c,d,e} and edge set
E = {{c,b}, {b,d}, {d,a}, {a,e}, {d,e}} is
depicted here:

    [semithick, scale=0.9]
        [every node/.style=circle,draw,fill=black,minimum size=3.5pt,inner sep=0pt]
           [label=[yshift=2pt]c] (A) at (0,0.5) ;
           [label=[yshift=2pt]b] (B) at (1,0.5) ;
           [label=[yshift=2pt]d] (C) at (2,0.5) ;
           [label=[xshift=8pt, yshift=-7pt]e] (D) at (3,0) ;
           [label=[xshift=8pt, yshift=-6pt]a] (E) at (3,1) ;
           (A) – (B) – (C) – (D) – (E) – (C);

Informally, a graph in which vertices are indistinguishable is said
to be unlabeled:

    [semithick, scale=0.9]
        [every node/.style=circle,draw,fill=black,minimum size=3.5pt,inner sep=0pt]
           [label=[text=white, yshift=2pt]c] (A) at (0,0.5) ;
           [label=[text=white, yshift=2pt]b] (B) at (1,0.5) ;
           [label=[text=white, yshift=2pt]d] (C) at (2,0.5) ;
           [label=[text=white, xshift=8pt, yshift=-7pt]e] (D) at (3,0) ;
           [label=[text=white, xshift=8pt, yshift=-6pt]a] (E) at (3,1) ;
           (A) – (B) – (C) – (D) – (E) – (C);

Formally, an isomorphism of graphs (U, E) and (V,E')
is a bijection σ:U→ V that preserves the adjacency relation:
{x,y}∈ E if and only if {σ(x), σ(y)}∈ E'.
Then an unlabeled graph is an isomorphism class.

A species defines not only a class of (labeled) combinatorial objects
but also how those objects are affected by relabeling. This mechanism is
called transport of structure. In particular, a species carries the
necessary information for defining the unlabeled counterpart of itself.

For graphs one defines [U] as the set of graphs on the finite set
U, and for a bijection σ: U→ V one defines the transport
of structure, [σ]:[U]→[V], by
[σ](U,E) = (V,σ(E)), where
σ(E) = {{σ(x),σ(y)}: {x,y}∈ E }.
For instance, if
σ = ([ a b c d e; 3 1 4 5 2 ])
is the bijection from U={a,b,c,d} to V={1,2,3,4} mapping a to 3, b to 1, etc.,
then

    [scale=0.95]
        [semithick, every node/.style=circle,draw,fill=black,minimum size=3.5pt,inner sep=0pt]
           [label=[yshift=2pt]c] (A) at (0,0.5) ;
           [label=[yshift=2pt]b] (B) at (1,0.5) ;
           [label=[yshift=2pt]d] (C) at (2,0.5) ;
           [label=[xshift=8pt, yshift=-7pt]e] (D) at (3,0) ;
           [label=[xshift=8pt, yshift=-6pt]a] (E) at (3,1) ;
           (A) – (B) – (C) – (D) – (E) – (C);
        [semithick, xshift=30,yshift=-45,every node/.style=circle,draw,fill=black,minimum size=3.5pt,inner sep=0pt]
           [label=[yshift=-16pt]4] (a) at (0,0.5) ;
           [label=[yshift=-16pt]1] (b) at (1,0.5) ;
           [label=[yshift=-16pt]5] (c) at (2,0.5) ;
           [label=[xshift=8pt, yshift=-7pt]2] (d) at (3,0) ;
           [label=[xshift=8pt, yshift=-6pt]3] (e) at (3,1) ;
           (a) – (b) – (c) – (d) – (e) – (c);
        [thin, decoration=
            markings,
            mark=at position 0.5 with >
          ]
          [dashed, postaction=decorate] (A) – (a);
          [dashed, postaction=decorate] (B) – (b);
          [dashed, postaction=decorate] (C) – (c);
          [dashed, postaction=decorate] (E) – (e);
           at (0.0,-0.5) [σ];
        [thin, dashed, decoration=
            markings,
            mark=at position 0.4 with >,
            postaction=decorate
          ] (D) – (d);

In terms of transport of structure, two graphs s∈[U] and
t∈[V] are isomorphic if there is a bijection σ:U→ V
such that [σ](s) = t.

It is easy to check that for all bijections σ: U→ V and
τ: V → W we have
[σ∘τ] = [σ]∘[τ]. And, for the
identity _U:U→ U, it holds that [_U] = _[U].

A species is a rule which



  * produces, for each finite set U, a finite set F[U];

  * produces, for each bijection σ:U→ V, a function
  F[σ]:F[U]→ F[V].


These data satisfy the following conditions: F[τ∘σ] = F[τ] ∘ F[σ] for
all bijections σ: U→ V and τ: V→ W, and
F[_U] = _F[U] for the identity map _U:U→ U. For
instance,  as defined above is a species.

While this definition of species is adequate, the natural setting for
species is category theory. A category consists of
the following data:


  * A collection of objects: U, V, W, …
  * A collection of arrows: σ, τ, ρ, …,
  each having a domain and a codomain; writing
  σ: U→ V we express that U is the domain and V is the
  codomain of σ.

  * For each pair of arrows σ: U→ V and τ: V→ W, a
  composite arrow τ∘σ:U→ W.

  * For each object U, an identity arrow _U:U→ U.


These data satisfy the following axioms:



  * Associativity: for σ and τ as above and ρ an
  arrow with domain W we have
  ρ∘ (τ∘σ) = (ρ∘τ)∘σ.

  * Identity laws: for σ as above,
  σ∘_U = σ = _V ∘σ.


Let us now give three examples of categories, the latter two of which
are essential to the definition of a species. The category  has
sets as objects and functions as arrows; the identity arrow _U is
the identity function on U. The category  is defined
similarly but has only finite sets as objects.  The category
 has finite sets as objects and bijections as arrows.

Morphisms of categories are called a functors. Eilenberg and Mac
Lane stress their importance in General theory of
natural equivalences <cit.>:


It should be observed first that the whole concept of a category is
essentially an auxiliary one; our basic concepts are essentially those
of a functor and of a natural transformation [ …]


The definition goes as follows: Let  and  be categories. A
functor F:→ is a mapping of objects to objects and
arrows to arrows such that



  * If σ:U→ V then F[σ]:F[U]→ F[V];

  * F[τ∘σ] = F[τ]∘ F[σ];

  * F[_U]=_F[U].


Armed with these notions from category theory a species is simply
a functor F:→. This definition was first given
by Joyal in 1981 <cit.>. An element s∈ F[U] is called an
F-structure on U. Note that if F is a species and
σ:U→ V is a bijection, then
_F[U] = F[_U] = F[σ^-1∘σ] = F[σ^-1]∘ F[σ]
and, similarly, _F[V] = F[σ]∘ F[σ^-1]. Thus,
the transport of structure is always a bijection and a species can also
be regarded as a functor →. In particular,
if U and V are two finite sets of the same cardinality
|U|=|V|, and σ:U→ V is a bijection witnessing this, then
F[σ]:F[U]→ F[V] is a bijection, proving that
|F[U]|=|F[V]|. In other words, the number of F-structures on
U only depends on the number of elements of U.

For ease of notation, we write F[n] for F[[n]], the set of
F-structures on [n]={1,2,…,n}. The generating
series of F is the formal power series

    F(x) = ∑_n≥ 0 |F[n]|x^n/n!.

Two F-structures s∈ F[U] and t∈ F[V] are
isomorphic, and we write s∼ t, if there is a bijection
σ:U→ V such that F[σ](s) = t. Let F[U]/∼
denote the set of equivalence classes under this relation. An unlabeled
F-structure is then simply a member of F[U]/∼. Two
isomorphic F-structures are also said to have the same
isomorphism type and the type generating series of F
is

    F(x) = ∑_n≥ 0 |F[n]/∼|x^n.





We have only seen one concrete species so far, that of simple graphs. Another
example is the species L of linear orders. For a finite set U
with n elements, let L[U] consist of all bijections
f:[n]→ U. For instance, if we represent f by its images
f(1)f(2)… f(n) then L[3]={123,132,213,231,312,321}.
Transport of structure is defined by L[σ](f) = σ∘ f,
or in terms of images
L[σ](f(1)… f(n)) = σ(f(1))…σ(f(n)). Clearly,
there are n! linear orders on [n]. Thus |L[n]|=n! and
L(x) = 1/(1-x). Any two linear orders f,g∈ L[U] are isomorphic.
Indeed, σ = g∘ f defines a bijection from U to U
and g = L[σ](f). Thus |L[n]/∼|=1 and
L(x) = 1/(1-x).

Let E be the species of sets. It is defined by E[U]={U} and,
for bijections σ:U→ V, E[σ](U)=V. That is, for any
finite set U there is exactly one E-structure, the set U
itself. Thus E(x)=e^x and E(x)=1/(1-x).

We can build new species from existing species using certain operations.
The simplest operation is addition, which is just disjoint union. An
(F+G)-structure is thus either an F-structure or a
G-structure:

    [semithick, scale=0.7]
        [rounded corners] (0,0) rectangle (3,2);
        / in
          0.35/1.64,0.26/0.3,0.9/1.7,1.16/0.3,0.4/1,2.4/1.2,2.0/1.7,2.3/0.4,2.6/0.45[black!40!green] (,) circle (1.4pt);
        ;
         at (1.5,1) F+G;
         at (3.5,1) =;
        / in
          0.35/1.64,0.26/0.3,0.9/1.7,1.16/0.3,0.4/1,2.4/1.2,2.0/1.7,2.3/0.4,2.6/0.45[black!40!green] (4+,) circle (1.4pt);
        ;
         at (5.5,1) F;
        [rounded corners] (4,0) rectangle +(3,2);
         at (7.5,1) or;
        / in
          0.35/1.64,0.26/0.3,0.9/1.7,1.16/0.3,0.4/1,2.4/1.2,2.0/1.7,2.3/0.4,2.6/0.45[black!40!green] (8+,) circle (1.4pt);
        ;
         at (9.5,1) G;
        [rounded corners] (8,0) rectangle +(3,2);

That is, for any finite set U we define
(F+G)[U] = F[U] ⊔ G[U]. For any bijection σ:U→ V,
transport of structure is defined by (F+G)[σ](s) = F[σ](s)
if s∈ F[U] and (F+G)[σ](s) = G[σ](s) if
s∈ G[U].

We can also form the product of two species. An (F· G)-structure
on a set U is a pair (s,t), where s is an F-structure on
a subset U_1 of U and t is a G-structure on the
remaining elements U_2=U∖ U_1:

    [semithick, scale=0.7]
        [rounded corners] (0,0) rectangle (3,2);
        / in
          0.35/1.64,0.26/0.3,0.9/1.7,1.16/0.3,0.4/1,2.4/1.2,2.0/1.7,2.3/0.4,2.6/0.45[black!40!green] (,) circle (1.4pt);
        ;
         at (1.5,1) F· G;
         at (3.5,1) =;
        / in
          0.35/1.64,0.26/0.3,0.9/1.7,1.16/0.3,0.4/1,2.4/1.2,2.0/1.7,2.3/0.4,2.6/0.45[black!40!green] (4+,) circle (1.4pt);
        ;
         [zigzag] (5.45,0) – (5.7,2);
         at (4.9,1) F;
         at (6.04,1) G;
        [rounded corners] (4,0) rectangle +(3,2);

Formally, (F· G)[U] =  (F[U_1] × G[U_2]) in
which the union is over all pairs (U_1,U_2) such that
U = U_1∪ U_2 and U_1∩ U_2 = ∅. The transport of
structure is defined by
(F· G)[σ](s,t) = (F[σ_1](s), G[σ_2](t)),
where σ_1 = σ|_U_1 is the restriction of σ to
U_1 and σ_2 = σ|_U_2 is the restriction of
σ to U_2.

It is clear that if F and G are species, then
(F+G)(x) = F(x)+G(x). It also holds that (FG)(x) = F(x)G(x). To
see this, recall that, for any species F and any finite set U,
the number |F[U]| of F-structures on U only depends on
|U|. Thus, the coefficient in front of x^n/n! in (FG)(x) is

    |(FG)[n]|
        = |_S⊆ [n] F[S] × G[[n]∖ S] |
        = ∑_k=0^nnk|F[k]| |G[n-k]|,

which is also the coefficient in front of x^n/n! in F(x)G(x).
For the type generating series one can similarly show that
(F+G)(x)=F(x)+G(x) and
(FG)(x)=F(x)G(x).

As a simple example, multiplying the set species with itself we get
E^2[U] = {(A, U∖ A): A⊆ U }. This is
called the subset (or power set) species, and is denoted . Note
that (x) = E(x)^2 = e^2x = ∑_n≥ 02^n x^n/n!,
reflecting the elementary fact that there are 2^n subsets of an
n-element set. Also,
(x) = 1/(1-x)^2 = ∑_n≥ 0(n+1)x^n, reflecting that
the isomorphism type of a set is determined by its cardinality
and that an n-element set has subsets of n+1 different cardinalities.


Another, perhaps more interesting, example is that of derangements:
Define the species  of permutations as follows. For any finite
set U, let [U] be the set of bijections f: U→ U; and,
for any bijection σ: U→ V, define the transport of structure
by [σ](f)=σ∘ f∘σ^-1. A
derangement is a permutation without fixed points. Let 
denote the species of derangements, so that
[U] = {f∈[U]: f(x)≠ x for all x∈ U}
with transport of structure defined the same way as for the species
. Note that any permutation on U can be seen as a set of
fixed points on a subset U_1 of U together with a derangement of
the remaining elements U_2=U∖ U_1. This is most apparent
when writing a permutation in disjoint disjoint cycle form. For
instance, the permutation (1)(2  7  3)(4)(5)(6  9)(8) can be
identified with a the pair consisting of the fixed point set
{1,4,5,8} together with the derangement (2  7  3)(6  9).
Thus = E· and (x) = E(x)(x). It
immediately follows that 
    (x)
        = (x)· E(x)^-1   = 1/1-x· e^-x
       =
          ∑_n≥ 0n!(1 - 1/1! + 1/2! - … + (-1)^n/n!)x^n/n!.
 In particular, |Der[n]|/n! → e^-1 as
n→∞, which the reader may recognize as the answer to
Montmort's (1713) hat-check problem <cit.>.

Define the singleton species X by X[U] = {U} if |U|=1 and
X[U] = ∅ otherwise. Similarly, define the species 1,
characteristic of the empty set, by 1[U] = {U} if U=∅
and 1[U] = ∅ otherwise. The combinatorial equality
L=1+XL informally states that a linear order is either empty or it
consists of a first element together with the remaining elements. A
computer scientist would recognize this as the same recursive pattern as
in the definition of a singly linked list of nodes: it is either the
null reference or it is a pair consisting of a data element and a
reference to the next node in the list. To make formal sense of this
combinatorial equality we first need to define what it means
for two species to be equal.

Two species F and G are (combinatorially) equal if there
is a family of bijections α_U:F[U]→ G[U] such that for any
bijection σ:U→ V the diagram

    [semithick]
         (m) [matrix of math nodes, row sep=4em, column sep=6em]
         F[U]     G[U] 
    
          F[V]     G[V] 
    ;
        [->,font=]
          (m-1-1) edge node[above] α_U (m-1-2)
                  edge node[left]  F[σ] (m-2-1)
          (m-2-1) edge node[above] α_V (m-2-2)
          (m-1-2) edge node[right] G[σ] (m-2-2);

commutes. That is, for any F-structure s on U we have
G[σ](α_U(s)) = α_V(F[σ](s)). In category theory
this is called natural isomorphism of functors.

To prove that L=1+XL we define the family of bijections
α_U:L[U]→ (1+XL)[U] by α_∅() = ∅
and α_U(a_1 a_2 ⋯ a_n) = (a_1,  a_2⋯ a_n) for
U≠∅. In the case U=∅ the diagram above
trivially commutes and for any nonempty finite set U we have

    [semithick]
         (m) [matrix of math nodes, row sep=3em, column sep=4em, minimum height=2em]
          a_1 a_2 ⋯ a_n     (a_1,  a_2⋯ a_n) 
    σ(a_1)σ(a_2)⋯σ(a_n)
              (σ(a_1), σ(a_2)⋯σ(a_n)) 
    ;
        [->,font=]
          (m-1-1) edge[|->] node[above] α_U (m-1-2)
                  edge[|->] node[left=3pt] L[σ] (m-2-1)
          (m-2-1) edge[|->] node[above] α_V (m-2-2)
          (m-1-2) edge[|->] node[right=3pt] (1+XL)[σ] (m-2-2);

which concludes the proof of L = 1+XL. From this it immediately
follows that L(x) = 1 + xL(x) and we rediscover the identity
L(x) = 1/(1-x). Similarly, L(x) = 1 + xL(x) and we
also rediscover that L(x) = 1/(1-x).

Next we shall define substitution of species. As a motivating example,
consider the species  of permutations. For instance,
(1  7)(2  8  3  4)(5  9)(6) is an element of [9]
written in disjoint cycle form. Here we have listed the cycles in
increasing order with respect to the smallest element in each cycle, but
this is just a convention; since the cycles are disjoint they commute
and we may list them in any order. In other words, any permutation can
be represented by a set of cycles. Using species this can be
expressed as = E∘ = E(), in which a
-structure is a permutation with a single
cycle.

Another example of substitution of species is that of set partitions;
this species is denoted . Define E_+ as the species of
nonempty sets, so that E=1+E_+. Then = E(E_+), which we can
read as stating that a partition is a set of nonempty sets. Similarly,
the species of ballots, also called ordered set partitions, is
defined by = L(E_+).

In general, we can think of an F(G)-structure as a generalized
partition in which each block of the partition carries a
G-structure, and the blocks are structured by F:

    [semithick, scale=0.8]
        [rounded corners] (0,0) rectangle (3,2);
        / in
          0.35/1.64,0.26/0.3,0.9/1.7,1.16/0.3,0.4/1,2.4/1.2,2.0/1.7,2.3/0.4,2.6/0.45[black!40!green] (,) circle (1.4pt);
        ;
         at (1.5,1) F∘ G;
         at (3.5,1) =;
        / in
          0.35/1.64,0.26/0.3,0.9/1.7,1.16/0.3,0.4/1,2.4/1.2,2.0/1.7,2.3/0.4,2.6/0.45[black!40!green] (4+,) circle (1.4pt);
        ;
         [zigzag] (5.45,0) – (5.85,2);
         [zigzag] (4,0.44) – (5.7,1.5);
         [zigzag] (5.65,1.07) – (7,0.8);
         at (4.65,1.33) G;
         at (4.78,0.55) G;
         at (6.60,1.6) G;
         at (6.00,0.4) G;
         at (5.50,1.14) F;
        [rounded corners] (4,0) rectangle +(3,2);

Formally, we define the substitution of G in F, also
called partitional composition, as follows. For species F and
G, with G[∅]=∅,

    (F∘ G)[U]  =
      _β = {B_1,B_2,…,B_k}
    partition of U
      F[β]× G[B_1]× G[B_2] ×⋯× G[B_k].

Transport of structure is defined in a natural way, but there are
quite a few details to keep track of. To a first approximation, an
(F∘ G)-structure on U is a tuple (s,t_1,…,t_k),
where s∈ F[β] and t_i∈ G[B_i]. To guarantee that the
union is disjoint we will, however, also “tag” these tuples with their
associated set partition. Hence a typical (F∘ G)-structure is of
the form (β,s,t_1,…,t_k).
To describe the image of this tuple under the transport of structure we
first need some auxiliary definitions.  Assume that σ:U→ V is a
bijection.  Let β̅={B̅_1,…,B̅_k} be the set
partition of V obtained from β by transport of structure. That is, with
σ̅= [σ] we have β̅=σ̅(β). Further, let
s̅ = F[σ̅](s)∈ F[β̅] and
t̅_i = G[σ_i](t_i)∈ G[B̅_i], where
σ_i = σ|_B_i is the restriction of σ to the block
B_i. Then

    (β̅,s̅,t̅_1,…,t̅_k) = (F∘ G)[σ](β,s,t_1,…,t_k).



Concerning generating series, one can show that F(G)(x)=F(G(x)). As
an example, recall that = E∘ and hence
(x) = exp((x)). Thus

    (x) = log((x)) = log (1-x)^-1
    = ∑_n≥ 1x^n/n
    = ∑_n≥ 1 (n-1)!x^n/n!,

which is unsurprising since there clearly are (n-1)! ways to make a
cycle using n distinct elements.

For type generating series the situation is more complicated. The
series F(G)(x) is, as a rule, different from
F(G(x)). To state the true relation between these
entities a more general generating series is needed. The cycle
index series for a species F is defined by 
    Z_F(x_1,x_2,x_3,…) =
        ∑_n≥ 0 1/n!∑_σ∈[n]| F[σ]| 
          x_1^c_1(σ)x_2^c_2(σ)x_3^c_3(σ)⋯
 where
F[σ] = { s ∈ F[n]: F[σ](s) = s } is the set of
F-structures on [n] fixed by F[σ], and c_i(σ)
denotes the number of cycles of length i in σ. To
illustrate this definition we give three examples:

Example 1. Consider the species X of singletons. The fixed
point set X[σ] is empty unless n=1 and there is only
one permutation on [1]={1}, the identity, so the cycle index
series consists of a single term:

    Z_X(x_1, x_2, …)
           = | X[_1]| x_1^c_1(_1) x_2^c_2(_1)… = x_1.


Example 2. For any species F we denote by F_n the
restriction of F to sets of cardinality n. In other words,
F_n[U] = F[U] if |U|=n and F_n[U] = ∅ otherwise.
With this notation the singleton species X is identical to the
species E_1. Let us now calculate the cycle index series for
E_2, the species of sets of cardinality 2:

    Z_E_2(x_1, x_2, …)
           = 1/2(| E_2[_2]| x_1^c_1(_2) x_2^c_2(_2) +
           | E_2[(1 2)]| x_1^c_1(1 2) x_2^c_2(1 2)) 
       = 1/2(x_1^2 + x_2).


Example 3. For the species L of linear orders,
L[σ] is empty unless σ is the identity map, in
which case L[σ] = L[n]. Thus

    Z_L(x_1, x_2, …)
           = ∑_n ≥ 01/n!| L[_n]|  x_1^c_1(_n) x_2^c_2(_n)…
       = ∑_n ≥ 01/n!|L[n]| x_1^n = 1/1-x_1.


It should be noted that the cycle index series encompasses both the
generating series and the type generating series of a species. To be
more precise, for any species F,

    F(x) = Z_F(x,0,0,…)   and  F(x) = Z_F(x,x^2,x^3,…).

Let us prove this. For the generating series we have

    Z_F(x,0,0,…)
             = ∑_n ≥ 01/n!(∑_ σ∈[n]
            | F[σ]| x^c_1(σ) 0^c_2(σ) 0^c_3(σ)…)
       = ∑_n ≥ 01/n! | F[_n]| x^n
          = ∑_n ≥ 0 |F[n]| x^n/n!
          = F(x).

For the type generating series we have

    Z_F(x,x^2,x^3,…)
             = ∑_n ≥ 01/n!∑_σ∈𝒮_n | F[σ]| x^c_1(σ)+2c_2(σ)+3c_3(σ)+⋯
       = ∑_n ≥ 01/n!∑_σ∈𝒮_n | F[σ]| x^n
          = ∑_n ≥ 0 |F[n]/∼| x^n = F(x)

by Burnside's lemma.

Further, for species F and G we have Z_F+G = Z_F+ Z_G,
Z_F· G = Z_F · Z_G, and

    Z_F∘ G(x_1, x_2, …) = Z_F(Z_G(x_1,x_2,…), Z_G(x_2,x_4,…), …).

In particular, (F∘ G)(x) = F(G(x)) while
F∘ G(x) = Z_F(G(x), G(x^2), G(x^3), …).
As an example, consider the species F=E_2∘ (X+X^2) and
isomorphism types of F-structures. For each of the sizes 2, 3, and 4
there is exactly one type: using pictures, those are
{∙,∙}, {∙,∙∙}, and
{∙∙,∙∙}. There is no type of any other
size and thus the type generating series is F(x)=x^2+x^3+x^4.
Note that the type generating series for E_2 and X+X^2 are
x^2 and x+x^2, and naively composing them we get
x^2+2x^3+x^4, which is different from F(x). The correct
procedure to calculate F(x) is

    F(x)
         = Z_E_2((X+X^2)(x), (X+X^2)(x^2), …) 
       = Z_E_2(x+x^2, x^2+x^4)
      = 1/2((x+x^2)^2 + x^2+x^4) = x^2+x^3+x^4.


Changing the topic, but continuing with the species
F=E_2∘ (X+X^2), say that we want to refine the count of
F-structures by keeping track of how many ordered pairs, stemming
from the X^2 term, such a structure contains. We can accomplish this
by putting a “weight”, say y, on each X^2-structure. The
type generating series for F would in this case be
x^2 + yx^3 + y^2x^4. Two more
interesting examples of this kind of refinement would be
to count permutations while
keeping track of the number of cycles, or to count trees while keeping
track of the number of leaves. There is a variant of combinatorial
species, called weighted species, that allows us to keep track of
various parameters. Before giving its definition we'll need to introduce
weighted sets and their morphisms.

Let R be a ring. An R-weighted set is a pair (A,w),
where A is a finite set and w:A→ R is a function. We think of
w as assigning a weight to each element of A. A morphism
of R-weighted sets (A,w) and (B,v) is a
weight-preserving function :A→ B; that is,
w = v ∘, or, equivalently, the diagram

    [semithick]
         (m) [matrix of math nodes, row sep=2.5em, column sep=3em]
         A        B 
        R 
    ;
        [->,font=]
          (m-1-1) edge node[auto]  (m-1-3)
          (m-1-1) edge node[below left] w (m-2-2)
          (m-1-3) edge node[below right] v (m-2-2);

commutes. If, in addition, ψ is a morphism of R-weighted
sets from (B,v) to (C,u) then it's easy to check that the
composition ψ∘ is a morphism from (A,w) to
(C,u). The identity map is of course also weight-preserving and so
we have all the ingredients of a category. More generally, given
categories  and , an object D∈ and a functor
F:→, the slice category (F/D) is defined as
follows: Objects are pairs (A,w) with A∈ and w:F[A]→ D
in . Arrows (A,w)→ (A',w') are arrows :A→ A'
making the following diagram commute:

    [semithick]
         (m) [matrix of math nodes, row sep=2.5em, column sep=3em]
         F[A]        F[A'] 
        D    
    ;
        [->,font=]
          (m-1-1) edge node[above] F[] (m-1-3)
          (m-1-1) edge node[below left] w (m-2-2)
          (m-1-3) edge node[below right] w' (m-2-2);

Recall that  is the category of sets and functions and that
 is the category of finite sets and functions.  By slight abuse
of notation, let the inclusion functor from  to  taking
objects and arrows to themselves also be denoted by .  In terms
of the definition of a slice category, let F=, =,
and =. Assuming that we for the moment identify the ring R with its
underlying set, forgetting about the two operations on R, we
also let D=R. Then (/R) is the (slice) category of
R-weighted sets with morphisms of R-weighted sets as arrows, and we
define an R-weighted species as a functor
F:→(/R).

As an example, let us define a [y]-weighted version of the
species  of permutations. Define the weight of f∈[U]
as w_U(f)=y^(f), where (f) denotes the number of
cycles in f, and let _w denote the resulting weighted
species. To be more specific,



  * for any finite set U, let _w[U] be the [y]-weighted
  set ([U], w_U);

  * for any bijection σ:U→ V, let
  _w[σ]:_w[U]→_w[V] be the morphism of
  [y]-weighted sets defined by
  [σ]:[U]→[V].


Recall that the transport of structure [σ] is conjugation
by σ; that is,
[σ](f)=σ∘ f∘σ^-1. It is well known
that two permutations are conjugate if and only if they have the same
cycle structure. In particular, conjugate permutations have the same
number of cycles. Thus, [σ] is weight-preserving, or,
equivalently, the diagram

    [semithick]
         (m) [matrix of math nodes, row sep=2.5em, column sep=3em]
        [U]       [V] 
       [y]    
    ;
        [->,font=]
          (m-1-1) edge node[auto] [σ] (m-1-3)
          (m-1-1) edge node[below left]  w_U (m-2-2)
          (m-1-3) edge node[below right] w_V (m-2-2);

commutes.

For any weighted set (A,w) let |A|_w = ∑_a∈ Aw(a); it's
called the total weight of A. Note that if w is the
trivial weight function, assigning 1 to each element, then
|A|_w=|A|. With this definition in hand, the power series associated
with a weighted species F_w are defined as expected:

    Z_F_w(x_1,x_2,x_3,…)    =
        ∑_n≥ 0 1/n!∑_σ∈[n]| F[σ]|_w 
          x_1^c_1(σ)x_2^c_2(σ)x_3^c_3(σ)⋯, 
    
      F_w(x) = Z_F_w(x,0,0,…)    = ∑_n≥ 0 |F[n]|_wx^n/n!,
    F_w(x) = Z_F_w(x,x^2,x^3,…)    = ∑_n≥ 0 |F[n]/∼|_w x^n,

where |F_w[U]/∼|_w is the total weight of any
member of F_w[U]/∼. Since F_w[σ] is weight-preserving
the choice of representative is immaterial.

It is straightforward to extend addition, multiplication, and
composition to weighted species. All we need to do is define disjoint
union and (Cartesian) product of weighted sets: If (A,w) and
(B,v) are weighted sets, then
(A,w)⊔ (B,v) = (A⊔ B, w⊔ v) and
(A,w)× (B,v) = (A× B, w× v), where (w⊔ v)(x)
is w(x) or v(x) depending on whether x∈ A or x∈ B,
and (w× v)(x,y) = w(x)v(y). With these definitions we have
|A⊔ B|_w⊔ v = |A|_w + |B|_v and
|A× B|_w× v = |A|_w|B|_v.

Returning to the _w example, we find that _w=E(y),
where y is suggestive notation for the weighted species of
cycles in which each cycle is given the weight y. Thus
_w(x)=exp(y(x)) =exp(ylog (1-x)^-1) = (1-x)^-y and
the coefficient in front of y^kx^n/n! in _w(x) is
an unsigned Stirling number of the first kind. That is,

    _w(x) = ∑_n≥ 0(∑_k=1^n c(n,k)y^k)x^n/n!,

where c(n,k) is the number of permutations of [n] with k cycles.


As a more complex example we shall now calculate the cycle index series of
the set species. We have | E[σ]|=1 for every
σ∈[n] and so

    Z_E(x_1,x_2,x_3,…) =
          ∑_n≥ 0 1/n!∑_σ∈[n]x_1^c_1(σ)x_2^c_2(σ)x_3^c_3(σ)⋯

Or, rewriting this slightly,

    Z_E(x_1,x_2,x_3,…) =
        [ ∑_n≥ 0 (
          ∑_σ∈[n]x_1^c_1(σ)x_2^c_2(σ)x_3^c_3(σ)⋯)x^n/n! ]_x=1.

Inside the outermost bracket is an exponential generating series for
permutations in which each cycle of length i carries the weight
x_i. Next, we recast this example in terms of weighted species. Let
_w be the [x_1,x_2,…]-weighted species of
permutations in which
w(σ) = x_1^c_1(σ)x_2^c_2(σ)⋯ for each
permutation σ. Then Z_E(x_1,x_2,…) = _w(1). On
the other hand, we have _w = E(x_1_1 + x_2_2 +⋯) in
which x_i_i is the species of cycles of length i, each with
weight x_i. Thus
_w(x) = exp(x_1x/1+x_2x^2/2+x_3x^3/3 + ⋯)
and setting x=1 we arrive at

    Z_E(x_1,x_2,x_3,…)
        = exp( x_1/1+x_2/2+x_3/3 + ⋯).

Let us use this expression to investigate the type generating series
of the set partition species . The isomorphism type of a set
partition is determined by the sizes of its blocks; those sizes form an
integer partition and hence (x) = ∏_k≥ 1(1-x^k)^-1.
On the other hand, =E(E_+) which in terms of type generating
series means

    (x) = Z_E((x),(x^2),(x^3),…).

Clearly, (x) = x/(1-x) and we arrive at the intriguing
identity

    ∏_k≥ 11/1-x^k
      = exp∑_k≥ 1 1/k x^k/1-x^k.


Let _w be the species of set partitions weighted by the number
of blocks: the weight function w_U:[U]→[y] is defined by
w_U(β)=y^k, where β={B_1,…,B_k} is a partition of
U with k blocks. Then _w = E(yE_+), in which yE_+
denotes the species of nonempty sets each with weight y. Thus
_w(x) = exp(y(e^x-1)), and the coefficient in front of
y^kx^n/n! in _w(x) is a Stirling number of the second kind:

    _w(x) = ∑_n≥ 0(∑_k=1^n S(n,k)y^k)x^n/n!,

where S(n,k) is the number of set partitions of [n] with k blocks.
Transitioning to type generating series we also find that

    ∏_k≥ 11/1-yx^k
      = exp∑_k≥ 1 1/k y^k x^k/1-x^k,

which is a refined generating series for integer partitions in which
y keeps track of the number of parts.

A two-sort species is a functor
F:×→ in which
× denotes a product category. In general,
if  and  are two categories, then × has pairs
(A,B) as objects, where A is an object of  and B is an
object of . Similarly, the arrows are pairs (f,g), where f
and g are arrows of  and , respectively. Composition of
arrows is componentwise and _(A,B) = (_A, _B). We shall
write F(X,Y) to indicate that F is a two-sort species and that
the two sorts are called X and Y. For natural numbers n and
k, let F[n,k] = F[[n],[k]]. We define the generating
series of F by

    F(x,y) = ∑_n,k≥ 0|F[n,k]|  x^n/n!y^k/k!.

Note that any unisort species F can be considered a two-sort
species by specifying of what sort it is: saying that F is a species
of sort X means that, as a two-sort species, F[U,V] = F[U] if
V is empty, and F[U,V]=∅ otherwise. To be a species of
sort Y is interpreted similarly.

Addition and multiplication of species is straightforwardly extended to
the two-sort context. As an example, consider the species
F(X,Y)=(1+X)Y, where X is the species of singletons of sort
X and Y is the species of singletons of sort Y. If
|U|≤ 1 and |V| = 1 then there is exactly one F-structure,
namely the pair (U,V); otherwise, there are no F-structures. For
instance, F[∅,{1}] = {(∅, {1})} and
F[{1,2},V] = ∅. Similarly,

    (E(X)Y)[U,V] =
    {(U,V)}   if |V|=1, 
    ∅   otherwise.


It is less clear how to extend the substitution operation to the
two-sort context and so we detail it here. Let [U,V] denote the
set of partitions of the disjoint union U⊔ V. For instance, if
U={1,2} and V = {a,b,c}, then
π = {{1},{2,a,c},{b}} is a member of
[U,V]. In the definition of F(G,H) below, we view a block B
of such a partition as a pair of sets (S,T), where
S=B∩ U ⊆ U and T=B∩ V⊆ V. Thus, the blocks
of the example partition, π, will be viewed as the pairs
({1}, ∅), ({2}, {a,c}), and (∅,{b}).
We are now in a position to define the substitution of G and H
in F, also called partitional composition. Let F(X,Y),
G(X,Y), and H(X,Y) be two-sort species. Then

    F(G,H)  = _π ∈ [U,V] 
    κ: π → {X,Y} F[β,γ]
           × G[B_1]×…× G[B_k]
           × H[C_1]×…× H[C_ℓ],

in which β = {B_1,…,B_k} = κ^-1(X) and
γ = {C_1,…,C_ℓ} = κ^-1(Y). Here we can think of
κ as assigning one of two colors to each block of π; the
partition β consists of the X-colored blocks, and γ
consists of the Y-colored blocks. Intuitively, an
F(G,H)-structure is obtained from an F-structure by inflating
each element of sort X into a G-structure and each element of
sort Y into an H-structure.

Let us now consider the species Φ(X,Y) whose structures on
(U,V) are all functions f:U→ V, and whose transport of
structure is defined by
Φ[σ, τ](f)=τ∘ f∘σ^-1.
We shall prove the combinatorial equality Φ(X,Y)=E(E(X)Y). Let
Ψ(X,Y)=E(E(X)Y) denote the right-hand side and define
α_UV:Φ[U,V]→Ψ[U,V] by

    α_UV(f) = {(f^-1(v), v): v∈ V }.

To show that Φ(X,Y)=Ψ(X,Y) then amounts to proving that, for any pair
of bijections σ:U→ U' and τ:V→ V', the diagram

    [semithick]
         (m) [matrix of math nodes, row sep=4em, column sep=6em]
        Φ[U,V]    Ψ[U,V] 
    Φ[U',V']    Ψ[U',V'] 
    ;
        [->,font=]
          (m-1-1) edge node[auto] α_UV (m-1-2)
                  edge node[left] Φ[σ,τ] (m-2-1)
          (m-2-1) edge node[auto] α_U'V' (m-2-2)
          (m-1-2) edge node[auto] Ψ[σ,τ] (m-2-2);

commutes. By direct calculation we have

    Ψ[σ,τ](α_UV(f))
           = {((σ∘ f^-1)(v), τ(v)): v∈ V };
    α_U'V'(Φ[σ,τ](f))
           = {((σ∘ f^-1∘τ^-1)(v), v): v∈ V' }.

Since τ is a bijection these two sets are clearly equal.

Let F(X,Y) be a two-sort species. Two F-structures
s∈ F[U,V] and t∈ F[U',V'] are said to have the same
isomorphism type, and one writes s ∼ t, if there are
bijections σ: U→ U' and τ: V→ V' such that
F[σ,τ](s) = t. The type generating series of F(X,Y) is

    F(x,y) = ∑_n,k≥ 0|F[n,k]/∼|  x^n y^k,

where F[n,k]/∼ denotes the set of equivalence classes of
F[n,k] with respect to ∼.

Two F-structures s∈ F[U,V] and t∈ F[U',V'] are said to
have the same isomorphism type according to the sort X, and
one writes s ∼_X t, if V=V' and there is a bijection
σ:U→ U' such that F[σ, _V](s) = t. Similarly,
s and t are said to have the same isomorphism type
according to the sort Y, and one writes s ∼_Y t, if U=U'
and there is a bijection τ:V→ V' such that
F[_U,τ](s) = t. It's easy to see that
∼_X∘∼_Y=∼=∼_Y∘∼_X, in which the circle denotes
composition of relations, and thus ∼_X and ∼_Y refine (factor) ∼ in
a natural way.
Define s = { t : t∼_X s } and
s = { t : t∼_Y s } as the equivalence classes of s
with respect to ∼_X and ∼_Y.

As an example, let us revisit the species Φ(X,Y) of
functions f:U→ V. For f∈Φ[U,V] and g∈Φ[U',V] we have

  g∼_X f
     Φ[σ, _V](g) = f          for some bijection  σ:U→U' 

     g = f∘σ         for some bijection  σ:U→U'.

To be even more concrete, let U=V={1,2,3} and represent
f∈Φ[U,V] by f(1)f(2)f(3). As we have just seen, g∼_X f in
Φ[U,V] precisely when f and g are equal up to a permutation of U. Thus
the set of equivalence classes of Φ[U,V] with respect to ∼_X
is

    {111, 112, 113, 122, 123, 
    133, 222, 223, 233, 333},

where we have chosen the lexicographically smallest representative for
each equivalence class. Why are there 10 equivalence classes in this
case? Well, up to a permutation of U, a function from U to
V={1,2,3} is determined by the number of elements, x_i, that f
maps to i∈ V. Every element of U has to be mapped to exactly one
element of V and thus x_1+x_2+x_3=|U|=3. From elementary
combinatorics we know that the number of nonnegative solutions to this
equation is |U|+|V|-1|U|=53=10.

For f∈Φ[U,V] and g∈Φ[U,V'], we have

  g∼_Y f
     Φ[_U,τ](g) = f          for some bijection  τ:V→V' 

     τ∘g = f                  for some bijection  τ:V→V'.

In particular, if V=V' then f∼_Y g precisely when f and g are
equal up to a permutation of V. Now, up to a permutation of V, a
function f∈Φ[U,V] is determined by the set of its nonempty
fibres { f^-1(v): v∈ f(U)}, sometimes called the coimage of
f. This set forms a partition of U into at most |V| blocks and hence the
number of equivalence classes of Φ[U,V] with respect to ∼_Y is
S(n,0)+S(n,1)+⋯+S(n,k), where n=|U| and k=|V|.  If
U=V={1,2,3}, then the S(3,1)+S(3,2)+S(3,3)=1+3+1=5 equivalence classes
are 111, 112, 121, 122, and 123.

We now continue our development of the general framework.
Following Joyal <cit.> we shall use the notation

    _U F[U,V]     = { s : s∈ F[U,V] for some finite set U }; 
    _V F[U,V]     = { s : s∈ F[U,V] for some finite set V }.

We would like to define a unisort “species of types” whose
structures are precisely the elements of _UF[U,V]. This
doesn't, however, quite fit our current species framework, the reason
being that the set _UF[U,V] could be infinite. For
instance, consider (again) the species Φ(X,Y) of functions
f:U→ V. For any nonempty finite sets U and V, both
_UΦ[U,V] and _VΦ[U,V] are infinite.
Indeed, if for simplicity we assume that V={v} is a singleton,
then _UΦ[U,V] contains one element per positive size of
the domain:

    [semithick,baseline=(x.base),xscale=0.65, yscale=0.85]
        [thin, rounded corners] (-0.7, 0.5) rectangle ++(3.4,-1.3);
        [rounded corners] (-0.4, 0.3) rectangle ++(0.8,-0.9);
        [rounded corners] ( 1.6, 0.3) rectangle ++(0.8,-0.9);
        [fill, circle, inner sep=1.4pt] (x) at (0,0) ;
        [draw, circle, inner sep=1.4pt, label=below:v] (y) at (2, 0) ;
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (x) – (y);
          [semithick,baseline=(x.base),xscale=0.65, yscale=0.85]
        [thin, rounded corners] (-0.7, 0.5) rectangle ++(3.4,-1.5);
        [rounded corners] (-0.4, 0.3) rectangle ++(0.8,-1.1);
        [rounded corners] ( 1.6, 0.3) rectangle ++(0.8,-1.1);
        [fill, circle, inner sep=1.4pt] (x1) at (0,0) ;
        [fill, circle, inner sep=1.4pt] (x2) at (0,-0.4) ;
        [draw, circle, inner sep=1.4pt, label=below:v] (y) at (2, 0) ;
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (x1) – (y);
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (x2) – (y);
          [semithick,baseline=(x.base),xscale=0.65, yscale=0.85]
        [thin, rounded corners] (-0.7, 0.5) rectangle ++(3.4,-1.65);
        [rounded corners] (-0.4, 0.3) rectangle ++(0.8,-1.25);
        [rounded corners] ( 1.6, 0.3) rectangle ++(0.8,-1.25);
        [fill, circle, inner sep=1.4pt] (x1) at (0,0) ;
        [fill, circle, inner sep=1.4pt] (x2) at (0,-0.3) ;
        [fill, circle, inner sep=1.4pt] (x3) at (0,-0.6) ;
        [draw, circle, inner sep=1.4pt, label=below:v] (y) at (2, 0) ;
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (x1) – (y);
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (x2) – (y);
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (x3) – (y);
          -2.5pt⋯

Similarly, if U={u} is a singleton, then
_VΦ[U,V] contains one element per positive size of the
codomain:

    [semithick,baseline=(x.base),xscale=0.65, yscale=0.85]
        [thin, rounded corners] (-0.7, 0.5) rectangle ++(3.4,-1.3);
        [rounded corners] (-0.4, 0.3) rectangle ++(0.8,-0.9);
        [rounded corners] ( 1.6, 0.3) rectangle ++(0.8,-0.9);
        [fill, circle, inner sep=1.4pt, label=below:u] (x) at (0,0) ;
        [draw, circle, inner sep=1.4pt] (y) at (2, 0) ;
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (x) – (y);
          [semithick,baseline=(x.base),xscale=0.65, yscale=0.85]
        [thin, rounded corners] (-0.7, 0.5) rectangle ++(3.4,-1.5);
        [rounded corners] (-0.4, 0.3) rectangle ++(0.8,-1.1);
        [rounded corners] ( 1.6, 0.3) rectangle ++(0.8,-1.1);
        [fill, circle, inner sep=1.4pt, label=below:u] (x) at (0,0) ;
        [draw, circle, inner sep=1.4pt] (y) at (2, 0) ;
        [draw, circle, inner sep=1.4pt]     at (2,-0.4) ;
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (x) – (y);
          [semithick,baseline=(x.base),xscale=0.65, yscale=0.85]
        [thin, rounded corners] (-0.7, 0.5) rectangle ++(3.4,-1.65);
        [rounded corners] (-0.4, 0.3) rectangle ++(0.8,-1.25);
        [rounded corners] ( 1.6, 0.3) rectangle ++(0.8,-1.25);
        [fill, circle, inner sep=1.4pt, label=below:u] (x) at (0,0) ;
        [draw, circle, inner sep=1.4pt] (y) at (2, 0) ;
        [draw, circle, inner sep=1.4pt]     at (2,-0.3) ;
        [draw, circle, inner sep=1.4pt]     at (2,-0.6) ;
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (x) – (y);
          -2.5pt⋯

We'll handle this using weighted species, but first we need to
generalize the notion of an R-weighted species. Recall that we
defined an R-weighted set to be a pair (A,w), where A is a
finite set and w:A→ R. Let us say that (A,w) is a
summable R-weighted set if A is a (possibly infinite) set,
w:A→ R, and the total weight |A|_w = ∑_a∈ Aw(a) exists.
Then an R-weighted species is a functor
F:→(/R), where (/R) is the category of
summable R-weighted sets with morphisms of R-weighted sets as
arrows.

We are now ready to define the desired species of types. For any two-sort
species F(X,Y) we define the [[x]]-weighted species
_UF[U,Y) as follows: For any finite set V, let the
collection of structures on V be the summable [[x]]-weighted
set (_UF[U,V], w ),
where for any s in F[U, V] the weight of s in _UF[U,V] is w(s)=x^|U|.
For any bijection τ:V→ V', define the
transport of structure _UF[U,τ] as the map

    [ s ]_X  ⟼ [ F[_U,τ](s) ]_X,

which is clearly weight-preserving. The resulting species,
_UF[U,Y), is called the species of types according to
X; the species _VF(X,V] of types according to Y is
defined analogously. We'll use the following notation for their generating series:

    _U F[U,y)
         = ∑_n,k≥ 0| F[n,k]/∼_X | x^ny^k/k!,
    _V F(x,V]
         = ∑_n,k≥ 0| F[n,k]/∼_Y | x^n/n!y^k,

where F[U,V]/∼_X = {s: s∈ F[U,V] } and
F[U,V]/∼_Y = {s: s∈ F[U,V] } are the sets of
equivalence classes with respect to the relations ∼_X and
∼_Y. Let us briefly return to the Φ(X,Y) species for an example. We
discussed the equivalence classes of Φ[U,V] with respect to
∼_X and ∼_Y in some detail above, and from that discussion it
is clear that

    _U Φ[U,y)
              = ∑_n,k≥ 0n+k-1n x^ny^k/k!; 
    _V Φ(x,V]
             = ∑_n,k≥ 0(S(n,0)+⋯+S(n,k)) x^n/n!y^k.


The cycle index series for a two-sort species F(X,Y) is defined by

    Z_F(x_1,x_2,…;y_1,y_2,…) =
        ∑_n≥ 0
     k≥ 0 1/n!k!∑_σ∈[n]
    τ∈[k]| F[σ,τ]| 
          x_1^c_1(σ)x_2^c_2(σ)⋯  y_1^c_1(τ)y_2^c_2(τ)⋯
 One can show that if F(X,Y), G(X,Y), and
H(X,Y) are two-sort species, then Z_F+G=Z_F+Z_G,
Z_FG=Z_F Z_G, and

    Z_F(G,H)( x_1,x_2,x_3…;  y_1,y_2,y_3… ) = 
    =0.9pt
          [ Z_F( Z_G(      x_1,      x_2,       x_3       …),  Z_G(x_2,      x_4,   x_6,…),  Z_G(x_3,      x_6,      x_9,   …), … ;;      Z_H(      y_1,      y_2,       y_3       …),  Z_H(y_2,      y_4,   y_6,…),  Z_H(y_3,      y_6,      y_9,   …), … ) ]

The major generating series associated with a two-sort
species relate to the cycle index series as follows:

    =1.3pt
    [       F(x,y)            =         Z_F(  x, 0, 0, 0,            …            ;  y, 0, 0, 0,            …           );;    _U F[U,y)            =         Z_F( x, x^2, x^3,            …            ;  y, 0, 0, 0,            …           );;     _VF(x,V]            =         Z_F(  x, 0, 0, 0,            …            ; y, y^2, y^3,            …           );;       F(x,y)            =         Z_F( x, x^2, x^3,            …            ; y, y^2, y^3,            …           ). ]


the-twelvefold-way


§ THE TWELVEFOLD WAY


Let R(X) be a unisort species and consider the two-sort species

    (X,Y) = E(R(X) Y)

of functions with R-enriched fibres <cit.>:
    [semithick, scale=0.85]
        [rounded corners] (0,0) rectangle +(2,4);
         [zigzag] (0,1.00) – (2,1.25);
         [zigzag] (0,2.80) – (2,2.70);
        [rounded corners] (3.5,0) rectangle +(1.5,4);
         (R1) at (0.75,0.5) R(X);
         (R2) at (0.75,1.8) R(X);
         (R3) at (0.75,3.3) R(X);
        [draw, circle, inner sep=1.4pt] (Y1) at (4.1,0.7) ;
         at (4.5,0.7) Y;
        [draw, circle, inner sep=1.4pt] (Y2) at (4.1,1.95) ;
         at (4.5,1.9) Y;
        [draw, circle, inner sep=1.4pt] (Y3) at (4.1,3.2) ;
         at (4.5,3.2) Y;
        [fill, circle, inner sep=1.4pt] (r11) at (1.5,0.5) ;
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (r11) – (Y1);
        [fill, circle, inner sep=1.4pt] (r21) at (1.1,2.30) ;
        [fill, circle, inner sep=1.4pt] (r22) at (1.4,1.59) ;
        [fill, circle, inner sep=1.4pt] (r23) at (1.7,1.95) ;
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (r21) – (Y2);
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (r22) – (Y2);
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (r23) – (Y2);
        [fill, circle, inner sep=1.4pt] (r31) at (1.5,3.55) ;
        [fill, circle, inner sep=1.4pt] (r32) at (1.6,3.10) ;
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (r31) – (Y3);
        [postaction=decorate,decoration=markings,mark=at position 0.5 with >] (r32) – (Y3);

Note that if R(X)=E(X) is the set species, then (X,Y)=Φ(X,Y) is
the species of all functions f:U→ V from above. If R(X)=E_+(X) is the
species of nonempty sets, then we are requiring that each fibre
f^-1(v) = {u∈ U: f(u) = v} is nonempty, and so f is
surjective. If R(X)=1+X, then each fibre is empty or a singleton, and we
get injective functions.


  Let (X,Y) = E(R(X)Y) be as above. Then
  
    (x,y)    = exp( yR(x) ); 
       = exp(yR(x)); 
       = exp( y(R(x)-R(0)))(1-y)^-R(0); 
    (x,y)    = exp∑_k≥ 1y^k/kR(x^k).



  The first equality is immediate. Calculating the cycle index series we find that
  
    Z_(x_1,x_2,x_3,…;y_1,y_2,y_3,…) =
        exp∑_k≥ 1y_k/k Z_R(x_k,x_2k,x_3k,…)

  and the remaining three identities follow from calculating
  Z_(x,x^2,x^3,…;y,0,0,0,…),
  Z_(x,0,0,0,…;y,y^2,y^3,…), and
  Z_(x,x^2,x^3,…;y,y^2,y^3,…).  Let us do the second
  of these three calculations. By isolating the first term in the sum on
  the right-hand side of (<ref>) it follows that
  
    = Z_(x,0,0,0,…;y,y^2,y^3,…) 
       = exp(
          yZ_R(x,0,0,…) +
          ∑_k≥ 2y^k/k Z_R(0,0,0,…)
          ).

  Since R(x) = Z_R(x,0,0,…) this can be further simplified as
  follows:
  
    = exp( yR(x) + R(0)∑_k≥ 2y^k/k) 
       = exp( yR(x) - yR(0) + R(0)log (1-y)^-1) 
       = exp( y(R(x)-R(0)))(1-y)^-R(0).

  We leave verification of the remaining two identities to the reader.


As an example, let us apply the above lemma when R(X)=X. Then each fibre
is a singleton and [X] is the species of bijections f:U→ V. The
four generating series are

    [X](x,y)    = e^xy = ∑_n≥ 0n!·x^ny^n/(n!)^2;
    [X]    = e^xy = ∑_n≥ 01· x^ny^n/n!;
    [X]    = e^xy = ∑_n≥ 01·x^n/n!y^n;
    [X](x,y)    = exp∑_k≥ 1x^ky^k/k
       = 1/1-xy = ∑_n≥ 01· x^ny^n.

In other words, to distribute n balls into k urns so that each urn
gets exactly one ball is impossible unless there are as many urns as
there are balls, that is, unless n=k. And, if n=k, then there are n! ways to
distribute the balls if balls and urns are distinct,
and there is exactly one way if the balls or the urns are identical.


  Let A(X) and B(X) be two unisort species, and let
  the two-sort species (X,Y)=E(R(X)Y) be as above.  Then
  
    [A+B](X,Y) = [A](X,Y)[B](X,Y).

  In particular, if R(X)=1+R_+(X), where R_+(X) is the species of nonempty
  R-structures, then
  
    (X,Y) = E(Y)[R_+](X,Y).



  For the first statement we have
  
    [A+B]
          = E((A+B)(X)Y )
          = E(A(X)Y +B(X)Y )
          = E(A(X)Y )E(B(X)Y )
          = [A][B].

  The second statement is simply [1](X,Y)=E(Y).



  Let A(X) and B(X) be two unisort species, and let (X,Y)
  be as above.  Then Z_[A+B] = Z_[A]Z_[B].  In
  particular, if R(X)=1+R_+(X) then Z_ = Z_E(Y)Z_[R_+],
  and consequently

  
    (x,y)    = E(y)·[R_+](x,y), 
       = E(y)·[R_+], 
       = E(y)·[R_+], 
    (x,y)    = E(y)·[R_+](x,y),

  in which E(y)=e^y and E(y) = 1/(1-y).

















The twelvefold way can be seen as the twelve generating series obtained
from calculating, for each R(X)∈{E(X), E_+(X), 1+X}, the four generating
series in Lemma <ref>. Note that it suffices to know R(x) and
R(x) to calculate those four series. For reference we record R(x)
and R(x) in Table <ref>.

We shall run through the cases of this table going from top to bottom.
Having already done R(X)=X, we proceed with R(X)=1+X. By direct
calculation, or from Corollary <ref> and equations
(<ref>) through (<ref>), we immediately get

    [1+X](x,y)    = e^y(1+x)
       = ∑_n,k≥ 0(k)_n x^n/n!y^k/k!,
    [1+X]    = e^y(1+x)
       = ∑_n,k≥ 0kn x^ny^k/k!,
    [1+X]    = 1/1-ye^xy
       = ∑_n,k≥ 0[n≤ k] x^n/n!y^k,
    [1+X](x,y)    = 1/1-y·1/1-xy
       = ∑_n,k≥ 0[n≤ k] x^ny^k,

where (k)_n=k(k-1)⋯(k-n+1) denotes the
falling factorial and [P] is the Iverson bracket, which is 1 if the
proposition P is true and 0 if it is false.


Assuming that each urn contains at most one ball, there are thus (k)_n
ways to distribute n distinct balls into k distinct urns; there are
kn ways to distribute n identical balls into k distinct
urns; if n≤ k, then there's exactly one way to distribute n balls
(distinct or identical) into k identical urns, and if n>k there's no
way to distribute the balls.

As a side note, the generating series in (<ref>) is the same as
for the [x]-weighted species _w(Y)=E_w(Y)E(Y) in which the
weight of an E_w-structure is w(A)=x^|A|. Indeed, those
species are combinatorially equal:
[1+X]=_w(Y).

Let us now consider R(X)=E_+(X). Using Lemma <ref> we find that

    [E_+](x,y)
         = exp( y(e^x - 1) )
        = ∑_n,k≥ 0k! S(n,k) y^k/k!x^n/n!,
    [E_+]
         = exp( xy/1-x)
        = ∑_n,k≥ 0n-1n-k  x^ny^k/k!,
    [E_+]
         = exp( y(e^x - 1) )
        = _w(x) = ∑_n,k≥ 0S(n,k) x^n/n!y^k,
    [E_+](x,y)
         = exp∑_k≥ 1y^k/kx^k/1-x^k
        = ∏_k≥ 11/1-yx^k
        = ∑_n,k≥ 0p_k(n) x^ny^k,

where S(n,k) is a Stirling number of the second kind and p_k(n) is
the number of integer partitions of n with k parts. Note that the
second equality in (<ref>) is the same as
(<ref>) on page
eq:integer-partitions-with-k-blocks, above. The interpretation
of the formulas above in terms of balls and urns should at this stage be
clear.

The last case of the twelvefold way is R(X)=E(X). Since E(X)=1+E_+(X) we may use
Corollary <ref> when convenient, and we have

    [E](x,y)
             = exp( y e^x  )
           = ∑_n,k≥ 0k^n x^n/n!y^k/k!; 
    [E]
              = exp(y/1-x)
           = ∑_n,k≥ 0n+k-1n x^ny^k/k!; 
    [E]
             = 1/1-y[E_+]
          = ∑_n,k≥ 0(S(n,0)+⋯+S(n,k)) x^n/n!y^k; 
    [E](x,y)
             = 1/1-y[E_+](x,y)
            =∑_n,k≥ 0(p_0(n) +⋯+ p_k(n) ) x^ny^k.




Bogart's <cit.> twentyfold way is a natural extension of
Rota's twelvefold way, which, in our setting, amounts to having more
choices for R(X). For the twelvefold way R(X) is one of E(X), E_+(X), or
1+X. For the twentyfold way there are three additional options:
X, L(X), and L_+(X). At first glance this appears to give us
6· 4 = 24 cases, but since E(x)=L(x) and
E_+(x)=L_+(x) there are only 20 distinct cases.

Let us explore these additional cases, and let us start with
R(X)=L_+(X). This gives us two new series (the other two series being the
same as for R(X)=E_+(X)):

    [L_+](x,y)    = exp(xy/1-x)
        = ∑_n,k≥ 0k!L(n,k) x^n/n!y^k/k!, 
    [L_+]    = exp(xy/1-x)
        = ∑_n,k≥ 0L(n,k) x^n/n!y^k,

where L(n,k)=nk(n-1)_n-k denotes a Lah
number <cit.>. Using the language of species, the standard
combinatorial interpretation of these numbers is as follows: Define the
species =E(L_+), so that a -structure is a set of nonempty
disjoint linear orders, such as {63,9,4815,27}∈[9]. The
number of -structures on [n] with k blocks / linear orders is
L(n,k).

With R(X)=L(X) the two new series are

    [L](x,y)    = exp(y/1-x)
          = ∑_n,k≥ 0(n+k-1)_n x^n/n!y^k/k!, 
    [L]    = 1/1-y[L_+]
          = ∑_n,k≥ 0(L(n,0)+⋯+L(n,k))x^n/n!y^k,

and this concludes the twentyfold way.

We have seen Stirling numbers of the second kind (R(X)=E_+(X)). We have also
seen  numbers (R(X)=L_+(X)), which are sometimes referred to as
Stirling numbers of the third kind <cit.>. But what about
the Stirling numbers of the first kind?  Is there a choice of R(X) which
gives those numbers? Note that the species constructions for the
Stirling numbers of the second and third kind follow a similar pattern:
(X) = E(E_+(X)) and (X) = E(L_+(X)). Assume, more generally, that the
species R(X) and R^c(X) are related by R(X)=E(R^c(X)), so that an
R-structure is a set of disjoint R^c-structures. We may then call
R^c the species of connected R-structures <cit.>.


  Assume that R(X)=E(R^c(X)) and define the [y]-weighted species
  R_w(X)=E(yR^c(X)), where yR^c(X) is like R^c(X) but with a weight y given
  to each structure. Then
  
    [R^c] = R_w(X).



  A typical [R^c]-structure on a finite set U is an
  equivalence class [s]_Y, where s∈[R^c][U,V] for some finite
  set V={v_1,…,v_k}. This representative, s, can in turn be
  written s={(s_v, v): s_v∈ R^c[B_v], v∈ V} for some partition
  {B_v_1,…,B_v_k} of U. Define
  α_U: _V[R^c][U,V] → R_w[U] by
  α_U(s)={s_v: v∈ V}. It's easy to see that this definition
  is independent of the representative for [s]_Y. It preserves weights
  too: the weight of [s]_Y is y^|V|=y^k, which is also the weight
  of {s_v: v∈ V}. Further, for any bijection σ:U→ U', the
  relevant diagram commutes and thus α_U is the desired natural
  isomorphism.


This proposition applies to every other row of
Table <ref>: the connected components of a set, E(X), are
the points, X; the connected components of a partition, (X), are
the blocks, E_+(X); the connected components of a -structure are
the linear orders, L_+(X); and the connected components of a permutation
are the cycles, (X). See also Figure <ref> for an
illustration of these cases. Letting
E_w(X)=E(yX),
_w(X)=E(yE_+(X)), _w(X)=E(yL_+(X)), and _w(X)=E(y(X)), and applying
Proposition <ref> we have

    =2pt
    [     [X]       = E_w(X);   [E_+]       =  _w(X);;   [L_+]       =  _w(X);      []       =  _w(X). ]

We could add to this list by considering other natural pairs R(X) and
R^c(X) such as graphs and connected graphs, or forests and trees.


Returning to the Stirling numbers, we see from above that

    [] = _w(x) = (1-x)^-y
        = ∑_n,k≥ 0c(n,k) x^n/n!y^k,

where c(n,k) denotes an unsigned Stirling number of the first kind. The other three
series for R(X)=(X) are [] =[E_+],
[](x,y) = [E_+](x,y), and
[](x,y) = (1-x)^-y= ∑_n,k≥ 0k!
c(n,k) x^n/n!y^k/k!.  Each choice of R(X) that we have
discussed up to this point can be found in Table <ref>, and the
four series associated with that choice are listed in
Table <ref>.

We will stop here, but note that there are, of course, other choices for
R(X) that may be natural, but we have omitted. For instance, setting

    R(X)=E_odd(X) = E_1(X)+E_3(X)+⋯

would require that each urn contains an odd number of balls.




abbrv


Division of Mathematics, The Science Institute, University of Iceland


