\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{enumerate}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\newcommand{\card}{\mathrm{card}}
\newcommand{\MOD}{\mathrm{MOD}}
\newcommand{\Add}{\mathrm{Add}}
\newcommand{\Duplicate}{\mathrm{Duplicate}}
\newcommand{\Recolor}{\mathrm{Recolor}}
\newcommand{\Uncolor}{\mathrm{Uncolor}}
\newcommand{\AddEdges}{\mathrm{AddEdges}}
\newcommand{\DeleteEdges}{\mathrm{DeleteEdges}}
\newcommand{\Lah}{\mathrm{Lah}}
\newcommand{\RG}{\mathrm{RG}}
\newcommand{\LQ}{\mathrm{LQ}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\SOL}{\mathrm{SOL}}
\newcommand{\FOL}{\mathrm{FOL}}
\newcommand{\MSOL}{\mathrm{MSOL}}
\newcommand{\CMSOL}{\mathrm{CMSOL}}
\newcommand{\CFOL}{\mathrm{CFOL}}
\newcommand{\fB}{{\mathfrak B}}
\newcommand{\bP}{{\mathbf P}}
\newcommand{\bMP}{{\mathbf{MP}}}
\newcommand{\bPH}{{\mathbf{PH}}}
\newcommand{\bNP}{{\mathbf{NP}}}
\newcommand{\cC}{{\mathcal{C}}}
\newcommand{\cP}{{\mathcal{P}}}
\newcommand{\bA}{{\mathbf{A}}}
\newcommand{\bB}{{\mathbf{B}}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\def\modd#1 #2{#1\ \mbox{\rm (mod}\ #2\mbox{\rm )}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{problem}[theorem]{Problem}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
MC-Finiteness of Restricted\\
\vskip .1in
Set Partition Functions 
}
\vskip 1cm
\large
Yuval Filmus, Eldar Fischer, and Johann A. Makowsky\\
Faculty of Computer Science\\
Israel Institute of Technology\\
3200003 Haifa \\ 
Israel\\
\href{mailto:yuvalfi@technion.ac.il}{\tt yuvalfi@technion.ac.il} \\
\href{mailto:eldar@cs.technion.ac.il}{\tt eldar@cs.technion.ac.il} \\
\href{mailto:janos@cs.technion.ac.il}{\tt janos@cs.technion.ac.il}\\
\ \\
Vsevolod Rakita\\
Faculty of Mathematics\\
Israel Institute of Technology\\
3200003 Haifa\\
Israel\\
\href{mailto:vsevolod@campus.technion.ac.il}{\tt vsevolod@campus.technion.ac.il}
\end{center}

\vskip .2 in

\begin{abstract}
A sequence $s(n)$ of integers is MC-finite if for every
$m \in \N$ the sequence $s(n) \bmod m$
is ultimately periodic. We discuss various ways of proving and disproving MC-finiteness.
Our examples are mostly taken from set partition functions, but our methods can be applied to 
many more integer sequences.
\end{abstract}

\section{Introduction}
\label{se:intro}

\subsection{Goal of this paper}
Given a sequence of integers $s(n)$ with some combinatorial interpretation, one wonders what can be said
about the  sequence $s(n)$. Ideally, we would like to have an explicit formula for $s(n)$, 
or some recurrence relation with coefficients being constant or polynomial in $n$.
Second best is an asymptotic description of $s(n)$. 
We could instead look at the
sequence $s^m(n) \equiv s(n)$ (mod $m$) and try to describe $s^m(n)$.
If for every  modulus $m$ the sequence $s^m(n)$ is ultimately periodic, we say that $s(m)$
is {\em MC-finite}. We consider MC-finiteness a legitimate topic in the study of integer sequences.
The notion of MC-finiteness appears under this name only since the publication of 
Makowsky \cite{makowsky2010application} in 2010.
Without its name, the concept seemingly appears first in Blatter and Specker 
\cite{blatter1981nombre,pr:BlatterSpecker84}. Otherwise it rarely appears 
in the literature, e.g., 
under the name of {\em supercongruence} in Banderier et al.\ \cite{banderier2017right,banderier2019period}.
The four substantial monographs
on integer sequences published after 2000 
by Everest et al., Mansour, and Mez{\H{o}}
\cite{everest2003recurrence,mansour2012combinatorics,mansour2012combinatorics,mezo2019combinatorics}
do not mention the concept at all, 

All the sequences we discuss in this paper appear in the 
{\em On-Line Encyclopedia of Integer Sequences \cite{oeis}}, with a number starting with $A$. 
We give these numbers with the first mention of the sequence, and list them also at the end of the paper.
Needless to say, our methods also apply to many other entries in OEIS.

Broder \cite{broder1984r} introduced 
the restricted Bell numbers $B_r(n)$
and the restricted Stirling numbers of the second kind
$S_r(n,k)$. The sequence $B_r(n)$ is
only listed in OEIS for 
$r=2, \seqnum{A005493}$ and
$r=3, \seqnum{A005494}$. 
The sequences
$S_r(n,k)$ appear in OEIS as
$\seqnum{A143494}, \seqnum{A143495}$, and $\seqnum{A143496}$. 
This paper grew out of our attempts to show that the sequence $B_r(n)$ 
of restricted Bell numbers is MC-finite.


The purpose of this paper is two-fold.
Its first part is mostly expository. It is written with the intent to popularize the study of MC-finiteness
for researchers interested in properties of integer sequences. 
However, the statements that the examples chosen are MC-finite have not, to the best of our knowledge,
been stated before in the literature.
We have chosen our examples
in order to familiarize the reader with the two general methods to establish MC-finiteness.
The first method is a {\em logical method}, pioneered by Blatter and Specker 
\cite{blatter1981nombre,specker1990application,pr:BlatterSpecker84}. 
It was further 
developed by two of the authors of this paper (EF and JAM) \cite{pr:FischerMakowsky03,ar:FischerMakowsky2022}.
The second method is a {\em combinatorial method} to prove MC-finiteness.
It was also first suggested by Specker 
\cite{specker1990application} and later, independently, by S\'enizergues \cite{senizergues2007sequences}.
Only Cadilhac et al.\ \cite{cadilhac2021polynomial} finally made this  second method precise.
It is based on the existence of finitely many mutual polynomial recurrence relations over $\Z$ that are
used to define the integer sequence.
In a separate paper, the first method is applied by Fischer and Makowsky to show MC-finiteness of 
infinitely many integer sequences arising from counting finite topologies \cite{topologies}. 

In this paper we investigate  MC-finiteness and counterexamples thereof of
integer sequences derived from counting various unrestricted and restricted set partitions and transitive relations.
Among the unrestricted cases we look at the Bell numbers $B(n)$, $\seqnum{A000110}$, and the Stirling numbers
of the second kind $S(n, k_0)$, $\seqnum{A000453}$. We also discuss
the number of linear quasi-orders (pre-orders) $\LQ(n)$, $\seqnum{A000670}$,
the number of quasi-orders (pre-orders) $Q(n)$, $\seqnum{A000798}$,
the number of partial orders $P(n)$, $\seqnum{A001035}$, and 
the number of transitive relations $T(n)$, $\seqnum{A006905}$, all of them on the set $[n]$.
The numbers $\LQ(n)$ are called {\em ordered Bell numbers} or {\em Fubini numbers}, often denoted 
in the literature by $a(n)$ and also by $F(n)$.
For the unrestricted cases the results are seemingly new, or at least have not been stated before. 
They are simple consequences
of growth arguments and the logical method due to Blatter and Specker 
\cite{pr:BlatterSpecker84,specker1990application}, the {\em Specker-Blatter theorem}.

Typical restricted cases, first introduced by Broder \cite{broder1984r} and further studied in \cite{benyi2019restricted}, 
are the Stirling numbers of the second kind $S_{A,r}(n,k)$,
which count the partitions of $[n+r]$ into $k+r$ blocks such that
the elements $i \leq r$ are all in different blocks and the size of every block is in $A \subseteq \NN$.
The case of $r=2$ appears as $\seqnum{A143494}$. 
The Bell numbers $B_{A,r}(n)$ are defined as $\sum_k S_{A,r}(n,k)$. They appear as $\seqnum{A005493}$ for $r=2$ and 
$\seqnum{A005494}$ for $r=3$.
The same restrictions can also be imposed on Stirling numbers of the second kind $S_{A,r}(n,k)$, 
and on all the unrestricted cases above.
For the restricted cases, the results are new and require non-trivial extensions of the Specker-Blatter theorem. 
The Catalan numbers, $\seqnum{A000108}$, also have an interpretation as set partitions. 
Roman \cite[Theorem 9.4]{roman2015introduction} and Koshy \cite[Chapter 10]{koshy2008catalan}
show that they count the number of
non-crossing partitions. 
Although this can be viewed as a restricted  version of the Bell numbers, our results do not apply to this case.
This is due to the global character of the restriction, as we shall explain later.

\subsection{Outline of the paper}

In Section \ref{se:mcfinite} we introduce C-finiteness and its modular variant MC-finiteness.
In Section \ref{se:howtoprove} we discuss the methods for proving and disproving C-finiteness and
MC-finiteness. 
In Section \ref{ap:mc-finite} we discuss larger classes of polynomial recursive sequences and weaker versions
of MC-finiteness, which in the literature appear under the name of {\em supercongruences}.
We also prove that, in a precise sense, almost all bounded integer sequences are not MC-finite.

In Section \ref{se:immediate}
we present immediate consequences of the logical method for set partitions without 
positional restrictions and without restrictions on size of the blocks.
The first four sections have a tutorial character. The material on MC-finiteness has never been collected
in this way before in the literature  
and neither has the MC-finiteness of the examples been stated.

In Sections \ref{se:restricted} and \ref{se:rproofs} we discuss  set partitions with
positional restrictions and restrictions on size of the blocks, and how new logical tools
are used to obtain C-finiteness and MC-finiteness in these cases.
In Section \ref{se:c-finite} we give further details for on how to use logic in order to prove C-finiteness.
We conclude the main part of the paper with Section \ref{se:conclu}, where
we present our conclusions and suggestions for further research. 

Sections \ref{ap:mc-finite}, \ref{se:explicit}, \ref{se:constants}, and \ref{se:c-finite} may be skipped in a first reading.

\section{C-finite and MC-finite integer sequences}
\label{se:mcfinite}
A sequence of integers $s(n)$ is {\em C-finite}
if there are constants $p, q \in \N$ and $c_i \in \Z, 0 \leq i \leq p-1$ 
such that for all $n \geq q$ the linear recurrence relation
$$
s(n+p) = \sum_{i=0}^{p-1} c_i s(n+i), n \geq q
$$
holds for $s(n)$.
C-finite sequences are also called in the literature {\em constant-recursive sequences}
or  {\em linear-recursive sequences}. 

C-finite sequences have limited growth; see, for instance, Everest et al.\ \cite{everest2003recurrence,kauers2011concrete}:
\begin{proposition}
\label{prop:c-finite}
Let $s_n$ be a C-finite sequence of integers. Then there is $c \in \N^+$ 
such that 
$a_n \leq 2^{cn}$
for all $n \in \N$.
\end{proposition}
Actually, a lot more can be said. Flajolet et al.\ \cite{flajolet2009analytic} 
discussed this in great detail, 
but we do not need it here for our purposes.

To prove that a sequence $s(n)$ of integers is not C-finite, we can use Proposition \ref{prop:c-finite}.
To prove that a sequence $s(n)$ of integers is C-finite, there are several methods:
One can try to find an explicit recurrence relation, one can exhibit a rational generating function,
or one can use a method based on model theory as described by Fischer and Makowsky in 
\cite{fischer2008linear,fischer2011application}.
The last method will be briefly discussed in
Section \ref{se:fm} and further explained in Section \ref{se:c-finite}. It is referred to as method FM.

A sequence of integers $s(n)$ is {modular C-finite}, abbreviated as {\em MC-finite}, 
if for every $m \in \N$ there are constants $p_m, q_m \in \N^+$ such that
for every  $n \geq q_m$ there is a linear recurrence relation
$$
s(n+p_m) \equiv \sum_{i=0}^{p_m-1} c_{i,m}  s(n+i)  \pmod{m}
$$
with constant coefficients $c_{i,m} \in \Z$. 
Note that the coefficients $c_{i,m}$ and both $p_m$ and $q_m$  generally do depend on $m$.

Let $s^m(n)$ denote the sequence $s^m(n) \equiv s(n)$ (mod $m$). 
\begin{proposition}
The sequence $s(n)$ is MC-finite iff $s^m(n)$ is ultimately periodic for every $m$.
\end{proposition}
\begin{proof}
MC-finiteness implies periodicity. The converse is proved by Reeds and Sloane in \cite{reeds1985shift}.
\end{proof}

Clearly, if a sequence $s(n)$ is C-finite then it is also MC-finite with $r_m=r$ and $c_{i,m}=c_i$ for all $m$.
The converse is not true. 
Proposition \ref{pr:many} below
shows that here are uncountably many MC-finite sequences 
with integer coefficients, 
but only
countably many C-finite sequences 
with integer coefficients. 

