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

S.Duzhin
COMBINATORICS
Lecture 6: Composition of combinatorial species
Definition. Let F and G be two combinatorial species such that G[;] = ; (there are
no G-structures on the empty set). The composition of species F ф G, also denoted by
F (G), is defined as follows. For any finite set U
(F ф G)[U ] =
[
 Part(U)
F [] 
Y
p2
G[p];
where Part(U) is the set of all partitions of U , i.e representations of U in the form of a
disjoint union of non-empty subsets U = U 1 [ ::: [U n . For  = fU 1 ; :::; U n g, F [] is the set
of all F -structures on the partition (=on the set of subsets U 1 ; :::; U n ). Because of the role
of partitions in the definition, this construction is also called partitional composition.
For a given bijection , the definition of the map (F ф G)[] is natural.
Unlike the two previously introduced operations on species, partitional composition is
literally compatible with only one generating series F (x). The following theorem holds.
Theorem. The generating series of the partitional composition are computed as follows:
(F ф G)(x) = F (G(x));
(
^
F ф G)(x) = Z F ( ~
G(x); ~
G(x 2 ); ~
G(x 3 ); :::
Z FфG (x 1 ; x 2 ; :::) = Z F (ZG (x 1 ; x 2 ; :::); ZG (x 2 ; x 4 ; :::); :::):
The operation on formal series in an infinite number of variables (numbered by natural
numbers) that appears in the formula for Z FфG , is referred to as the plethystic substitution
of ZG into Z F .
Examples.
1. Consider an endofunction, i.e. a mapping  : U ! U . The points of U can be divided
into two types: recurrent points, such that  k (x) = x for some k  1, and non-recurrent
points. Recurrent points form several cycles, while non-recurrent ones form several trees
flowing into these cycles. Therefore. an endofunction if a permutation of rooted trees, and
we can write:
End = S ф R:
2. Every permutation is a set of disjoint cycles, therefore
S = E ф C;
where E is the species of sets and C is the species of cyclic permutations.
Problems.
1. Find the relations between the generating series of the species End, S, R and S, E,
C that follow from the previous combinatorial identities.
2. Prove the isomorphisms Bal = L(E+ ), Par = E(E+ ) and derive enumerative conse-
quences thereof.
1