Definability of Combinatorial Functions and Their Linear Recurrence Relations

Details Definability of Combinatorial Functions and Their Linear Recurrence Relations Definability of Combinatorial Functions and Their Linear Recurrence Relations

2009-07-30

arxiv.org/abs/0907.5420v1

Mathematics

Combinatorics

18 pages, 1 table

Scientific paper

We consider functions of natural numbers which allow a combinatorial interpretation as density functions (speed) of classes of relational structures, s uch as Fibonacci numbers, Bell numbers, Catalan numbers and the like. Many of these functions satisfy a linear recurrence relation over $\mathbb Z$ or ${\mathbb 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 \in \mathbb{N}$ a linear recurrence relation over $\mathbb{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 $\mathbb{Z}$, and discuss various extensions and limitations of the Specker-Blatter theorem.

Affiliated with

Also associated with

No associations

Rating

Definability of Combinatorial Functions and Their Linear Recurrence Relations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Definability of Combinatorial Functions and Their Linear Recurrence Relations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Definability of Combinatorial Functions and Their Linear Recurrence Relations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-266902