2 E. FISCHER, T. KOTEK, AND J.A. MAKOWSKY
Part 1. Introduction and Synopsis
1. Sequences of integers and their combinatorial interpretations
We discuss sequences a(n) of natural numbers or integers which arise in com-
binatorics. In some cases such sequences satisfy linear recurrence relations with
constant or polynomial coefficients. In this paper we discuss sufficient structural
conditions on a(n) which imply the existence of various linear recurrence relations.
The traditional approach for studying such sequences consists of interpreting
a(n) as the coefficients of a generating function g(x) =

n
a(n)xn, and of using
analytic methods, to derive properties of a(n), cf. [38]. Another general framework
of species of structures for combinatorial interpretations of counting functions is
described in [9, 10]. Lack of space does not allow us to use this formalism in this
paper. There is also a substantial theory of how to algorithmically verify and prove
identities among the terms of a(n), see [64].
We are interested in the case where the sequence a(n) admits a combinatorial
or a logical interpretation, i.e., a(n) counts the number of relations or functions
over the set [n] = {1,...,n} which have a certain property, possibly definable in
some logical formalism (with or without its natural order). To make this precise,
we assume the reader is familiar with the basics of Logic and Finite Model Theory,
cf. [30, 56] and also [46]. We shall mostly deal with the logics SOL, Second
Order Logic, and MSOL, Monadic Second Order Logic. Occasionally, we formulate
statements in the language of automata theory and regular languages and use freely
the uchi-Elgot-Trakhtenbrot Theorem, which states that a language is regular iff
it is definable in MSOL when we view its words of length n as ordered structures
over a set of n elements equipped with unary predicates, cf. [30]. More details on
the logical tools used will be given wherever needed.
We define a general notion of combinatorial interpretations for finite ordered
relational structures.
Definition 1.1 (Combinatorial interpretation). A combinatorial interpreta-
tion K of a(n) is given by
(i) a class K of finite structures over a vocabulary
τ = {R1,...Rr} = {R} or τord = {
nat
, R}
where the universe of a structure of size n in K is [n] = {1,...,n}, and
the relation symbol
nat
is interpreted as the natural order on [n].
(ii) The counting function dK(n),
dK(n) = {R on [n] : [n],
nat
, R K}
which counts the number of
relations1,
is such that dK(n) = a(n).
(iii) A combinatorial interpretation K is a pure combinatorial interpretation
of a(n) if K is closed under τ-isomorphisms. In particular, if K does not
depend on the natural order
nat
on [n], but only on τ.
Our counting functions count labeled structures. In the example of counting
linear orders we have n! linear orders on [n] in the labeled case, whereas only one
linear order in the unlabeled case. In this article we do not deal with the unlabeled
case.
1In
enumerative combinatorics there are various terminologies. If the counting function is
monotone, it is called speed in [5].
2
Previous Page Next Page