\newpage
\begin{example}
\label{ex:mc}\ 
\begin{enumerate}[(i)]
\item
The Fibonacci sequence is C-finite.
\item
If $s(n)$ is C-finite then it has at most simple exponential growth, by Proposition \ref{prop:c-finite}.
\item
The Bell numbers $B(n)$ are {\em not C-finite}, but are {\em MC-finite}.
\item
Let $f(n)$ be any integer sequence. The sequence $s_1(n)=2\cdot f(n)$ is ultimately periodic modulo $2$,
but not necessarily MC-finite.
\item
Let $g(n)$ be any integer sequence.
The sequence  $s_2(n) = n!\cdot g(n)$ is MC-finite.
\label{many-mc}
\item
The sequence $s_3(n)= \frac{1}{2} {2n \choose n}$ is not MC-finite:  the value of
$s_3(n)$ is odd iff $n$ is a power of $2$, and otherwise it is even (Lucas, 1878).
A proof may be found in Graham et al.\ \cite[Exercise 5.61]{graham1989concrete}, or in Specker \cite{specker1990application}.
\item
The Catalan numbers $C(n) = \frac{1}{n+1}{2n \choose n}$ are not MC-finite,
since $C(n)$ is odd iff $n$ is a Mersenne number, that is  $n = 2^m-1$ for some $m \in \N$.
A good reference is Koshy \cite[Chapter 13]{koshy2008catalan}.
\item
\label{many-nonmc}
Let $p$ be a prime and $f(n)$ be monotone increasing.
Let $s(n)$ be the sequence 
$$
s(n) = \begin{cases}
p^{f(n)}, & \text{ if } n \neq p^{f(n)}; \\
p^{f(n)}+1, & \text{ otherwise}. 
\end{cases}
$$
Then $s(n)$ is monotone increasing but  not ultimately periodic modulo $p$, hence not MC-finite.
\end{enumerate}
\end{example}

\begin{proposition}
\label{pr:many}\ 
\begin{enumerate}[(i)]
\item
There are uncountably many monotone increasing sequences that are MC-finite, and uncountably many
that are not MC-finite.
\item
Almost all integer sequences are not MC-finite.
\end{enumerate}
\end{proposition}
\begin{proof}
Claim (i) follows from
Examples \ref{ex:mc}
(\ref{many-mc}) and (\ref{many-nonmc}).
Claim (ii) is shown in
Proposition \ref{pr:normal} in  Section \ref{se:ProofMC}.
\end{proof}

Although we are mostly interested in MC-finite sequences $s(n)$, it is natural to check in each example
whether the sequence $s(n)$ is also C-finite. In most examples the answer is negative.
However, Theorem \ref{th:c-finite} shows that the restricted Stirling numbers of the second kind
listed therein are all C-finite. 
We show this via a general method, Theorem \ref{th:FM}, without exhibiting a generating function
like in the classical case for $S(n,k)$.


\section{How to prove and disprove MC-finiteness}
\label{se:howtoprove}

\subsection{Polynomial recurrence relations}

In his paper, Specker \cite[p.~144]{specker1990application} noted the following:
\begin{quote}
In many known cases, [MC-finiteness] is a consequence of
polynomial recurrence relations 
$$f(n) = \sum_{i=1}^d P_i(n) f(n-i)$$
where $P_i$ are polynomials in $\Z[x]$.
\end{quote}
For $f(n) = n!$ this is obvious.
In general this needs some elaboration.

\begin{definition}\ 
\begin{enumerate}[(i)]
\item
An integer sequence $s(n)$ is {\em holonomic over $\Z$} 
if there exist
polynomials $P_i \in \Z[x]$ with $P_1, P_k \neq 0$ such that
$$
s(n) = \sum_{i=1}^k P_i(n)s(n-i).
$$
\item
An integer sequence $s(n)$ is {\em polynomially recursive (PRS) over $\Z$} if
there exist $k$ integer sequences $s_i(n), 1 \leq i \leq k$ 
with $s(n) = s_1(n)$
and polynomials $P_i \in \Z[x_1, \ldots , x_k]$
such that  the mutual recursion 
$$
s_i(n+1) = P_i(s_1(n), \ldots , s_k(n)), i = 1, \ldots, k
$$
holds.
\item
An integer sequence $s(n)$ is {\em PRS  over $\Z$ and $n$} if
the polynomials also involve $n$ as an additional variable.
In other words $P_i \in \Z[x_1, \ldots , x_k, y]$ and
$$
s_i(n+1) = P_i(s_1(n), \ldots , s_k(n), n), i = 1, \ldots, k.
$$
\end{enumerate}
Actually, (ii) and (iii) are equivalent.
\end{definition}

We note that
if $s(n)$ is an integer sequence that is polynomially recursive over $\Z$ and $n$, 
then $s(n)$ is holonomic over $\Z$.

In fact, the following is true:
\begin{theorem}
\label{th:MC}
If $s(n)$ is an integer sequence that is polynomially recursive over $\Z$ and $n$ then $s(n)$
is MC-finite. 
In particular, this is true also for integer sequences $s(n)$ 
that are holonomic over $\Z$.
\end{theorem}
The proof is given in Section \ref{se:ProofMC}. There we also briefly discuss weaker properties than
MC-finiteness, where the modular recurrence holds only for almost all $m \in \N^+$.


\begin{remark}\ 
\begin{enumerate}[(i)]
\item
In general, holonomic sequences are defined over  fields $\mathbb{F}$ rather than the ring $\Z$.
A good reference is the monograph by Kauers and Paule \cite[Chapter 7]{kauers2011concrete}.
A theorem related to Theorem \ref{th:MC} for holonomic sequences can be found in two papers
by Banderier et al.\ \cite[Theorem 7]{banderier2017right} and \cite{banderier2019period}.
\item
Cadilhac et al.\ \cite{cadilhac2020icalp,cadilhac2021polynomial}
define polynomially recursive sequences for rational numbers rather than
integers, and the polynomials are in $\Q[x_1, \ldots , x_k]$.
\end{enumerate}
\end{remark}

The following examples, except (v), are from \cite{cadilhac2021polynomial}.
\begin{example}\ 
\begin{enumerate}[(i)]
\item
The sequences $a(n) = n!$ with $a(n) = n\cdot a(n-1)$ and $a(0)=1$ is holonomic over $\Z$.
It is obviously MC-finite.
\item
The sequence
$a(n)= 2^{2^n}$ is polynomially recursive with $a(0)=2$ and $a(n) = a(n-1)^2$. 
It is not holonomic, since Gerhold \cite{gerhold2004some} showed that 
every holonomic sequence $a(n)$ is bounded by some $2^{p(n)}$
for some polynomial $p(n)$. 
It is easy to see that it is MC-finite, but it is also MC-finite by the Specker-Blatter theorem below,
as it counts the number of ways one can interpret a unary predicate over $[n]$.
\item
The Catalan numbers $C_n$ are holonomic: $ (n+2)C_{n+1} = (4n+2)C_n $.
They are not holonomic over $\Z$, since they are not MC-finite. 
Furthermore, they are not polynomially recursive even if we allow rational numbers.
\item
The sequence $n^n$ is not polynomially recursive, but
it is MC-finite by the Specker-Blatter theorem below.
\item
We show in Section \ref{ap:mc-finite} that
the sequence $\seqnum{A086714}$ given by 
$$a(0)=4, a(n+1) = {a(n) \choose 2}$$ 
is not MC-finite but is periodic modulo every odd number.
\end{enumerate}
\end{example}

MC-finite sequences are closed under various arithmetic operations.
\begin{proposition}
\label{mc-closure}
Let $a(n), b(n)$ be MC-finite sequences and $c \in \Z$.
\begin{enumerate}[(i)]
\item
The sequences $c\cdot a(n), a(n) + b(n), a(n) \cdot b(n)$ are MC-finite.
\item
If additionally $b(n) \in \N^+$ and tends to infinity, then
$a(n)^{b(n)}$ is also MC-finite.
\item
Let  $A \subseteq \N^+$ be non-periodic and  $a(n) =2$ be a constant, hence MC-finite, sequence.
Let $b(n)$ be the sequence
$$
b(n) =
\begin{cases}
1, & \text{if } n \in A; \\
n!+1, & \text{ otherwise}. 
\end{cases}
$$
Then $b(n)$
is MC-finite and oscillates. However $a(n)^{b(n)}$ is not MC-finite. 
\end{enumerate}
\end{proposition}

\subsection{A definability criterion}
In order to prove that a sequence $s(n)$ is MC-finite one can also use a method
due to Blatter and  Specker from 1981
\cite{blatter1981nombre,pr:BlatterSpecker84,specker1990application}. 
It uses logical definability as a sufficient condition.
We let $\FOL$ denote first order logic, $\MSOL$ denote monadic second-order logic, and
$\CMSOL$ denote the logic $\MSOL$ 
augmented with modular counting quantifiers. Details on the definition of $\CMSOL$ are given in Section
\ref{se:periodic}.
In its simplest form, the Specker-Blatter theorem can be stated as follows:

\begin{theorem}[Specker-Blatter theorem]
\label{th:BS-CMSOL}
Let $S_{\phi}(n)$ be
the number of binary relations $R$ on a set $[n]$ that
satisfy a given formula $\phi \in \CMSOL$.
The sequence $S_{\phi}(n)$ is MC-finite or, equivalently, $S^m_{\phi}(n)$ is ultimately periodic for every $m$.
\end{theorem}
The original Specker-Blatter theorem was stated for classes of structures with a finite set of binary relations
definable in monadic second-order logic $\MSOL$. It also works with unary relations added. 
The extension to $\CMSOL$ is due to Fischer and Makowsky \cite{pr:FischerMakowsky03}.
These combined methods 
are abbreviated in the sequel by SB.

\subsection{Comparing the methods}
If one proves MC-finiteness for an integer sequence directly, the proof may be sometimes straightforward,
but also sometimes tricky, and not applicable to other sequences.
In contrast to this, Theorems \ref{th:MC} and \ref{th:BS-CMSOL} are meta-theorems. They only require to
check for some structural data about the sequence $s(n)$, recurrence relations or logical definability.
However, these meta-theorems  are only existence theorems, 
without explicitly giving the required coefficients $c_{i,m}$ that show MC-finiteness.

\begin{example}
We note that the two meta-theorems cannot always be applied to the same integer sequences.
\begin{enumerate}[(i)]
\item
The sequence $s(n)=n^n$ counts the number of unary functions (as binary relations) from $[n]$ to $[n]$,
which is $\FOL$-definable, but not polynomially recursive, as shown by Cadilhac et al.\ \cite{cadilhac2021polynomial}.
However, MC-finiteness can also be established directly without much effort.
\item
There are polynomially recursive sequences over $\Z$ (hence MC-finite) 
that grow as fast as $2^{2^n}$,
e.g., the sequence defined by $a(0) = 2$ and $a(n+1) = a(n)^2$ 
satisfies $a(n) = 2^{2^n}$. 
However, counting the number of $k$ binary relations over $[n]$ is bounded by $2^{kn^2}$.
Hence, Theorem \ref{th:BS-CMSOL} cannot be applied.
Again, MC-finiteness can also be established directly without much effort.
\item
The class of regular simple graphs is not $\CMSOL$-definable.   For a general method for
proving non-definability in $\CMSOL$ the reader should consult Makowsky and Kotek \cite{makowsky2014connection}. 
Hence Theorem \ref{th:BS-CMSOL} cannot be applied
to the sequence $\seqnum{A295193}$, which counts the  number of regular simple graphs on $n$ labelled nodes. 
In contrast to this, $r$-regular graphs are $\FOL$-definable; hence Theorem \ref{th:BS-CMSOL} can be applied
easily to the sequence $\RG(n,r)$ that counts the number of labelled $r$-regular graphs.
The existence of recurrences for fixed $r$ is discussed in McKay \cite{mckay1983applications} and the references cited therein.
For $r=2,3$ this is  $\seqnum{A110040}$.
Recurrences for $r = 0, 1, 2$ are found easily. For $r=3,4$ explicit recurrences were published
by Read and Wormald \cite{read1970some,read1980number}, and for $r=5$ by Goulden et al.\ \cite{goulden1983hammond}. 
The recurrence for $r=5$ is linear but very long.
Gessel 
\cite{gessel1990symmetric} 
showed that $\RG(n,r)$ is holonomic (P-recursive) for every $k \in \N^+$. 
We have not checked whether $\RG(n,r)$ is holonomic over $\Z$.
Read showed that $\RG(n,4)$ is polynomially recursive 
\cite{read1980number},
but the equations given there
do not show that $\RG(n,4)$ is polynomially recursive over $\Z$.
It seems that 
Theorem \ref{th:BS-CMSOL} is the most suitable method to show that for each $r$ the sequence $\RG(n,r)$ is MC-finite.
\end{enumerate}
\end{example}

We will use, like in
Fischer and Makowsky \cite{fischer2011application,ar:FischerMakowsky2022}, 
the logic $\CMSOL$, where we also allow hard-wired constants.
Dealing with hard-wired constants is briefly described in Section \ref{se:constants}.

Clearly, $S_{\phi}(n)$ is computable by brute force, given $\phi$ and $n$.
Specker \cite{specker1990application}, mentions that
$S^m_{\phi}(n) \equiv S_{\phi}(n)$ (mod $m$) can be computed more efficiently, but no details are given.
Only the special case for $Q^m(n)$ is given, where $Q(n)$ is the number of quasi-orders over $[n]$.

\section{More on MC-finiteness}
\label{ap:mc-finite}
\label{se:ProofMC}

\subsection{Polynomial recursive sequences}

