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 coeﬃcients. In this paper we discuss suﬃcient 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 coeﬃcients 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 B¨ 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

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 coeﬃcients. In this paper we discuss suﬃcient 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 coeﬃcients 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 B¨ 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