Exact Largest and Smallest Size of Components in Decomposable Structures

Daniel Panario

University of Toronton

Algorithms Seminar

June 21st, 1999

[summary by Bruno Salvy]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Abstract
In [2], the number of permutations of n objects with largest cycle length equal to k is studied in detail. The purpose of [3] which is summarized here is to show that these results generalize in a straightforward manner to all labelled sets, unlabelled sets and unlabelled powersets.

Sets are a basic combinatorial construction. Many properties of general structures are direct consequences of their being sets. Special cases of sets are: graphs of various kinds (sets of connected components), permutations (sets of cycles), polynomials over finite fields (sets of factors). In all those cases, the statistics of the largest and smallest component are related to the complexity of algorithms operating over these structures. Very explicit results concerning these statistics can be obtained by extracting coefficients from the proper generating functions, which in this case is a refined way of performing an inclusion-exclusion argument.

The study is based on three generating functions corresponding to three different ways of considering sets, depending on whether the atomic objects (those of size 1) are labelled or unlabelled and on whether repetitions are allowed or not in sets (in the unlabelled case). Let C(z) be the generating function of the objects of which a set is being made (ordinary in the unlabelled case and exponential in the labelled case):
C(z)=
 
å
n³0
cnzn  or    C(z)=
 
å
n³0
cn
zn
n!
,
where cn is the number of objects of size n and it is assumed that c0=0 so that the enumeration is well-defined. Then the generating functions under study are
L(z)
=exp (C(z))=:
 
å
n
ln
zn
n!
,
P(z)
=exp ( C(z)-C(z2)/2+C(z3)/3-··· ) ,
S(z)
=exp ( C(z)+C(z2)/2+C(z3)/3+··· ) ,
L(z) is the exponential generating function in the labelled case, P(z) and S(z) are the ordinary generating functions in the unlabelled case, with repetitions allowed for S and forbidden for P. These equations and their derivations are classical, see for instance [1].

Setting all the cn to 0 for n>k leads to formulæ for sets whose largest component has size at most k. Similarly, setting all the cn to 0 for n<k yields formulæ for sets whose smallest component has size at least k. Taking the difference between largest size at most k and largest size at most k-1 gives the formulæ for largest size exactly k, and similarly for the smallest size. The corresponding generating functions will be denoted Lkl(z), Lks(z), Pkl(z),.... Thus for instance
L
l
 
k
(z)=exp æ
ç
ç
è
k-1
å
m=0
cmzm
m!
ö
÷
÷
ø		 (e
ckzk/k!
 
-1)=(e
ckzk/k!
 
-1)L(z)exp æ
ç
ç
è		 -
 
å
m³ k
cmzm
m!
ö
÷
÷
ø		 .     (1)

The simultaneous study of the number of components in the set is achieved by changing C into uC for a new variable u, which leads to bivariate generating functions the coefficient of ukzn of which is the number of sets of size n with k elements.

Various combinations of these techniques produce numerous results. We exemplify the ideas in the labelled case below. The procedure is the same in the unlabelled case and the results are slightly more complicated.

Expanding the first exponential in (1) and extracting the coefficient of zn yields
[zn]L
l
 
k
(z)
=
ck
k!
ln-k
(n-k)!
,
     n/2<k£ n
 
=
ck
k!
æ
ç
ç
è
ln-k
(n-k)!
+
ck
2k!
ln-2k
(n-2k)!
-
n-2k
å
m=k
cm
m!
ln-m-k
(n-m-k)!
ö
÷
÷
ø		 ,
     n/3<k£ n/2,
and more and more complicated formulæ as more terms of the exponentials have to be taken into accounts. These formulæ generalize all of the results in [2], except one which is derived by noticing that L=åkLkl leading to a recurrence expressing [zn]Lkl(z) in terms of the [zn-ki]Ljl(z), j£ k-1, i£ë n/kû.

Formulæ involving the smallest component are derived in a similar manner from
Lks(z)=exp æ
ç
ç
è
 
å
m>k
cmzm
m!
ö
÷
÷
ø		 (e
ckzk/k!
 
-1).
Extracting coefficients yields
[zn]Lks(z)
=
ck
k!
,
     k=n,
  =0,      n/2<k<n,
 
=
ck2
2k!2
,
     k=n/2,
 
=
ck
k!
cn-k
(n-k)!
,
     n/3<k<n/2,...
And again a recurrence formula can be derived. In all cases, an obvious inclusion-exclusion argument can be read off the formula.

References

[1]
Bergeron (F.), Labelle (G.), and Leroux (P.). -- Combinatorial species and tree-like structures. -- Cambridge University Press, Cambridge, 1998, xx+457p. Translated from the 1994 French original by Margaret Readdy, With a foreword by Gian-Carlo Rota.

[2]
Golomb (Solomon W.) and Gaal (Peter). -- On the number of permutations of n objects with greatest cycle length k. Advances in Applied Mathematics, vol. 20, n°1, 1998, pp. 98--107.

[3]
Panario (Daniel) and Richmond (Bruce). -- Exact largest and smallest size of components in decomposable structures. -- June 1999. Preprint.
This document was translated from LATEX by HEVEA.