Cadilhac \cite{cadilhac2021polynomial}
defines a
\emph{polynomial recursive sequence}
as given by a mutual recurrence in which the recurrence 
relation is a polynomial. That is, we define $d$ sequences in parallel 
by initial values $a_1(0),\ldots,a_d(0)$ and the recurrence
\[
 a_i(n+1) = P_i(a_1(n),\ldots,a_d(n)),
\]
where $P_i$ is a polynomial with rational coefficients. 
We will only consider recurrences for which $a_i(n) \in \mathbb{N}$ for all $i \in [d]$ and $n \ge 0$.
\begin{theorem}[\cite{cadilhac2021polynomial}] \label{thm:CMPPS20}
Let $m$ be a natural number that is relatively prime to all denominators of coefficients of the defining 
polynomials $P_1,\ldots,P_d$. Then the sequences $a_i(n)$ modulo $m$ are eventually periodic.
\end{theorem}
\begin{proof}
Let the polynomials $P_1,\ldots,P_d$ be given by
\[
 P_k(x_1,\ldots,x_d) = \sum_{e \in \mathbb{N}^d} \frac{s_{ke}}{t_{ke}} \prod_{i=1}^d x_i^{e_i},
\]
where $(t_{ke},m) = 1$ for all $k,e$, and the sum has finite support (that is, for each $k$, all but finitely many of the $s_{ke}$ vanish).

Let $\wp\colon \mathbb{Z} \to \mathbb{Z}_m$ be the (mod $m$) mapping. We extend the definition of $\wp$ to the polynomials $P_1,\ldots,P_d$ as follows:
\[
 \wp(P_k)(y_1,\ldots,y_d) = \sum_{e \in \mathbb{N}^d} \frac{\wp(s_{ke})}{\wp(t_{ke})} \prod_{i=1}^d y_i^{e_i},
\]
which is well-defined since $(t_{ke},m) = 1$. Consequently, $\wp(t_{ke})$ is invertible in the ring $\mathbb{Z}_m$.

Elementary number theory shows that
\[
 \wp(P_k(x_1,\ldots,x_d)) = \wp(P_k)(\wp(x_1),\ldots,\wp(x_d)),
\]
and so
\[
 \wp(a_k(n+1)) = \wp(P_k(a_1(n),\ldots,a_d(n))) = \wp(P_k)(\wp(a_1(n)),\ldots,\wp(a_d(n))).
\]

Now consider the mapping $Q\colon \mathbb{Z}_m^d \to \mathbb{Z}_m^d$ given by
\[
 Q(y_1,\ldots,y_d) = (\wp(P_1)(y_1,\ldots,y_d),\ldots,\wp(P_d)(y_1,\ldots,y_d)).
\]
The foregoing shows that 
\[
 (\wp(a_1(n+1)),\ldots,\wp(a_d(n+1))) = Q(\wp(a_1(n)),\ldots,\wp(a_d(n))).
\]

Using the notation $b(n) = (\wp(a_1(n)),\ldots,\wp(a_d(n)))$, we can express this more succinctly as
\[
 b(n+1) = Q(b(n)).
\]
Elementary induction shows that for all $i < j$,
\[
 b(j) = Q^{(j-i)}(b(i)),
\]
where $Q^{(j-i)}$ denotes the composition of $Q$ with itself $j-i$ times.

Since $b(n) \in \mathbb{Z}_m^d$, by the pigeonhole principle, 
the list $b(0),\ldots,b(m^d)$ must contain two identical elements, 
say $b(i) = b(j)$ for some $i < j$. 
This means that $Q^{(j-i)}(b(i)) = b(i)$, and so $b(i + t(j-i)) = b(i)$ for all $t \in \mathbb{N}$. 
Consequently, $b(n)$ is eventually periodic. We conclude that its components, 
$\wp(a_k(n)) \equiv a_k(n)$ (mod $m$), are eventually periodic as well.
\end{proof}

This result raises the following question: what happens for other $m$? 
It turns out that the theorem fails in general for such $m$.

Consider the following sequence $\seqnum{A086714}$:
\[
 a(n+1) = \binom{a(n)}{2}, \quad a(0) = 4.
\]
and put $\hat{a}(n) \equiv a(n)$ (mod $2$).
\begin{theorem} \label{thm:main}
The sequence $\hat{a}(n)$ is not ultimately periodic.
\end{theorem}

The same result holds (with the same proof) for any $a(0) \ge 4$, 
as well as for any recurrence of the form $a(n+1) = (a(n)+b)(a(n)+c)/2$, 
as long as $b,c$ have different parities and $a(0)$ is chosen so that $a(n) \to \infty$.

\subsection{Proof of Theorem \ref{thm:main}}

Let $\beta(n) \equiv a(n)$ (mod $2$). It is not hard to check that the sequence 
$\beta(n), \ldots, \beta(n + k - 1)$ depends only on $a(n)$ (mod $2^k$). 
It turns out that the opposite holds as well: we can determine $a(n)$ (mod ${2^k}$) 
from the values $\beta(n), \ldots, \beta(n + k - 1)$.

\begin{lemma} \label{lem:bijection}
Let $a_r,\beta_r$ be defined as above, except with the initial condition $a_r(0) = r$.
For all $k \ge 1$, the function
\[
 \Phi_k(r) = \beta_r(0), \ldots, \beta_r(k-1)
\]
is a bijection between $\{0,\ldots,2^k-1\}$ and $(0,1)^k$.
\end{lemma}

For example, if $k = 3$, we get the following bijection:
\begin{align*}
\Phi_3(0) &= 000 &
\Phi_3(1) &= 100 &
\Phi_3(2) &= 010 &
\Phi_3(3) &= 111 \\
\Phi_3(4) &= 001 &
\Phi_3(5) &= 101 &
\Phi_3(6) &= 011 &
\Phi_3(7) &= 110
\end{align*}

\begin{proof}
The proof is by induction on $k$. The result is clear when $k = 1$, so suppose $k > 1$.

The first bit of $\Phi_k(r)$ is the parity of $r$, and the remaining bits are 
$\Phi_{k-1}(s)$, where $s \equiv \binom{r}{2}$ (mod $2^{k-1}$). 
To complete the proof, we show that the mapping $r \mapsto s$ is $2$-to-$1$, 
with the two pre-images of every $s$ having different parity.

Indeed, suppose that 
$$
\binom{a}{2} \equiv \binom{b}{2} \pmod{2^{k-1}}
$$ 
for $a,b \in \{0,\ldots,2^k-1\}$. 
Then $a(a-1) \equiv b(b-1)$ (mod $2^k$), and so 
$$
2^k \mid a(a-1) - b(b-1) = (a-b)(a+b-1).
$$

If $a,b$ have the same parities then $a+b-1$ is odd and so $2^k \mid a-b$. 
Since $a,b \in \{0,\ldots,2^k-1\}$, in this case $a = b$.

If $a,b$ have different parities then $a-b$ is odd and so $2^k \mid a+b-1$, 
and so $b \equiv 1-a$ (mod $2^k$) is uniquely defined, and has a parity different from $a$.
\end{proof}

We can now prove Theorem \ref{thm:main}. First we notice that ${a \choose 2} > a$ for 
$a \geq 4$, and so $a(n) \to \infty$. 
Now suppose that the sequence $\beta$ is ultimately periodic, say with period $\beta(N), \ldots, \beta(N+\ell-1)$.

Lemma \ref{lem:bijection} implies that for every $k \ge 1$, the sequence $a(n)$ (mod $2^k$) has period 
$$
a(N) \pmod{2^k}, \ldots, a(N+\ell-1) \pmod{2^k},
$$ and in particular, 
$$
a(N) \equiv a(N+\ell) \pmod{2^k}.
$$ 
We reach a contradiction by choosing $k$ such that $2^k > a(N+\ell)$.


\subsection{Normal sequences}
Let $s(n)$ be an integer sequence, $b \in \N^+$, and $s^b(n) \equiv s(n)$ (mod $b$). 
The sequence $s^b(n)$
is {\em normal} if,  when it is partitioned into substrings of length 
$\ell \ge 1$, then each of the $b^\ell$ possible strings of $[b]^\ell$ appear in $s^b(n)$ with equal limiting frequency. 
It is {\em absolutely normal} if it is normal for every $b$.
The sequence $s^b(n) \equiv s(n)$ (mod $b$) can be viewed as a real number $r_b$ written in base $b$.
A classical theorem  from 1922 by \'Emile Borel says that almost all reals are absolutely normal. 
This is discussed in Everest et al.\  \cite{everest2003recurrence}.
The theorem below shows that MC-finite integer sequences are very rare.

Let $\mathrm{PR}_b$ be the set of integer sequences $s^b(n)$ 
with $s^b(n) \equiv s(n)$ (mod $b$) for some integer sequence $s(n)$.
$\mathrm{PR}_b$ is the projection of all integer sequences to sequences over $\Z_b$.
We think of $\mathrm{PR}_b$ as a set of reals with the usual topology and its Lebesgue measure.
Let $\mathrm{UP}_b \subseteq \mathrm{PR}_b$ be the set of sequences $s^b(n) \in \mathrm{PR}_b$ that are ultimately periodic.

\begin{proposition} 
\label{pr:normal}\ 
\begin{enumerate}[(i)]
\item
Almost all reals are absolutely normal. 
\item
$s(n)$ is MC-finite iff for every $b \in \N^+$ the sequence $s^b(n)$ is ultimately periodic
\item
If $s^b(n)$ is normal for some $b$, then $s(n)$ is not MC-finite. 
\item
$\mathrm{UP}_b \subseteq \mathrm{PR}_b$ has measure $0$.
\end{enumerate}
\end{proposition}
Proving that a specific sequence is normal is usually difficult.
Here is a challenge:
\begin{conjecture}
The binary sequence $\beta(n) \equiv a(n)$ ({\rm mod} $2$) from Theorem \ref{thm:main} is normal with $b=2$. 
\end{conjecture}


\section{Immediate consequences of the Specker-Blatter theorem}
\label{se:immediate}
\subsection{The Bell numbers $B(n)$}

The Bell numbers $B(n)$ count the number of partitions of the set $[n]$.
This is the same as counting the number of equivalence relations over $[n]$,
which is expressible by an $\FOL$-formula. 
Therefore, we immediately get from Theorem \ref{th:BS-CMSOL} that:
\begin{theorem}
\label{th:bell}
The Bell numbers $B(n)$ are MC-finite.
\end{theorem}
The Bell numbers do satisfy some known congruences.
For $m=p$ a prime, they satisfy the Touchard congruence 
$$
B(p+n) \equiv B(n) + B(n+1) \pmod{p}.
$$
However, this is not enough to establish MC-finiteness.

The Bell numbers are not C-finite, because they grow too fast. 
The following estimate is due to De Bruijn and Berend \cite{de1981asymptotic,berend2010improved}.
\begin{proposition}
\label{prop:b-growth}
For every $n \in \N^+$
$$ \left(\frac{n}{e \ln n}\right)^n \leq B(n).$$ 
Furthermore, for every $\epsilon > 0$ there is $n_0(\epsilon)$ such that for all $n \geq n_0(\epsilon)$ 
$$B(n) \leq \left(\frac{n}{e^{1-\epsilon} \ln n}\right)^n.$$
\end{proposition}
Flajolet et al.\ \cite[Proposition VIII.3]{flajolet2009analytic} gives better estimates, but they are not needed here.
Another way to see that Bell numbers are not C-finite is by noticing that they are not holonomic, as shown by Klazar
\cite{klazar2003bell}. There, and in Banderier et al.\ \cite{banderier2002generating}, 
some variations of Bell numbers are also studied:
\begin{definition}\ 
\begin{enumerate}[(i)]
\item
$B(n)_{k,m}$ counts the number of partitions of $[n]$ that have $k$ blocks modulo $m$.
\item
$B(n)^{\pm} = B(n)_{0,2} - B(n)_{1,2}$ are the Uppuluri-Carpenter numbers $\seqnum{A000587}$.
\item
$B(n)^{bc}$ counts the number of {\em bicolored partitions} of $[n]$, that is, the partitions of $[n]$
where the blocks are colored with two non-interchangeable colors $C_1, C_2$,
$\seqnum{A001861}$.
\end{enumerate}
\end{definition}
\begin{theorem}
\label{th:klazar}
The sequences $B(n), B(n)_{k,m}, B(n)^{\pm}, B(n)^{bc} $ are not holonomic, hence not C-finite, but they are
MC-finite.
\end{theorem}
\begin{proof}
In Klazar \cite{klazar2003bell}, and in Banderier et al.\ \cite{banderier2002generating} is shown 
that they are not holonomic. 
To see that they are MC-finite, we apply Theorem \ref{th:BS-CMSOL}.
\begin{enumerate}[(i)]
\item
$B(n)_{k,m}$ is definable in $\CMSOL$. We say that there is a set $X \subseteq [n]$ that intersects every block in
exactly one element, and the size of the set $X$  is $k$ (mod $m$).
\item
$B(n)^{\pm}$ is the difference of two MC-finite sequences, hence MC-finite.
\item
$B(n)^{bc}$ counts the number of binary and unary relations $E, C_1, C_2$ over $[n]$ such that
$E$ is an equivalence relations, $C_1, C_2 \subseteq [n]$ partition $[n]$, and each of them
is closed under $E$.
\end{enumerate}
\end{proof}

\subsection{Counting transitive relations}
The Bell numbers $B(n)$ count the number of equivalence relations $E(n)$ on a set $[n]$.
Similarly we can look at 
the number of linear quasi-orders (linear pre-orders) $\LQ(n)$,
the number of quasi-orders (pre-orders) $Q(n)$,
the number of partial orders $P(n)$, and 
the number of transitive relations $T(n)$ on the set $[n]$.
These integer sequences were analyzed by Pfeiffer \cite{pfeiffer2004counting}.
They are all definable in $\FOL$, and we have
\begin{proposition}
\label{transitive}
$
B(n)=E(n) \leq \LQ(n) \leq P(n) \leq Q(n) \leq T(n).
$
\end{proposition}
\begin{proof}
$E(n) \leq \LQ(n)$: We can turn an equivalence relation into a linear quasi-order
by linearly ordering the equivalence classes.

$\LQ(n) \leq P(n)$: Each linear quasi-order can be made into a partial order 
by replacing every set of mutually equi-comparable elements in a linear quasi-order with an anti-chain.

