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. 1 In enumerative combinatorics there are various terminologies. If the counting function is monotone, it is called speed in [5]. 2

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2011 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.