Definability of Combinatorial Functions and Their Linear Recurrence Relations

摘要

We consider functions of natural numbers which allow a combinatorial interpretation as counting functions (speed) of classes of relational structures, such as Fibonacci numbers, Bell numbers, Catalan numbers and the like. Many of these functions satisfy a linear recurrence relation over Z or Z_m and allow an interpretation as counting the number of relations satisfying a property expressible in Monadic Second Order Logic (MSOL). C. Blatter and E. Specker (1981) showed that if such a function f counts the number of binary relations satisfying a property expressible in MSOL then f satisfies for every m ∈ N a linear recurrence relation over Z_m. In this paper we give a complete characterization in terms of definability in MSOL of the combinatorial functions which satisfy a linear recurrence relation over Z, and discuss various extensions and limitations of the Specker-Blatter theorem.