$P(n) \leq Q(n)$: Each partial order is also a quasi-order.

$Q(n) \leq T(n)$: Each quasi-order is transitive.
\end{proof}
Hence we get using the Specker-Blatter theorem and Proposition \ref{transitive}:
\begin{theorem}
\label{th:1}
The sequences 
$
B(n)=E(n), \LQ(n),  P(n),  Q(n)$  and 
$T(n) $
are MC-finite but not C-finite.
\end{theorem}

\subsection{Stirling numbers of the second kind}
Let $S(n,k)$ be the number of partitions of $[n]$ into $k$ non-empty blocks.
$S(n,k)$ is also known as the Stirling number of the second kind. Clearly,
$$
B(n) = \sum_k S(n,k).
$$
\begin{theorem}
\label{th:stirling}
For fixed $k=k_0$ the sequence $S(n, k_0)$ is C-finite, and hence MC-finite.
\end{theorem}
This can be seen by observing that 
$S(n, k_0)$ has the following rational generating function: 
$$
\sum_{n=0}^\infty S(n,k_0) x^n = \frac{x^{k_0}}{(1-x)(1-2x)\cdots (1-k_0x)}.
$$
Details can be found in Graham et al.\ \cite[7.47]{graham1989concrete}.

\subsection{Lah numbers $\Lah(n)$} 
If we modify the Stirling numbers of the second kind $S(n,k)$ such that the elements in the blocks of the 
partition are ordered between them, 
we arrive at the somewhat less known Lah number $\Lah(n,k)$, $\seqnum{A001286}$, 
introduced by I. Lah \cite{lah1954new} in the context
of actuarial science. 
Good references for Lah numbers are the monographs by Graham et al.\ \cite{graham1989concrete},
and by Charalambides \cite{charalambides2018enumerative}.
The Lah numbers are also coefficients expressing rising factorials $x^{(n)}$ in terms of 
falling factorials $x_{(n)}$.
\begin{proposition}
\label{pr:Lah-identity}
$$
x^{(n)} = \sum_{k=1} \Lah(n,k) x_{(k)}
\text{  and  }
x_{(n)} = \sum_{k=1} (-1)^{n-k} \Lah(n,k) x^{(k)}.
$$
\end{proposition}
Guo \cite{guo2015six} gives six proofs of Proposition \ref{pr:Lah-identity}.
Furthermore we  define $\Lah(n) = \sum_k \Lah(n,k)$.

$\Lah(n)$ counts the number of linear quasi-orders over $[n]$, in other words $\Lah(n) = \LQ(n)$, and
$\Lah(n,k)$ counts the number of linear quasi-orders over $[n]$ with $k$ sets of equi-comparable elements.
Two elements $u,v$ in a quasi-order are {\em equi-comparable} if both $u \leq v$ and $v \leq u$.
This is again definable in first order logic $\FOL$.

There are explicit formulas:
\begin{proposition}
\label{prop:Lah}
\begin{gather}
\Lah(n,k) = \frac{n!}{k!} \cdot {{n-1} \choose {k-1}} =  \sum_{j=0}^n s(n,j) S(j,k) 
\label{eq:lah-1}
\\
\text{   and   } \notag
\\
\Lah(n) = \sum_k \Lah(n,k) = n! \sum_k \frac{1}{k!} \cdot {{n-1} \choose {k-1}}.
\label{eq:lah-2}
\end{gather}
where $s(n,j)$ are the Stirling numbers of the first kind. 
\end{proposition}
For details the reader may consult Comtet \cite{comtet2012advanced}.

There is also a recurrence relation:
\begin{gather}
\Lah(n+1,k) = \Lah(n, k-1) + (n+k) \Lah(n,k).
\label{eq:lah-3}
\end{gather}
But again this is not enough to establish C-finiteness or MC-finiteness, since it is a recurrence
involving both $n$ and $k$.
\begin{theorem}
\label{th:lah}
Both $\Lah(n)$ and $\Lah(n,k_0)$ are MC-finite but not C-finite.
\end{theorem}
\begin{proof}
It follows directly from Equation (\ref{eq:lah-1}), and also from Equation (\ref{eq:lah-3}), 
that for $k=k_0$ fixed the sequence $\Lah(n,k_0)$ is not
C-finite.
MC-finiteness again follows using Theorem 
\ref{th:BS-CMSOL}.
\end{proof}
Note however that the recurrence relation given in Equation (\ref{eq:lah-3})
does not have constant coefficients.

\subsection{Summary so far}
Table \ref{table-1} summarizes the results that are direct consequences of the growth arguments or non-holonomicity (NH),
and the Specker-Blatter theorem \ref{th:BS-CMSOL} (SB).

\begin{table}[h]
\begin{center}
\footnotesize
\begin{tabular}{||l|l|l|l||l|l|l|}
\hline
\hline
Sequence & C-     & Proof & Theorem & MC-       & Proof & Theorem \\
       & finite &       &         & finite    &       &         \\
\hline
\hline
$S(n) = B(n)$ & no & Growth & \ref{th:1} &  yes & SB  & \ref{th:bell} \\
\hline
$S(n,k_o)$ & yes & gen.fun& \ref{th:stirling} &    yes & gen.fun &\ref{th:stirling} \\ 
\hline
$B(n)^{\pm}$ & no & NH & \ref{th:klazar} &    yes & SB &\ref{th:klazar} \\ 
\hline
$B(n)^{bc}$ & no & NH & \ref{th:klazar} &    yes & SB &\ref{th:klazar} \\ 
\hline
\hline
$\LQ(n)$ & no & Growth & \ref{th:1} &   yes & SB &  \ref{th:1} \\
\hline
$Q(n)$ & no & Growth & \ref{th:1} &   yes & SB &  \ref{th:1} \\
\hline
$P(n)$ & no & Growth & \ref{th:1} &   yes & SB &  \ref{th:1} \\
\hline
$T(n)$ & no & Growth & \ref{th:1} &   yes & SB &  \ref{th:1} \\
\hline
\hline
$\Lah(n) = \LQ(n)$ & no & Growth & \ref{th:lah} & yes & SB & \ref{th:lah} \\
\hline
$\Lah(n, k_0)$ & no & Growth & \ref{th:lah} &   yes & SB & \ref{th:lah} \\
\hline
\hline
\end{tabular}
\caption{Direct consequences of the Specker-Blatter theorem.}
\label{table-1}
\end{center}
\end{table}

\section{Restricted set partitions}
\label{se:restricted}
The new results of this paper concern C-finiteness and MC-finiteness
for restricted versions of set partitions.
We have two kinds of restrictions in mind.
The first are {\em positional restrictions}, which impose conditions on the positions of the elements of $[n]$, 
where $[n]$ is equipped with its natural order.
The second are {\em size restrictions}, which impose conditions on the size of the blocks or their number.

\subsection{Global positional restrictions}

\begin{definition}
Let $A$ and $B$ be two blocks of a partition of $[n]$.
\begin{enumerate}[(i)]
\item
$A$ and $B$ are {\em crossing} if there are elements
$a_1, a_2 \in A$ and $b_1, b_2 \in B$ such that 
$a_1 < b_1 < a_2 < b_2$ or
$b_1 < a_1 < b_2 < a_2$.
\item
Let 
$\min{A},\max{A},\min{B},\max{B}$ 
the smallest and the largest elements in $A$ and $B$.
$A$ and $B$ are {\em overlapping} if 
$\min{A} < \min{B} < \max{A} < \max{B}$ or
$\min{B} < \min{A} < \max{B} < \max{A}$.
\item
If $A$ and $B$ are overlapping they are also crossing, but not conversely.
\item 
As shown in
Roman \cite{roman2015introduction},
the number $B(n)^{nc}$ of 
non-crossing set partitions over $[n]$ is one of the interpretations of the Catalan numbers, 
\item
The Bessel number $B(n)^B$, $\seqnum{A006789}$, is the number 
of non-overlapping set partitions over $[n]$. 
It was introduced by Flajolet and Schott
\cite{flajolet1990non}.
\end{enumerate}
\end{definition}
The Catalan numbers $C(n)$ are not holonomic and not MC-finite.
Banderier et al.\ \cite{banderier2002generating}
show that the Bessel numbers $B(n)^B$ are not holonomic. 
Are the Bessel numbers $B(n)^B$ MC-finite?  
The positional restrictions here are {\em global} in the sense that they involve all of the elements
of $[n]$ with their natural order.
For non-holonomic integer sequences $s(n)$ that count the number of set partitions subject to global positional restrictions,
we have currently no tools to decide whether they are MC-finite or not.

Inspired by Broder's work \cite{broder1984r},
various recent papers look at {\em local\/} positional restrictions 
one can impose on
Stirling and Lah numbers, for instance the publications
\cite{wagner1996generalized,nyul2015r,benyi2019some,benyi2019restricted}.
They are local because they only put restrictions on the positions of a fixed number
of elements of $[n]$ with their natural order.

\subsection{Local positional and size restrictions}
Recall that we use $[n]$ to denote the set $\{1, 2, \ldots, n\}$.
We write $S_r(n,k)$ for the number of partitions of $[n+r]$ into $k+r$ non-empty blocks
with the additional condition that the first $r$ elements are in distinct blocks.
The elements $1, \ldots, r$ are called {\em special elements}. The partitions where the first $r$ elements
are in distinct blocks are called $r$-partitions. When dealing with definability we view the special elements
as {\em hard-wired} constants, i.e., constant symbols $a_i, 1 \leq i \leq r$ 
with a fixed interpretation by elements of $[n+r]$.

We define $S_r(n)= B_r(n)$ by
$$
S_r(n) = \sum_k S_r(n,k).
$$
Nyul \cite{nyul2015r} and Shattuck \cite{shattuck2016generalized} define
the sequences $\Lah_r(n,k)$, $\seqnum{A143497}$, and $\Lah_r(n)$ analogously 
with the condition that $a_1 < a_2 < \cdots < a_r$ are in different blocks.

Let $A \subseteq \N$. We write respectively
$S_{A,r}(n) = B_{A,r}(n)$, 
$S_{A,r}(n,k)$,
$\Lah_{A,r}(n)$ and $\Lah_{A,r}(n,k)$
for the number of corresponding partitions where every block has its size in $A$. 

For $r=0$, in the absence of special elements, we just write 
$S_A(n), S_A(n,k), \Lah_A(n)$ and $\Lah_A(n,k)$.
We note that $S_A(n) = B_A(n)$. 
Analogous definitions can be made for $\LQ(n)$, denoted by $\LQ_{A,r}$, and also called $r$-Fubini sequences, 
with OEIS-number $\seqnum{A232472}$.

A set $A \subseteq \N$ is {\em (ultimately) periodic} if there exist $p,n_0 \in \N^+$ such that for all $n \in \N$
($n \ge n_0$)
we have $n \in A$ iff $n+p \in A$.
In other words, the characteristic function $\chi_A(n)$ of $A$ is ultimately periodic in the usual sense,
$\chi_A(n) = \chi_A(n+p)$ ($n \geq n_0$).

\subsection{Main results for restricted set partitions}
Our  results for restricted set partitions are summarized in Tables
\ref{table-2}, 
\ref{table-3},
\ref{table-4}, and 
\ref{table-5} 
below.
The abbreviation FM, SB* and NH refer respectively to 
the proof method of Fischer and Makowsky \cite{fischer2008linear,fischer2011application}, 
to the extension of the Specker-Blatter theorem to allow a fixed finite set of special elements as hard-wired constants,
and to proofs of non-holonomicity.
The results listed in Table \ref{table-4} 
also hold for $\LQ_{A,r}$, the $r$-Fubini numbers, and other similarly defined sequences.

\begin{table}[h]
\begin{center}
\footnotesize
\begin{tabular}{|l||l|l|l||l|l|l|}
\hline
\hline
Sequence & C-     & Proof & Theorem & MC-       & Proof & Theorem \\
       & finite &       &         & finite    &       &         \\
\hline
\hline
$S_A(n) = B_A(n)$ & no & Growth & \ref{th:g-bell} & yes & SB* & \ref{th:A-periodic} \\
\hline
$S_A(n,k_0)$ & yes & FM & \ref{th:c-fin} & yes &  FM &  \ref{th:c-fin} \\
\hline
$\Lah_A(n) = \LQ_A(n)$ & no & Growth & \ref{th:g-lah} & yes & SB* & \ref{th:A-periodic} \\
\hline
$\Lah_A(n, k_0)$ & no & Growth & \ref{th:g-lah} & yes & SB* & \ref{th:A-periodic} \\
\hline
\hline
\end{tabular}
\caption{With ultimately periodic $A$ only.}
\label{table-2}
\end{center}
\end{table}

\begin{table}[h]
\begin{center}
\footnotesize
\begin{tabular}{|l||l|l|l||l|l|l|}
\hline
\hline
Sequence & C-     & Proof & Theorem & MC-       & Proof & Theorem \\
       & finite &       &         & finite    &       &         \\
\hline
\hline
$S_r(n)=B_r(n)$ & no & Growth & \ref{th:g-bell} & yes & SB* &  \ref{co:SB*} \\
\hline
$S_r(n, k_0)$ & yes & FM &\ref{th:c-fin} &  yes & FM &  \ref{th:c-fin} \\
\hline
\hline
$\Lah_r(n, k_0)$ & no & Growth &\ref{th:g-lah} &  yes & SB* & \ref{co:SB*} \\
\hline
\hline
\end{tabular}
\caption{With hard-wired constants only.}
\label{table-3}
\end{center}
\end{table}

