Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/ium/postscript/f00/notes/comb05.ps Дата изменения: Thu Jan 23 16:43:45 2003 Дата индексирования: Sat Dec 22 19:18:15 2007 Кодировка: Поисковые слова: arp 220

S.Duzhin
COMBINATORICS
Lecture 5: Algebra of combinatorial species
A multitude of algebraic operations can be dened between combinatorial species. In
this lecture, we will introduce addition and multiplication that turn the set of (equivalence
classes of) species into a commutative semiring with unity.
Denition. Let F and G be two combinatorial species. The sum of species is dened
as follows. For any nite set U
(F +G)[U ] = F [U ] [ G[U ];
where the sets F [U ] and G[U ] are considered to have no common elements. (If F [U ]
and G[U ] do have common elements, then we should set, for example, (F + G)[U ] =
(F [U ]  f1g [ (G[U ]  f2g). For a given bijection, the denition of the map (F +G)[] is
natural.
Theorem. Each of the three generating series associated with the sum of species is
equal to the sum of corresponding series:
(F +G)(x) = F (x) +G(x);
(
^
F +G)(x) = ~
F (x) + ~
G(x);
Z F+G = Z F + ZG :
Examples.
1. If E e is the species of even sets and E o the species of odd sets, then we have
E = E e + E o :
The corresponding relations between the generating functions are:
e x = ch(x) + sh(x);
1
1 x
=
1
1 x 2
+
x
1 x 2
;
exp
X
k
x k
k
= exp
X
k
x 2k
2k
[ch(x 1 + x 3 =3 + :::) + sh(x 1 + x 3 =3 + :::)]:
2. (The canonical decomposition of a species). For any species F , set
F n [U ] =

F [U ]; if jU j = n;
;; otherwise
:
Then
F = F 0 + F 1 + F 2 + :::
1

Denition. Let F and G be two combinatorial species. The product of species is
dened as follows. For any nite set U
(F
G)[U ] =
X
V U
F [V ] G[U n V ];
sum being taken over all subsets of U , including the empty set and the set U itself. For a
given bijection , the denition of the map (F
G)[] is natural.
Theorem. Each of the three generating series associated with the sum of species is
equal to the product of the two corresponding series:
(F
G)(x) = F (x)
G(x);
(
]
F
G)(x) = ~
F (x)
~
G(x);
Z F
G = Z F
ZG :
Examples.
1. E 2 = E
E is the species of subsets.
2. Consider the species of permutations S. The set on which a permutation acts, can
be divided into two parts: the subset of xed points and the subset where the permutation
acts without xed points. In the language of species, this fact can be written as
S = E
Der;
where Der is the species of derangements, i.e. permutations without xed points.
Problems.
1. Using the above combinatorial equations, nd the expressions of the three generating
functions for the species E 2 and Der.
2. Let E+ be the species of non-empty sets (so that E = 1+E+ ). Explain the meaning
of the species
Bal =
1
X
k=0
(E+ ) k
and nd its generating series.
3. Prove that the species of linear orders L and the species of singletons X satisfy the
equations
L = 1 +XL =
1
X
k=0
X k =
1
Y
k=0
(1 +X 2 k
):
2