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

S.Duzhin
COMBINATORICS
Lecture 4: Combinatorial species
According to N. Bourbaki, a structure in a set U is an element of a tower of sets over U .
In the combinatorial context, A. Joyal substitutes this organic denition by a functional
one.
Denition. A species of structures is a functor from the category B of nite sets and
bijections to the category of nite sets and arbitrary maps S:
F : B ! S:
In other words, a species F is a rule that assigns, to every nite set U , a nite set F [U ]
and to every bijection  : U ! V , a mapping F [] : F [U ] ! F [V ] in such a way that
1 ф . F [ ф  ] = F [] ф F [ ].
2 ф . F [id U ] = id F [U ] .
Every element of F [U ] is referred to as a structure of species F , or an F -structure
in the set U . The mapping F [] is called the transport of F -structures along . If  :
U ! U and s 2 F [U ], then the structures s and s 0 = F [](s) are called equivalent or
isomorphic, notation: s  s 0 . It immediately follows from the denition that all maps F []
are bijections. thus a species is in fact a functor F : B ! B .
Examples.
1. Empty species 0[U ] = ; for any U .
2. Species of empty sets 1[U ] = fUg, if U = ;, and ; otherwise.
3. Species of singletons X[U ] = fUg, if jU j = 1, and ; otherwise.
4. Species of sets E[U ] = fUg for any U .
5. Species of elements "[U ] = U for any U .
6. Species of linear orders L[U ] = flinear orders in the set Ug.
7. Species of permutations S[U ] = fpermutations of the set Ug.
Denition. (1) Two species, F 1 and F 2 , are said to be equipotent, if the sets F 1 [U ] and
F 2 [U ] have equal cardinality for any nite set U .
(2) Two species, F 1 and F 2 , are said to be isomorphic, if the corresponding functors are
isomorphic in category theoretic sense, i.e. there is a family of bijections F 1 [U ] ! F 2 [U ],
natural with respect to U .
The distinction between these two notions can be understood by comparing the two
species L and S which are equipotent but not isomorphic.
With every species F , one can associate three important formal power series: F , ~
F and
Z F .
Before giving the denitions, let us note that the number of elements in the set F [U ]
is uniquely dened by the cardinality of the set U , therefore jF [U ]j = jF [n]j, if jU j = n,
where [n] stands for the set f1; 2; :::; ng and F [n] is the simplied way to write F [[n]].
1

Denition. The generating series of a combinatorial species F is
F (x) =
1
X
n=0
f n
n!
x n ;
where f n = jF [n]j.
Denition. The type generating series of a combinatorial species F is
~
F (x) =
1
X
n=0
~
f n x n ;
where ~
f n = jF [n]=  j is the number of F -structures in a set of n elements considered up
to isomorphism.
Denition. The cycle index series of a combinatorial species F is the formal power
series in an innite number of variables x 1 ; x 2 ; :::
Z F (x 1 ; x 2 ; :::) =
1
X
n=0
1
n!
 X
2Sn
x F [] x 1
1 x  2
2




;
where, for a permutation  : [n] ! [n], the symbol  k is the number of cycles of length k in
the decomposition of  into disjoint cycles and x F [] means the number of xed points
of the mapping F [] : F [n] ! F [n].
Examples.
Notation Name F (x) ~
F (x) Z F (x 1 ; x 2 ; :::)
0 empty species 0 0 0
1 empty sets 1 1 1
X singletons x x x 1
E sets e x 1
1 x
exp
P 1
k=1
x k
k
" elements xe x x
1 x
x 1 exp
P 1
k=1
x k
k
L linear orders 1
1 x
1
1 x
1
1 x 1
S permutations 1
1 x
Q 1
k=1
1
1 x k
Q 1
k=1
1
1 x k
Each of the two series F (x) and ~
F (x) can be deduced from the cycle index series.
Theorem. For any species F , we have:
(a) F (x) = Z F (x; 0; 0; : : :);
(b) ~
F (x) = Z F (x; x 2 ; x 3 ; : : :):
2