\begin{table}[h]
\begin{center}
\footnotesize
\begin{tabular}{|l||l|l|l||l|l|l|}
\hline
\hline
Sequence & C-     & Proof & Theorem & MC-       & Proof & Theorem \\
       & finite &       &         & finite    &       &         \\
\hline
\hline
$S_{A,r}(n)= B_{A,r}(n)$ & no & Growth & \ref{th:bell-A} &  yes & SB* &   \ref{co:SB*} \\
\hline
$S_{A,r}(n, k_0)$ & yes & FM & \ref{th:c-fin}  & yes & FM &  \ref{th:c-fin} \\
\hline
$\Lah_{A,r}(n, k_0)$ & no & Growth & \ref{th:bell-A} & yes & SB* & \ref{co:SB*} \\
\hline
\hline
\end{tabular}
\caption{With ultimately periodic $A$ and hard-wired constants.}
\label{table-4}
\end{center}
\end{table}

\begin{table}[h]
\begin{center}
\footnotesize
\begin{tabular}{|l||l|l|l||l|l|l|}
\hline
\hline
Sequence & C-     & Proof & Theorem & MC-       & Proof & Theorem \\
       & finite &       &         & finite    &       &         \\
\hline
\hline
$B(n)^B$ & no & NH & \cite{banderier2002generating} &  ??? & ??? &  ---  \\
\hline
$B(n)^{nc} = C(n)$ & no & NH & \cite{roman2015introduction} &  no & 
\cite{roman2015introduction} & \cite{banderier2002generating} \\
\hline
\hline
\hline
\end{tabular}
\caption{With global positional restrictions.}
\label{table-5}
\end{center}
\end{table}

\section{Proofs for the restricted cases}
\label{se:rproofs}
For the analysis of MC-finiteness in the restricted cases we need some additional tools.

\subsection{An explicit computation of $S_A(n,k)$}
\label{se:explicit}

Let $A\subseteq \NN$. The sequence
$S_A(n,k)$ counts the number of partitions of $[n]$ into $k$ sets with cardinalities in $A$. 

We shall compute $S_A(n,k)$ explicitly. For $A = \N^+$ this will give also an alternative way of computing
$S(n,k)$, the Stirling numbers of the second kind. 
Charalambides uses this method in his monograph \cite[Theorem 8.6]{charalambides2018enumerative}.
Stanley proves it in very different notation in \cite[Chapter 1, Exercise 45]{bk:Stanley86}.

We introduce some suitable notation.
Let $A\subseteq \NN$.  Then
$S_A(n,k)$ counts the number of partitions of $[n]$ into $k$ sets with cardinalities in $A$. 
Let $V(A,k)$ be the set of $k$-tuples $(L_1, \ldots, L_k)$
of elements of $A$ ordered in non-decreasing order, 
with $\sum_{i=1}^k =n$,
i.e.,
$$
V(A,k)=\{(l_1,l_2,\ldots,l_k)\in A^k:0<l_1\leq l_2\leq\cdots\leq l_k,\sum_{i=1}^k l_i=n\}.
$$
For $(l_1,l_2,\ldots,l_k)\in V(A,k)$ 
define $g(m;l_1,l_2,\ldots,l_k)$ to be the number of times $m$ appears in the $k$-tuple $(l_1,l_2,\ldots,l_k)$, 
and 
$$f(l_1,l_2,\ldots,l_k)=\prod_{m\in(l_1,l_2,\ldots,l_k)}g(m;l_1,l_2,\ldots,l_k)! .$$ 
Next we define the sequence $(c_i)$ inductively as follows:
$$c_1 =n \ \text{ and } \ c_{i+1} = c_i - l_i.$$
Hence $c_i = n - \sum_{j=1}^{i-1} l_j$.
\begin{theorem}
\label{th:explicit}
Let $A\subseteq \NN$.
Then
$$
S_A(n,k)=
\sum_{(l_1,l_2,\ldots,l_k)\in V(A,k)}\frac{1}{f(l_1,l_2,\ldots,l_k)}
\prod_{i=1}^k {c_i \choose l_i}.
$$
\end{theorem}
\begin{proof}
To partition $[n]$ into $k$ sets with cardinalities in $A$, we proceed as follows: 
first we select the cardinalities of the $k$ sets. 
This corresponds to picking an element $(l_1,l_2,\ldots,l_k) \in V(A,k)$. 
To construct a partition of $n$, we choose $l_1$ elements from $[n]$, then $l_2$ elements from $[n-l_1]$ etc. 
Finally, we divide by $f(l_1,l_2,\ldots,l_k)$ to account for double counting 
of tuples with equal entries.
\end{proof}


\subsection{Ultimate periodicity of $A$}
\label{se:periodic}

Recall that a formula with a {\em modular counting quantifier $C_{b,m}x \phi(x)$} is true in a structure $\fB$ if
the cardinality of the set of elements in $\fB$ that satisfy $\phi(x)$,
satisfies 
$$
|\{a \in B: \phi(a) \}| \equiv \modd{b} {m}.
$$
$\CMSOL$ is the logic obtained from $\MSOL$ by extending it with all the modular counting
quantifiers $C_{b,m}$.
In \cite{pr:FischerMakowsky03} the Specker-Blatter theorem was extended to hold for $\CMSOL$, as already
stated in Theorem \ref{th:BS-CMSOL}.
$\CMSOL$ is also needed to prove the following lemma:

\begin{lemma}
\label{le:periodic}
Let $A$ be ultimately periodic and $\psi(x)$ be a formula of $\CMSOL$.
Then there is a sentence $\psi_A \in \CMSOL$ such that
in every finite structure $\fB$ we have
$$\fB \models \psi_A \text{ iff }|\{b \in B: \psi(b) \}| \in A.$$
\end{lemma}
\begin{proof}
If  
$$
A = A_{a,m}= \{ n \in \N: n \equiv \modd{a} {m} \}
$$ 
the formula $\psi_A$
is the sentence $C_{a,m} x \psi(x)$.

Next we observe that if $A$ is ultimately periodic,
then there are finitely many $a_1, \ldots, a_k$ and $q$
such that $A = \bigcup_{i=0}^k A_i$ with $A_0 \subseteq [q]$ and 
$$
A_i = \{ n > q: n \equiv \modd{a_i} {m} \}.
$$
We proceed in steps:
\begin{enumerate}[(i)]
\item
$\exists^{\geq k}x\psi(x):=\exists x_1,\ldots,x_k \bigwedge_{i=1}^k\psi(x_i)\wedge\bigwedge_{1\leq i<j\leq k}(x_i\neq x_j)$
says that there are at least $k$ elements that satisfy $\psi(x)$.
\item
$\exists^{=k}x\psi(x):=\exists^{\geq k}x\psi(x)\wedge\neg\exists^{\geq k+1}x\psi(x)$
says that there are exactly $k$ such elements.
\item
$\psi_{A_0}:=
(\exists^{<q} x \psi(x)
\rightarrow
\bigvee_{j\in A_0}\exists^{=j}x\psi(x))$
says that if the number of elements satisfying $\psi(x)$ is at most $q$
then the number of such elements has exactly one of the cardinalities in $A_0$.
\item
$\psi_{A_i}:=\exists^{\geq q+1}x\psi(x)\wedge C_{a,m}x\psi(x)$
says that, if the number of elements satisfying $\psi(x)$ is bigger or equal than $q$,
then the number such elements equals $a_i$ (mod $m$).
\item
$\psi_A(x):= \bigvee_{i=0}^k \psi_{A_i}(x)$ is the required formula.
\end{enumerate}
\end{proof}

Theorem \ref{th:BS-CMSOL} together with Lemma \ref{le:periodic} immediately gives the following result:
\begin{theorem}
\label{th:A-periodic}
Assume that $A$ is ultimately periodic.
Then the sequences
$B_A(n)= S_A(n)$, $\Lah_A(n)$, and $\Lah_A(n, k_0)$ are MC-finite.
\end{theorem}

\subsection{Growth arguments}

We first discuss growth arguments for $B_A(n)= S_A(n)$,
$\Lah_A(n)$, and $\Lah_A(n, k_0)$.
\begin{theorem}
\label{th:bell-A}
Let $A \subseteq \N$ be infinite and ultimately periodic. Then the sequences
$B_A(n)= S_A(n)$, $\Lah_A(n)$, and $\Lah_A(n, k_0)$ are not C-finite.
\end{theorem}
\begin{proof}
First we prove it for $B_A(n)$ and 
$$
A = A_m = \{ n \in \N: n \equiv \modd{0} {m} \}.
$$ 
Let $P_1, \ldots , P_k$ be a partition of $[n]$.
We replace in each $P_i$ every element by $m$ elements. This gives us a partition of $[mn]$ with each block
of size in $A_m$. Hence 
$$
P_A(mn) \geq P(n) \geq \left(\frac{n}{e \ln n}\right)^n
$$
or, equivalently,
$$
P_A(n) \geq P(\lfloor n/m \rfloor) \geq 
\left(
\lfloor n/m \rfloor
e \ln \lfloor  n/m  \rfloor
\right)^{\lfloor  n/m  \rfloor},
$$
which still grows superexponentially.

Next we assume that 
$$
A = A_{k,a,m}= \{ n \in \N: n \equiv \modd{a} {m}  \text{ for}\  n \geq k \}.
$$
We proceed as before, but additionally add $mr+a$ elements to each block, for $r$ large enough.
Finally, we note that for every infinite (ultimately) periodic set $A$  
there is a set $A_{k, a,m}$ for some $k, a, m \in \N^+$ such that 
$ A_{k,a,m} \subseteq A$.

For $\Lah_A(n)$ and $\Lah_A(n, k_0)$ we proceed similarly using Proposition \ref{prop:Lah}.
\end{proof}

Next we discuss growth for 
$\Lah(n,k_0)$, $\Lah(n) = \sum_k \Lah(n,k)$ and $\Lah_r(n, k_0)$.
We have seen in Proposition \ref{prop:b-growth} that 
$$
\left(\frac{n}{e \ln n}\right)^n \leq B(n) \leq \left(\frac{n}{e^{1-o(1)} \ln n}\right)^n.
$$
We now prove a lemma.
\begin{lemma}
\label{le:bell-3}
$B_r(n) \geq B(n)$.
\end{lemma}
\begin{proof}
Every partition of $[n]$ gives rise to at least one partition of $[n+r]$ where the first $r$ elements are in
distinct blocks containing only one element.
\end{proof}

From  Propositions \ref{prop:c-finite}, \ref{transitive},
and \ref{le:bell-3}, we get the following result:
\begin{theorem}
\label{th:g-bell}
The sequences $B(n)$ and $B_r(n)$
are not C-finite.
\end{theorem}


\begin{lemma}
\label{le:lah-1}
For $k_0, r$ fixed, the Lah number $\Lah(n,k_0)$ satisfies the following:
\begin{enumerate}[(i)]
\item
$\Lah(n,k_0) = {{n-1} \choose {k_0-1}} \frac{n!}{k_0!}$,
\item
$\Lah(n) \geq \Lah(n, k_0)$, and
\item
$\Lah_r(n, k_0) \geq \Lah(n, k_0)$.
\end{enumerate}
\end{lemma}
\begin{proof}
(i) is from \cite{lah1954new}. (ii) follows from (i), and (iii) is proved like Lemma \ref{le:bell-3}.
\end{proof}

This immediately gives
\begin{theorem}
\label{th:g-lah}
Let $k_0$ be fixed. 
The sequences 
$\Lah(n,k_0)$, 
$\Lah_r(n, k_0)$, and 
$\Lah(n) = \sum_k \Lah(n,k)$ 
are not C-finite.
\end{theorem}

\subsection{Hard-wired constants}
Recall that a constant is {\em hard-wired} on $[n]$ if its interpretation is fixed.

The Specker-Blatter theorem is originally proved for classes of structures with
a finite number of binary relations. 
Fischer showed in 2002 that it is false for one quaternary relation \cite{ar:Fischer02}.
Fischer and Makowsky
announced recently that it is also false for one ternary relation \cite{ar:FischerMakowsky2022}.

The Specker-Blatter theorem remains true when adding a finite number of unary relations.
This is so because a unary relation $U(x)$ can be expressed as a binary relation
$R(x,x)$ that is false for $R(x,y)$ when $x \neq y$.

Adding constants comes in two flavors, with variable interpretations, or hard-wired.
Assume we want to count the number of unary predicates $P$ over $[n]$ that
contain the interpretation 
of a constant symbol $c$.
There are $n$ possible interpretations for $c$ and $2^{n-1}$ interpretations for sets not containing $c$,
hence $n2^{n-1}$ many such sets.
However, if $c$ is hard-wired to be interpreted as $1 \in [n]$, there are only $2^{n-1}$ many such sets.

Constants can be represented as unary predicates where their interpretation is a singleton.
If we do this, the Specker-Blatter theorem holds, but we cannot model the $r$-Bell numbers like this.
To prove that the $r$-Bell numbers are MC-finite one has to deal with $r$ many hard-wired constants.
Adding a finite number of hard-wired constants needs some work.
In Section \ref{se:constants} we show how to eliminate a finite number of hard-wired constants
for the case of $S_r(n)$. The proof generalizes. Fischer and Makowsky \cite{ar:FischerMakowsky2022} proved
the most general version.
\begin{theorem}
\label{th:SB*}
Let $\tau_r$ be a vocabulary with finitely many binary and unary relation symbols, and $r$ hard-wired constants.
Let $\phi$ be a formula of 
$\CMSOL(\tau_r)$.
Then $S_{\phi}(n)$ is MC-finite.
\end{theorem}
\begin{corollary}
\label{co:SB*}
The sequences
$S_r(n)=B_r(n)$, 
$S_{A,r}(n)= B_{A,r}(n)$, 
$\Lah_r(n, k_0)$, 
and  $\Lah_{A,r}(n, k_0)$
are MC-finite.
\end{corollary}

\subsection{Eliminating hard-wired constants}
\label{se:constants}

Let $\mathfrak{S}_r(n) =( [r+n], a_1, \ldots , a_r, E)$ be the structures over $[r+n]$ 
where $E$ is an equivalence relation and the $r$ elements $a_1, \ldots , a_r$  are in different equivalence classes.
The number $S_r(n)$ counts the number of such structures on $[r+n]$.

Let $\mathfrak{E}_r(n)$ be a structure
over $[n]$ that consists of the following:
\begin{enumerate}[(i)]
\item
The relation
$E(x,y)$ is an equivalence relation over $[n]$;
\item
There are $r$ unary relations $U_1, \ldots, U_r$ on  $[n]$;
\item
The sets $U_i(x)$ are disjoint;
\item
Each $U_i(x)$ is either empty or consists of  exactly one equivalence class of $E$;
\end{enumerate}
Let $E_r(n)$ be the number of such structures over $[n]$.

\begin{lemma}
For every $r,n \in \N^+$ there is a bijection $f$ between the structures $\mathfrak{E}_r(n)$ over $[n]$
and the structures $\mathfrak{S}_r(n)$ over $[r+n]$,
hence we have $E_r(n) = S_r(n)$.
\end{lemma}
\begin{proof}
Given a structure $\mathfrak{S}_r(n)$ we define $f(\mathfrak{S}_r(n))$
as follows:
\begin{enumerate}[(i)]
\item
The universe of $f(\mathfrak{S}_r(n))$ is $\{r+1, \ldots, r+n\}$.
\item
If for $i \leq r$ the set $\{i\}$ is a singleton equivalence class, we put $U_i =\emptyset$.
If there is an equivalence class $E_i$ that strictly contains 
$\{i\}$, we define $U_i = E'_i = E_i \setminus \{i\}$.
\item
$E'$ is the equivalence relation induced by $E$ over $\{r+1, \ldots, r+n\}$.
\end{enumerate}
Conversely, given a structure $E_r(n) = ([n], E, U_1, \ldots, U_r)$
we define $g(E_r(n))$ as follows:
\begin{enumerate}[(i)]
\item 
The universe of $g(E_r(n))$ is $[n+r]$ and the equivalence relation $E'$ is defined
by defining its equivalence classes.
\item
If $U_i$ is empty for some $i \in [r]$ the singleton $\{i\}$  is an equivalence class of $E'$.
If $U_i$ is not empty, then the equivalence class of $E'$ that contains $i$ is $U_i \cup \{i\}$.
\item
If $C$ is an equivalence class of $E$ such that
$U_i \neq C$ for all $i \in [r]$,  then $C$ is an equivalence class for $E'$.
\end{enumerate}
It is now easy to check that $f,g$ are bijections and inverses of each other.
\end{proof}

\begin{remark}\ 
\begin{enumerate}[(i)]
\item 
Clearly the class of structures $E_r(n)$ as defined here is $\FOL$-definable.
Hence we can apply the Specker-Blatter theorem and conclude that
$S_r(n)$ is MC-finite.
\item
If $A$ is ultimately periodic
then $S_{A,r}(n)$ is also MC-finite.
To see this we note that
for $S_{A,r}(n)$ all the equivalence classes $C$  satisfy $|C| \in A$.
This means that in a structure $\mathfrak{E}_{A,r}(n)$
the equivalence classes $C$ satisfy $|C| \in A$, if they do not contain a $U_i$.
Otherwise they satisfy $|C| \in A'$ where $A' = \{ a-1: a \in A \}$.
If $A$ is ultimately periodic, so is $A'$ and both are definable in $\CMSOL$.
\item
For the Lah numbers $L_{r}(n)$ and $L_{A,r}(n)$ we proceed likewise by replacing the equivalence relation
by a linear quasi-order.
For every $i$ we add two  further unary relations and the appropriate conditions 
in order to take care of the ordering of the special elements.
Hence both $L_{r}(n)$ and $L_{A,r}(n)$ are MC-finite.
\end{enumerate}
\end{remark}

\section{Proving C-finiteness}
\label{se:fm}

In this section we explain a special case of the method used by Fischer and Makowsky in \cite{fischer2008linear}
to prove C-finiteness.
It is based on counting partitions of graphs satisfying additional properties and computing these partitions for 
iteratively constructed graphs.

\subsection{Counting partitions with a fixed number of blocks}
Let $G = (V(G), E(G))$ be a graph, and $k_0 \in \N$.  We look at partitions $P_1, \ldots, P_{k_0} \subseteq V(G)$ 
of $V(G)$ that can be described
in the logic $\CMSOL$.  The following are three typical examples:
\begin{example}\ 
\begin{enumerate}[(i)] 
\item
The underlying sets of $G[P_i(G)]$ form a partition of $V(G)$ without further restrictions.
\item
For each $i \leq k_0$ the induced graph $G[P_i(G)]$ is edgeless (proper coloring).
\item
Let $\mathcal{C}$ be a graph property.
For each $i \leq k_0$ the set $G[P_i(G)]$  is in $\mathcal{C}$ ($\mathcal{C}$-coloring).
\end{enumerate}
\end{example}

We look at the counting function
$$
f_{\phi}(G) =
| \{ P_1, \ldots, P_{k_0} \subseteq V(G): \phi(P_1, \ldots, P_{k_0}) \}|,
$$
defined using an $\CMSOL$-formula $\phi$.

Let $A \subseteq \N$ be an ultimately periodic set.
We also look at the  restricted counting function
$$
f_{\phi, A}(G) =
| \{ P_1, \ldots, P_{k_0}: \phi(P_1, \ldots, P_{k_0}) \text{  and  } |P_i| \in A \}|.
$$

Finally, we also allow graphs with a fixed number of distinct 
vertices, which may appear in the formula $\phi$.

\subsection{Iteratively constructed graphs}
\begin{definition}\ 
\begin{enumerate}[(i)]
\item
A {\em $k$-colored graph} is a graph $G$ together with subsets $V_i \subseteq V(G), i \in [k]$ 
such that $V_i \cap V_j =\emptyset $ for $i\neq j$.
\item
A {\em basic operation} on $k$-colored graphs is one of the following:
\begin{itemize}
\item $\Add_i$: add a new vertex of color $i$ to $G$.
\item $\Recolor_{i,j}$: recolor all vertices with color $i$ to color $j$ in $G$.
\item $\Uncolor_{i}$: remove the color of all vertices with color $i$. Uncolored vertices cannot be recolored again.
\item $\AddEdges_{i,j}$: add an edge between every vertex with color $i$ and every vertex with color $j$ in $G$.
\item $\DeleteEdges_{i,j}$: delete all edges between vertices with color $i$ and vertices with color $j$ from $G$.
\end{itemize}
\item
A unary operation $F$ on graphs is {\em elementary} if $F$ is a finite composition of basic 
operations on $k$-colored graphs (with $k$ fixed). 
\item
We say that a sequence of graphs $\{G_n\}$ is {\em iteratively constructed} 
if it can be defined by fixing a graph $G_0$ and defining $G_{n+1}=F(G_n)$ for an elementary operation $F$.
\end{enumerate}
\end{definition}

\begin{example}
\label{exIterativelyConstructed}
The following sequences are iteratively constructed:
\begin{enumerate}[(i)]
\item The complete graphs $K_n$ can be constructed using two colors: 
Fix $G_0$ to be the empty graph. 
Given a graph $G_n$, 
the operation $F$ 
adds a vertex with color $2$, 
adds edges between all vertices with color $2$ and color $1$, and recolors all vertices with color $2$ to color $1$.
\item The paths $P_n$ can be constructed using three colors: 
Fix $G_0$ to be the empty graph. 
Given a graph $G_n$, 
the operation $F$ 
adds a vertex with color $3$, adds edges between all vertices with colors $2$ and $3$, 
recolors all vertices with color $2$ to color $1$, and recolors all vertices with color $3$ to color $2$.
\item The cycles $C_n, n \geq 3$ can be constructed by first constructing a path $P_n$ where the first and the last element
have colors $1$ and $2$ different from the remaining vertices. Then we connect the first and last element of $P_n$
by an edge. This needs $5$ colors, but is not iterative.
To make it an iterative construction we proceed as follows.
Given a cycle $C_n$ with with two neighboring vertices of color $1$ and $2$, uncolor all the other vertices and
remove the edge $(1,2)$. Then add a new vertex with color $3$, make edges $(1,3)$ and $(3,2)$, uncolor the 
old vertices colored by $1$, 
and then recolor $3$ to have color $1$.
\end{enumerate}
\end{example}

\begin{remark}
In Fischer and Makowsky \cite{fischer2008linear} 
there was an additional operation allowed:
\begin{itemize}
\item $\Duplicate$: Add a disjoint copy of $G$ to $G$.
\end{itemize}
It was assumed erroneously that $\Duplicate$ behaves like a unary operation on graphs.
Although it looks like a unary operation on graphs, the sequence of graphs
$$
G_0 = E_1, G_{n+1} = \Duplicate(G_n)
$$
grows too fast and does not fit the framework that the authors have envisaged in \cite{fischer2008linear}.
\end{remark}



\subsection{The FM method}
In this framework Fischer and Makowsky \cite{fischer2008linear} proved the following result.
\begin{theorem}[The FM-theorem]
\label{th:FM}
Let $G_n$ be an iteratively constructed sequence of graphs, $A \subseteq \N$ be ultimately periodic,  and  define
\begin{align*}
f_{\phi}(G_n) &=  | \{ P_1, \ldots, P_{k_0} \subseteq V(G_n): \phi(P_1, \ldots, P_{k_0}) \}|  \\
& = \sum_{\substack{
P_1, \ldots, P_{k_0} \subseteq V(G_n): \\
\phi(P_1, \ldots, P_{k_0})
}}
 1 ; \\
f_{\phi, A}(G_n) &= | \{ P_1, \ldots, P_{k_0} \subseteq V(G_n): \phi(P_1, \ldots, P_{k_0}) \ {\rm and} \  |P_i| \in A \}| \\
&= \sum_{\substack{
P_1, \ldots, P_{k_0} \subseteq V(G_n):  \\
\phi(P_1, \ldots, P_{k_0}) \ \rm{and} \  |P_i| \in A 
}}
1,
\end{align*}
where $\phi \in \CMSOL$.
Then the sequences $f_{\phi}(G_n)$ 
and
$f_{\phi, A}(G_n)$ are C-finite.
\end{theorem}

\begin{remark}
We use unary predicates for the partition, to make sure that the formula $\phi$ is in $\CMSOL$.
Let $k_1$ be the number of unary predicates that are not tied to hard-wired elements.
If we want to disregard the labeling of the unary predicates that are not tied to hard-wired constants, 
we divide by $(k_1)!$.
This does not affect C-finiteness, since $k_1$ is a constant.
In the proof of Theorem  \ref{th:c-fin} below we have $k_1 = k_0-r$.
\end{remark}


We now use Theorem \ref{th:FM} to prove the following result:
\begin{theorem}
\label{th:c-finite}
\label{th:c-fin}
Let $A$ be ultimately periodic, $r, k_0 \in \N$. Then
$S(n,k_0)$,
$S_A(n,k_0)$,
$S_r(n,k_0)$ and
$S_{A,r}(n,k_0)$
are C-finite.
\end{theorem}
\begin{proof}
It suffices to prove it for $S_{A,r}(n,k_0)$. 
The other cases can be obtained by setting 
$r=0$ and/or $A= \N$.

We have to show that
$S_{A,r}(n,k_0)$
is of the form 
$f_{\phi, A}(G_n)$.
We define an iteratively constructed sequence of graphs $G =(V(G), E(G), v_1, \ldots, v_r)$
with $r$ distinct vertices as follows.
$G_0 = (K_r, v_1, \ldots, v_r)$.
$G_{n+1} = G_n \sqcup K_1$.

Now take $\phi(P_1, \ldots , P_{k_0}, v_1, \ldots , v_r)$,
which says that the $P_i$'s form a partition and for each $i \leq r$  
the distinguished vertex $v_i$ belongs to $P_i(G)$.
\end{proof}

Further details are given in Section \ref{se:c-finite}.

\section{Proof of Theorem \ref{th:FM} and its applications}
\label{se:c-finite}

In order to prove Theorem \ref{th:FM} we use Theorem \ref{th:FMapp} below.
For this we have to introduce the definition of $\CMSOL$-definable graph polynomials.

\subsection{$\CMSOL$-definable graph polynomials}
\begin{definition}
Let $\Z$ be the ring of integers.  We consider polynomials over 
$\Z[\bar{x}]$. 
For a $\CMSOL$-formula for graphs 
$\phi(\bar{v})$ with $\bar{v}= (v_1, \ldots , v_s)$, define $\card_G(\phi)$ to be the cardinality of subsets of $V(G)^s$ 
defined by $\phi$.
The extended $\CMSOL$ graph polynomials are defined recursively. We first
define the {\em extended $\CMSOL$-monomials}.  
Let $\phi(\bar{v}) \in \CMSOL$. 
An extended $\CMSOL$-monomial is a term of one of the following possible forms:
\begin{itemize}
\item $x^{\card_G(\phi)}$ where $x$ is one of the variables of $\bar{x}$.
\item $x_{(\card_G(\phi))}$ i.e., the falling factorial of $x$.
\item ${x \choose \card_G(\phi)}$.
\item $\prod_{\bar{v} \in V(G)^s:\phi(v)}t(\bar{x})$
\\
Here $\bar{v}$ ranges over tuples of vertices of $G$,
$t(\bar{x})$ is a term in $\ZZ[\bar{x}]$, and $\bar{x}$ are indeterminates of the polynomial.

\end{itemize}
The {\em extended $\CMSOL$ graph polynomials} are obtained from the monomials by
closing  under finite addition and multiplication.
Furthermore, they are closed under
summation over subsets of $V(G)$ of the form 
$$\sum_{U:\phi(U)} t(\bar{x}),$$
where $\phi$ is a $\CMSOL$-formula with free set variables $U$, and $t(\bar{x})$ is a term in the indeterminates $\bar{x}$.
They are also closed under multiplication over elements of $V(G)^s$ of the form 
$$\prod_{\bar{v} \in V(G)^s:\phi(v)}t(\bar{x}).$$
\end{definition}

\begin{lemma}
\label{le:FM}
The counting functions from Theorem \ref{th:FM}, namely,
\begin{align*}
f_{\phi}(G_n) &=  | \{ P_1, \ldots, P_{k_0} \subseteq V(G_n): \phi(P_1, \ldots, P_{k_0}) \}| \\
& = \sum_{\substack{
P_1, \ldots, P_{k_0} \subseteq V(G_n): \\
\phi(P_1, \ldots, P_{k_0})
}}
 1 , \\
f_{\phi, A}(G_n) &= | \{ P_1, \ldots, P_{k_0} \subseteq V(G_n): \phi(P_1, \ldots, P_{k_0}) \text{  and  } |P_i| \in A \}| \\
& = \sum_{\substack{
P_1, \ldots, P_{k_0} \subseteq V(G_n):  \\
\phi(P_1, \ldots, P_{k_0}) \text{ and } |P_i| \in A 
}}
1
\end{align*}
are $\CMSOL$-definable graph polynomials without indeterminates, 
provided $\phi \in \CMSOL$ and $A$ is ultimately periodic.
\end{lemma}

We first state a theorem from Fischer and Makowsky \cite[Theorem 1]{fischer2008linear}:
\begin{theorem}
\label{th:FMapp}
Let $F$ be an elementary operation on graphs, $\{G_n:n\in \NN\}$ an $F$-iterated sequence of graphs, 
and $P$ an extended $\CMSOL$-definable graph polynomial. 
Then the sequence $P(G_n)$ is C-finite, 
i.e., there exist polynomials $p_1,p_2,\ldots,p_k\in \ZZ[\bar{x}]$ such that for sufficiently large $n$,
$$
P(G_{n+k+1})=\sum_{i=1}^k p_iP(G_{n+i}).
$$
\end{theorem}
\begin{proof}[Proof of Theorem \ref{th:FM}]
Take for $P$ the counting functions from
Lemma \ref{le:FM} and apply Theorem \ref{th:FMapp}.
\end{proof}

\subsection{Proofs of C-Finiteness}

Now we give the details for the proof of Theorem \ref{th:c-finite}.
However, instead of using Theorem \ref{th:FM}, we use Theorem \ref{th:FMapp} directly by exhibiting an
appropriate iteratively constructible sequence of graphs.
\begin{proposition}
\label{R1}
Fix $k_0\in \NN$. Then  $S(n,k_0)$ is a C-finite sequence.
\end{proposition}
\begin{proof}
Let $\cP$ be the graph property 
$\cP=\{K_n:n\geq 1\}$ 
of cliques with at least one vertex 
and define $G_n=K_n$. 
Note that a $\cP$-coloring of $G_n$ with $k_0$ colors is a partition of $V(G_n)$ into exactly $k_0$ non-empty color classes, 
so $H_{\cP}(G_n,k_0)=S(n,k_0)$. We want to apply the FM-theorem. 
First we note that the sequence $G_n$ is iteratively constructible in the sense of
Example \ref{exIterativelyConstructed}
or  Fischer and Makowsky \cite[Proposition 2]{fischer2008linear}.
Hence $H_{\cP}$ is an extended $\CMSOL$ graph polynomial 
and we can use Theorem \ref{th:FMapp}.
\end{proof}

\begin{proposition}
\label{R2}
Fix $k_0\in \NN$. Then  $S_r(n,k_0)$ is a C-finite sequence.
\end{proposition}
\begin{proof}
Let $\cP$ be the graph property of edgeless graphs with at least one vertex, i.e., $\cP=\{\bar{K_n}:n\geq 1\}$, 
and define $G_n=K_r\cup \bar{K_n}$. Note that a $\cP$-coloring of $G_n$ with $k_0+r$ colors 
is a partition of $V(G_n)$ into exactly $k_0+r$ non empty color classes, 
such that every vertex in $V(K_r)\subseteq V(G_n)$ is in a different color class, 
so $H_{\cP}(G_n,k_0+r)=S_r(n,k_0)$. We want to apply the FM-theorem. 
First we note that the sequence $G_n$ is iteratively constructible: 
put $G_0=K_r$. Now given $G_n$, we construct $G_{n+1}$ by adding a disjoint vertex.
Hence $H_{\cP}$ is again an extended $\CMSOL$ graph polynomial 
and we can use Theorem \ref{th:FMapp}.
\end{proof}

\begin{proposition}
\label{R3}
Let $A\subseteq \NN$, and $k_0\in \NN$. Then $S_A(n,k_0)$ is a C-finite sequence if and only if $A$ is ultimately periodic.
\end{proposition}
\begin{proof}
First we note that 
$S_A(n,1)=1$ iff $n\in A$. 
Therefore, if $A$ is not ultimately periodic, 
$S_A(n,1)$ is 
not C-finite.
On the other hand, assume that $A$ is ultimately periodic. 
Let $\cP$ be the graph property of cliques with vertex size in $A$, i.e., $\cP=\{K_n:n\in A\}$, and define $G_n=K_n$. 
Note that a $\cP$-coloring of $G_n$ with $k_0$ colors is a partition of $V(G_n)$ into exactly $k_0$ non empty 
color classes, with each color class
with size in $A$. 
so $H_{\cP}(G_n,k_0)=S_A(n,k_0)$. We want to apply the FM-theorem. 
As before, the sequence $G_n$ is iteratively constructible.
Hence $H_{\cP}$ is again an extended $\CMSOL$ graph polynomial 
and we can use Theorem \ref{th:FMapp}.
\end{proof}

\begin{proposition}
\label{R4}
Let $A\subseteq \NN$, and $k_0\in \NN$. 
Then  $S_{A,r}(n,k_0)$ is a C-finite sequence if and only if $A$ is ultimately periodic.
\end{proposition}
\begin{proof}
We note that $S_A(n,1)=1$ iff $n\in A$. 
If $A$ is not ultimately periodic, 
then also $S_A(n,1)$ is 
not C-finite. 
Assume that $A$ is ultimately periodic. 
Let $\cP$ be the graph property of edgeless graphs with vertex size in $A$, i.e., $\cP=\{\bar{K_n}:n\in A\}$, 
and define $G_n=K_r\cup \bar{K_n}$. 
Note that a $\cP$-coloring of $G_n$ with $k_0+r$ colors is a partition of $V(G_n)$ 
into exactly $k_0+r$ non empty color classes with sizes in $A$, 
such that every vertex in $V(K_r)\subseteq V(G_n)$ is in a different color class, so $H_{\cP}(G_n,k_0+r)=S_r(n,k_0)$. 
We want to apply the FM-theorem. As before, the sequence $G_n$ is iteratively constructible.
Hence $H_{\cP}$ is again an extended $\CMSOL$ graph polynomial 
and we can use Theorem \ref{th:FMapp}.
\end{proof}

\section{Conclusions and further research}
\label{se:conclu}
In the first part of the paper we introduced MC-finiteness as a worthwhile topic in the study
of integer sequences. We surveyed two methods of establishing MC-finiteness of such sequences.
In Theorem \ref{th:MC}, MC-finiteness follows from the existence of polynomial recurrence relations
with coefficients in $\Z$. In Theorem \ref{th:BS-CMSOL}, MC-finiteness follows from a logical definability
assumption in monadic second-order logic augmented with modular counting quantifiers $\CMSOL$.
We have compared the advantages and disadvantages of the methods, and we have used
the model theoretic method of Theorem \ref{th:BS-CMSOL} to give quick and transparent proofs of MC-finiteness.

In the second part of the paper, we
got similar results for locally restricted set partition functions
like $B_{A,r}$. For this purpose the Specker-Blatter theorem had to be extended 
in order to 
count labeled structures where
a fixed number of special (hard-wired) elements are in a certain configuration. In the case of $B_{A,r}(n)$,
$A$ is a set of natural numbers and $r$ is a natural number. The sequence $B_{A,r}$ counts the number of set partitions
of $[n]$ where the first $r$ elements are in different blocks and
$A$ indicates the possible cardinalities of  the blocks of the partition.
The extension of the Specker-Blatter theorem needed is  given
in Theorem \ref{th:SB*}. A proof of a special case of this theorem is given in Section \ref{se:rproofs}.
The general case can be found in \cite{ar:FischerMakowsky2022}.
Our new results are summarized in Tables \ref{table-2}--\ref{table-5}. 

We did not investigate in depth whether 
MC-finiteness 
of the examples 
in Tables \ref{table-2}--\ref{table-5}
can be established directly or, alternatively, by exhibiting suitable polynomial recurrence schemes in order to apply
Theorem \ref{th:MC}.

\begin{problem}
\label{problem-Bessel}
Are the Bessel numbers $B(n)^B$ MC-finite?
\end{problem}

\begin{problem}
\label{problem-PRS}
Find systems of mutual polynomial recurrences for all the examples in Tables \ref{table-2}--\ref{table-4}.
\end{problem}

Instead of set partition functions we can also count the number of, say, partial orders
where
\begin{enumerate}[(i)]
\item
the set of $r$ special elements are in a particular $\CMSOL$ definable configuration,
such as prescribed comparability and incomparability, and
\item
the set of integers $A$ indicates the possible cardinalities of  certain definable sets, such as antichains or
maximal linearly ordered sets.
\end{enumerate}
Our techniques allow us to show that counting such partial orders over $[n]$ results in MC-finite
sequences.

Finally, some words on the complexity of computing $S_{\phi}(n)$.
The reader not familiar with complexity of computation should consulta
 Arora and Barak \cite{bk:AroraBarak2009} or Papadimitriou \cite{bk:papadimitriou94}.
For a complete picture there is always the Complexity Zoo \cite{complexityzoo}.

Clearly, $S_{\phi}(n)$ is computable by brute force, given $\phi$ and $n$.
In fact, for $\phi \in \FOL$ the problem is in $\sharp\bP$.
For $\phi \in \CMSOL$ it is in $\sharp\bPH$, the analogue of $\sharp\bP$ for problems definable 
in second-order logic, or equivalently,
in the polynomial hierarchy. As noted in Makowsky and Pnueli \cite[Proposition 11]{makowsky1996arity}, 
there are arbitrarily complex problems in $\bPH$ already definable in $\MSOL$.
However, $S^m_{\phi}(n)$ is in $\MOD_m\bP$, respectively in $\MOD_m\bPH$, the corresponding modular counting classes
introduced by Beigel and Gill in \cite{beigel1992counting}. 
It is still open how exactly $\MOD_m\bP$ is related to $\sharp\bP$.
Green et al.\ \cite{green1995power} introduced a counting complexity class $\bMP \subseteq \bP^{\sharp\bP}$ and
showed that for each $m$ the complexity classes $\MOD_m\bP$ are low for $\bMP$. 
{\em A complexity class  $\bB$ is low for a complexity class $\bA$} if $\bA^{\bB} \subseteq \bA$. In other words,
using $\bB$ as an oracle for $\bA$ does not yield more computational power.
The reader further interested in details about complexity classes can consult the Complexity Zoo \cite{complexityzoo}
as a guide to the literature.

Specker 
\cite{specker1990application} 
mentions 
that
$S^m_{\phi}(n) \equiv S_{\phi}(n)$ (mod $m$) can be computed more efficiently, but no details are given.
Only the special case of $Q^m(n)$ is given, where $Q(n)$ is the number of quasi-orders over $[n]$.

\begin{problem}
\label{problem-1}
Given $\phi \in \FOL$ and $m$, find algorithms for computing $S_{\phi}(n)$ and  $S^m_{\phi}(n)$  and
determine upper and lower bounds for them. One may assume that $n$ is encoded in unary.
\end{problem}
\begin{problem}
\label{problem-2}
Same as Problem \ref{problem-1} for $\phi \in \CMSOL$.
\end{problem}
\begin{problem}
Inspired by the remarks above, the following might be a worthwhile project:
\label{problem-3}
Investigate the complexity classes $\sharp\bPH$ and $\MOD_m\bPH$ and their mutual relationships.
\end{problem}

\section{Acknowledgments}
The study of restricted set partition functions arose from questions in
Rakita's PhD thesis \cite{rakita-phd}.
We would like to thank the two anonymous referees for their constructive criticism and their suggestions.
Their comments led to major improvements of the paper.

Y. Filmus was
partially supported by
the European Union's Horizon 2020 research and innovation program under grant agreement No.~802020-ERC-HARMONIC.
E. Fischer was
partially supported by Israel Science Foundation (ISF) grant no.\ 879/22.
V. Rakita was
partially supported by a Technion grant for PhD students.

\begin{thebibliography}{99}

\bibitem{complexityzoo}
Complexity {Z}oo.  Electronic resource, available at 
\url{https://complexityzoo.net/Complexity_Zoo}.

\bibitem{bk:AroraBarak2009}
Sanjeev Arora and Boaz Barak, {\em Computational Complexity: A Modern
  Approach}, Cambridge University Press, 2009.

\bibitem{banderier2017right}
Cyril Banderier, Jean-Luc Baril, and C{\'e}line Moreira~Dos Santos, Right-jumps
  and pattern avoiding permutations, {\em Discrete Math. Theor. Comput. Sci.}
  {\bf 18} (2017), \#12.

\bibitem{banderier2002generating}
Cyril Banderier, Mireille Bousquet-M{\'e}lou, Alain Denise, Philippe Flajolet,
  Daniele Gardy, and Dominique Gouyou-Beauchamps, Generating functions for
  generating trees, {\em Discrete Math.} {\bf 246} (2002), 29--55.

\bibitem{banderier2019period}
Cyril Banderier and Florian Luca, On the period (mod $m$) of
polynomially-recursive sequences:
a case study, {\em J. Integer Sequences} {\bf 22} (2019), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL22/Banderier/band3.html}{Article 19.5.2}.

\bibitem{beigel1992counting}
Richard Beigel and John Gill, Counting classes: Thresholds, parity, mods, and
  fewness, {\em Theoret. Comput. Sci.} {\bf 103} (1992), 3--23.

\bibitem{benyi2019restricted}
Be{\'a}ta B{\'e}nyi, Miguel M{\'e}ndez, Jos{\'e}~L Ram{\'\i}rez, and Tanay
  Wakhare, Restricted $r$-{S}tirling numbers and their combinatorial
  applications, {\em Appl. Math. Comput.} {\bf 348} (2019), 186--205.

\bibitem{benyi2019some}
Be{\'a}ta B{\'e}nyi and Jos{\'e}~L. Ram{\'\i}rez, Some applications of
  $s$-restricted set partitions, {\em Period. Math. Hungar.} {\bf 78} (2019),
  110--127.

\bibitem{berend2010improved}
Daniel Berend and Tamir Tassa, Improved bounds on {B}ell numbers and on moments
  of sums of random variables, {\em Probab. Math. Statist.} {\bf 30} (2010),
  185--205.

\bibitem{blatter1981nombre}
Christian Blatter and Ernst Specker, Le nombre de structures finies d'une
  th\'eorie \'a charact\`ere fini, {\em Sciences Math{\'e}matiques, Fonds
  Nationale de la Recherche Scientifique, Bruxelles}  (1981), 41--44.

\bibitem{pr:BlatterSpecker84}
Christian Blatter and Ernst Specker, Recurrence relations for the number of
  labeled structures on a finite set, In {\em In Logic and Machines: Decision
  Problems and Complexity}, Vol.\ 171 of {\em Lecture Notes in Comput. Sci.},
  Springer, 1984, pp.\  43--61.

\bibitem{broder1984r}
Andrei~Z. Broder, The $r$-{S}tirling numbers, {\em Discrete Math.} {\bf 49}
  (1984), 241--259.

\bibitem{de1981asymptotic}
Nicolaas~Govert de~Bruijn, {\em Asymptotic Methods in Analysis}, Vol.~4,
  Courier Corporation, 1981.

\bibitem{cadilhac2020icalp}
Micha{\"e}l Cadilhac, Filip Mazowiecki, Charles Paperman, Micha\l\ Pilipczuk,
  and G{\'e}raud S{\'e}nizergues, {On polynomial recursive sequences}, In {\em
  47th International Colloquium on Automata, Languages, and Programming (ICALP
  2020)}, Vol.\ 168 of {\em Leibniz International Proceedings in Informatics
  (LIPIcs)}, pp.\  117:1--117:17. Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r
  Informatik, 2020.

\bibitem{cadilhac2021polynomial}
Micha{\"e}l Cadilhac, Filip Mazowiecki, Charles Paperman, Micha{\l} Pilipczuk,
  and G{\'e}raud S{\'e}nizergues, On polynomial recursive sequences,
  Electronically available at \url{https://doi.org/10.1007/s00224-021-10046-9},
  2021.
\newblock To appear in Theory Comput. Syst.

\bibitem{charalambides2018enumerative}
Charalambos~A. Charalambides, {\em Enumerative Combinatorics}, Chapman and
  Hall/CRC, 2018.

\bibitem{comtet2012advanced}
Louis Comtet, {\em Advanced Combinatorics: The Art of Finite and Infinite
  Expansions}, Springer, 2012.

\bibitem{topologies}
Eldar Fischer and Johann~A. Makowsky, Counting the number of finite topologies,
manuscript in preparation, 2023.

\bibitem{everest2003recurrence}
Graham Everest, Alfred~J. van~der Poorten, Igor Shparlinski, and Thomas Ward,
  {\em Recurrence Sequences}, Vol.\ 104 of {\em Mathematical Surveys and
  Monographs}, American Mathematical Society, 2003.

\bibitem{ar:Fischer02}
Eldar Fischer, The {S}pecker-{B}latter theorem does not hold for quaternary
  relations, {\em J. Combin. Theory Ser. A} {\bf 103} (2003), 121--136.

\bibitem{fischer2011application}
Eldar Fischer, Tomer Kotek, and Johann~A. Makowsky, Application of logic to
  combinatorial sequences and their recurrence relations.
\newblock In {\em Model Theoretic Methods in Finite Combinatorics}, Vol.\ 558 of
  {\em Contemporary Mathematics}.  American Mathematical Society,
  2011, pp.\ 1--42.

\bibitem{pr:FischerMakowsky03}
Eldar Fischer and Johann~A. Makowsky, The {S}pecker-{B}latter theorem
  revisited, In {\em COCOON'03}, Vol.\ 2697 of {\em Lecture Notes in Comput.
  Sci.}, Springer, 2003, pp.~90--101.

\bibitem{fischer2008linear}
Eldar Fischer and Johann~A. Makowsky, Linear recurrence relations for graph
  polynomials, In {\em Pillars of Computer Science}, Vol. 4800 of {\em Lecture
  Notes in Comput. Sci.}, Springer, 2008, pp.\  266--279.

\bibitem{ar:FischerMakowsky2022}
Eldar Fischer and Johann~A. Makowsky, Extensions and limits of the
  {S}pecker-{B}latter theorem.  Arxiv preprint
\newblock arXiv:2206.12135, 2022.  Available at 
\url{https://arxiv.org/abs/2206.12135}.

\bibitem{flajolet1990non}
Philippe Flajolet and Ren{\'e} Schott, Non-overlapping partitions, continued
  fractions, {B}essel functions and a divergent series, {\em European J.
  Combin.} {\bf 11} (1990), 421--432.

\bibitem{flajolet2009analytic}
Philippe Flajolet and Robert Sedgewick, {\em Analytic Combinatorics}, Cambridge
  University Press, 2009.

\bibitem{oeis}
OEIS Foundation, The on-line encyclopedia of integer sequences, 2023.  Available
at \url{https://oeis.org/}.

\bibitem{gerhold2004some}
Stefan Gerhold, On some non-holonomic sequences, {\em Electron. J. Combin.}
  {\bf 11} (2004), \#R87.

\bibitem{gessel1990symmetric}
Ira~M. Gessel, Symmetric functions and {P}-recursiveness., {\em J. Comb.
  Theory Ser. A} {\bf 53} (1990), 257--285.

\bibitem{goulden1983hammond}
Ian~P. Goulden, David~M. Jackson, and James~W. Reilly, The {H}ammond series of
  a symmetric function and its application to {P}-recursiveness, {\em SIAM
  J. Alg. Discrete Methods} {\bf 4} (1983), 179--193.

\bibitem{graham1989concrete}
Ronald~L Graham, Donald~E. Knuth, and Oren Patashnik, {\em Concrete
  Mathematics: A Foundation for Computer Science}, Addison-Wesley, 1989.

\bibitem{green1995power}
Frederic Green, Johannes Kobler, Kenneth~W Regan, Thomas Schwentick, and Jacobo
  Tor{\'a}n, The power of the middle bit of a \#{P} function, {\em J. 
  Comput. System Sci.} {\bf 50} (1995), 456--467.

\bibitem{guo2015six}
Bai-Ni Guo and Feng Qi, Six proofs for an identity of the {L}ah numbers, {\em
  Online J. Anal. Comb.} {\bf 10} (2015), 1--5.

\bibitem{kauers2011concrete}
Manuel Kauers and Peter Paule, {\em The Concrete Tetrahedron: Symbolic Sums,
  Recurrence Equations, Generating Functions, Asymptotic Estimates}, Springer,
  2011.

\bibitem{klazar2003bell}
Martin Klazar, Bell numbers, their relatives, and algebraic differential
  equations, {\em J. Combin. Theory Ser. A} {\bf 102} (2003), 63--87.

\bibitem{koshy2008catalan}
Thomas Koshy, {\em Catalan Numbers with Applications}, Oxford University Press,
  2008.

\bibitem{lah1954new}
Ivo Lah, A new kind of numbers and its application in the actuarial
  mathematics, {\em Bol. Inst. Actu\'ar. Port.} {\bf 9} (1954), 7--15.

\bibitem{makowsky2010application}
Johann~A. Makowsky, Application of logic to integer sequences: a survey, In
  {\em Logic, Language, Information and Computation, WoLLIC 2010}, Vol. 6188 of
  {\em Lecture Notes in Comput. Sci.}, Springer, 2010, pp.\ 34--41.

\bibitem{makowsky2014connection}
Johann~A. Makowsky and Tomer Kotek, Connection matrices and the definability of
  graph parameters, {\em Log. Methods Comput. Sci.} {\bf 10} (2014), 1--33.

\bibitem{makowsky1996arity}
Johann~A. Makowsky and Yachin~B. Pnueli, Arity and alternation in second-order
  logic, {\em Ann. Pure Appl. Logic} {\bf 78} (1996), 189--202.

\bibitem{mansour2012combinatorics}
Toufik Mansour, {\em Combinatorics of Set Partitions}, CRC Press, 2012.

\bibitem{mckay1983applications}
Brendan~D. McKay, Applications of a technique for labelled enumeration, {\em
  Congr. Numer.} {\bf 40} (1983), 207--221.

\bibitem{mezo2019combinatorics}
Istv{\'a}n Mez{\H{o}}, {\em Combinatorics and Number Theory of Counting
  Sequences}, CRC Press, 2019.

\bibitem{nyul2015r}
G{\'a}bor Nyul and Gabriella R{\'a}cz, The $r$-{L}ah numbers, {\em Discrete
  Math.} {\bf 338} (2015), 1660--1666.

\bibitem{bk:papadimitriou94}
Christos Papadimitriou, {\em Computational Complexity}, Addison-Wesley, 1994.

\bibitem{pfeiffer2004counting}
G{\"o}tz Pfeiffer, Counting transitive relations, {\em J. Integer Sequences}
{\bf 7} (2004), \href{https://cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html}{Article 04.3.2}.

\bibitem{rakita-phd}
Vsevolod Rakita, {\em On generating and {H}arary polynomials of graphs}, PhD
  thesis, IIT--Israel Institute of Technology, May 2023.

\bibitem{read1970some}
Ronald~C. Read, Some unusual enumeration problems, {\em Ann. New York Acad.
  Sci.} {\bf 175} (1970), 314--326.

\bibitem{read1980number}
Ronald~C. Read and Nicholas~C. Wormald, Number of labeled 4-regular graphs,
  {\em J. Graph Theory} {\bf 4} (1980), 203--212.

\bibitem{reeds1985shift}
James~A. Reeds and Neil J.~A. Sloane, Shift register synthesis (modulo $m$),
  {\em SIAM J. Comput.} {\bf 14} (1985), 505--513.

\bibitem{roman2015introduction}
Steven Roman, {\em An Introduction to Catalan Numbers}, Springer, 2015.

\bibitem{senizergues2007sequences}
G{\'e}raud S{\'e}nizergues, Sequences of level $1, 2, 3,\ldots, k,\ldots$, In
  {\em Computer Science in Russia}, Vol. 4649 of {\em Lecture Notes in Comput.
  Sci.}, Springer, 2007, pp.\  24--32.

\bibitem{shattuck2016generalized}
Mark Shattuck, Generalized $r$-{L}ah numbers, {\em Proc. Indian Acad.
  Sci. (Math. Sci.)} {\bf 126} (2016), 461--478.

\bibitem{specker1990application}
Ernst Specker, Application of logic and combinatorics to enumeration problems.
\newblock In {\em Ernst Specker Selecta}, Springer, 1990,
pp.\  324--350.

\bibitem{bk:Stanley86}
Richard~P. Stanley, {\em Enumerative Combinatorics}, Vol.~1, Wadsworth and
  Brooks, 1986.

\bibitem{wagner1996generalized}
Carl~G. Wagner, Generalized {S}tirling and {L}ah numbers, {\em Discrete Math.}
  {\bf 160} (1996), 199--218.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 05A99; Secondary 05A10, 05A18, 05A99, 03C13, 11Y55.

\noindent \emph{Keywords: }  set partition function,
C-Finiteness, MC, finiteness, supercongruence,
monadic second-order logic, Specker-Blatter theorem.


\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000108},
\seqnum{A000110},
\seqnum{A000453},
\seqnum{A000587},
\seqnum{A000670},
\seqnum{A000798},
\seqnum{A001035},
\seqnum{A001286},
\seqnum{A001861},
\seqnum{A005493},
\seqnum{A005494},
\seqnum{A006789},
\seqnum{A006905},
\seqnum{A086714},
\seqnum{A110040},
\seqnum{A143494},
\seqnum{A143495},
\seqnum{A143496},
\seqnum{A143497},
\seqnum{A232472}, and
\seqnum{A295193}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  February 19 2023;
revised versions received February 20 2023; June 10 2023;
June 11 2023; July 3 2023; July 16 2023; August 2 2023; 
August 3 2023.
Published in {\it Journal of Integer Sequences}, August 4 2023.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}
