MC-Finiteness of Restricted Set Partition Functions

Yuval Filmus, Eldar Fischer, and Johann A. Makowsky Faculty of Computer Science Israel Institute of Technology

3200003 Haifa Israel

 yuvalfi@technion.ac.il
 eldar@cs.technion.ac.il
 janos@cs.technion.ac.il

Vsevolod Rakita Faculty of Mathematics

Israel Institute of Technology

3200003 Haifa Israel

vsevolod@campus.technion.ac.il

Abstract

A sequence s(n) of integers is MC-finite if for every m ∈ ℕ the sequence s(n) mod m is ultimately periodic. We discuss various ways of proving and disproving MCfiniteness. Our examples are mostly taken from set partition functions, but our methods can be applied to many more integer sequences.

1 Introduction

1.1 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) ≡ 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 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 [38] in 2010. Without its name, the concept seemingly appears first in Blatter and Specker [10, 11]. Otherwise it rarely appears in the literature, e.g., under the name of supercongruence in Banderier et al. [3, 5]. The four substantial monographs on integer sequences published after 2000 by Everest et al., Mansour, and Mező [19, 41, 41, 43] do not mention the concept at all,

All the sequences we discuss in this paper appear in the On-Line Encyclopedia of Integer Sequences [27], 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 [12] 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, \underline{A005493} and r = 3, \underline{A005494}. The sequences S_{r}(n, k) appear in OEIS as \underline{A143494}, \underline{A143495}, and \underline{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 MCfiniteness. The first method is a logical method, pioneered by Blatter and Specker [10, 54, 11]. It was further developed by two of the authors of this paper (EF and JAM) [22, 24]. The second method is a combinatorial method to prove MC-finiteness. It was also first suggested by Specker [54] and later, independently, by Sénizergues [52]. Only Cadilhac et al. [15] finally made this second method precise. It is based on the existence of finitely many mutual polynomial recurrence relations over ℤ 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 [18].

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), \underline{A000110}, and the Stirling numbers of the second kind S(n, k_{0}), \underline{A000453}. We also discuss the number of linear quasi-orders (pre-orders) LQ(n), \underline{A000670}, the number of quasi-orders (pre-orders) Q(n), \underline{A000798}, the number of partial orders P (n), \underline{A001035}, and the number of transitive relations T (n), \underline{A006905}, all of them on the set [n]. The numbers LQ(n) are called ordered Bell numbers or 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 [11, 54], the Specker-Blatter theorem.

Typical restricted cases, first introduced by Broder [12] and further studied in [7], 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 ≤ r are all in different blocks and the size of every block is in A ⊆ ℕ. The case of r = 2 appears as \underline{A143494}. The Bell numbers B_{A,r}(n) are defined as ∑_{k} S_{A,r}(n, k). They appear as \underline{A005493} for r = 2 and \underline{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, \underline{A000108}, also have an interpretation as set partitions. Roman [51, Theorem 9.4] and Koshy [36, Chapter 10] 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.

1.2 Outline of the paper

In Section 2 we introduce C-finiteness and its modular variant MC-finiteness. In Section 3 we discuss the methods for proving and disproving C-finiteness and MC-finiteness. In Section 4 we discuss larger classes of polynomial recursive sequences and weaker versions of MC-finiteness, which in the literature appear under the name of supercongruences. We also prove that, in a precise sense, almost all bounded integer sequences are not MC-finite.

In Section 5 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 6 and 7 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 MCfiniteness in these cases. In Section 9 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 10, where we present our conclusions and suggestions for further research.

Sections 4, 7.1, 7.5, and 9 may be skipped in a first reading.

2 C-finite and MC-finite integer sequences

A sequence of integers s(n) is C-finite if there are constants p, q ∈ ℕ and c_{i} ∈ ℤ, 0 ≤ i ≤ p−1 such that for all n ≥ q the linear recurrence relation

s(n + p) = ∑_{i=0}^{p−1} c_{i}s(n + i), n ≥ q

holds for s(n). C-finite sequences are also called in the literature constant-recursive sequences or linear-recursive sequences.

C-finite sequences have limited growth; see, for instance, Everest et al. [19, 34]:

Proposition 1. Let s_{n} be a C-finite sequence of integers. Then there is c ∈ ℕ^{+} such that a_{n} ≤ 2^{cn} for all n ∈ ℕ.

Actually, a lot more can be said. Flajolet et al. [26] 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 1. 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 [23, 21]. The last method will be briefly discussed in Section 8 and further explained in Section 9. It is referred to as method FM.

A sequence of integers s(n) is modular C-finite, abbreviated as MC-finite, if for every m ∈ ℕ there are constants p_{m}, q_{m} ∈ ℕ^{+} such that for every n ≥ q_{m} there is a linear recurrence relation

s(n + p_{m}) ≡ ∑_{i=0}^{p_{m}−1} c_{i,m}s(n + i) (mod m)

with constant coefficients c_{i,m} ∈ ℤ. 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) ≡ s(n) (mod m).

Proposition 2. The sequence s(n) is MC-finite iff s^{m}(n) is ultimately periodic for every m.

Proof. MC-finiteness implies periodicity. The converse is proved by Reeds and Sloane in [50].

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 4 below shows that here are uncountably many MC-finite sequences with integer coefficients, but only countably many C-finite sequences with integer coefficients.

Example 3.

(i) The Fibonacci sequence is C-finite. (ii) If s(n) is C-finite then it has at most simple exponential growth, by Proposition 1. (iii) The Bell numbers B(n) are not C-finite, but are MC-finite. (iv) Let f(n) be any integer sequence. The sequence s_{1}(n) = 2 · f(n) is ultimately periodic

modulo 2, but not necessarily MC-finite.

(v) Let g(n) be any integer sequence. The sequence s_{2}(n) = n! · g(n) is MC-finite. (vi) The sequence s_{3}(n) = \frac{1}{2} \binom{2n}{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. [31, Exercise 5.61], or in Specker [54].

(vii) The Catalan numbers C(n) = \frac{1}{n+1} \binom{2n}{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 ∈ ℕ. A good reference is Koshy [36, Chapter 13].

(viii) Let p be a prime and f(n) be monotone increasing. Let s(n) be the sequence

s(n) = \begin{cases}p^{f(n)}, & if n ≠ p^{f(n)}; \\ p^{f(n)} + 1, & otherwise. \end{cases}

Then s(n) is monotone increasing but not ultimately periodic modulo p, hence not MC-finite.

Proposition 4.

(i) There are uncountably many monotone increasing sequences that are MC-finite, and uncountably many that are not MC-finite.

(ii) Almost all integer sequences are not MC-finite. Proof. Claim (i) follows from Examples 3 (v) and (viii). Claim (ii) is shown in Proposition 15 in Section 4.

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 46 shows that the restricted Stirling numbers of the second kind listed therein are all C-finite. We show this via a general method, Theorem 44, without exhibiting a generating function like in the classical case for S(n, k).

3 How to prove and disprove MC-finiteness

3.1 Polynomial recurrence relations

In his paper, Specker [54, p. 144] noted the following:

In many known cases, [MC-finiteness] is a consequence of polynomial recurrence relations

f(n) = ∑_{i=1}^{d} P_{i}(n)f(n − i)

where P_{i} are polynomials in ℤ[x].

For f(n) = n! this is obvious. In general this needs some elaboration.

Definition 5.

(i) An integer sequence s(n) is holonomic over ℤ if there exist polynomials P_{i} ∈ ℤ[x] with P_{1}, P_{k} ≠ 0 such that

s(n) = ∑_{i=1}^{k} P_{i}(n)s(n − i).

(ii) An integer sequence s(n) is polynomially recursive (PRS) over ℤ if there exist k integer sequences s_{i}(n), 1 ≤ i ≤ k with s(n) = s_{1}(n) and polynomials P_{i} ∈ ℤ[x_{1}, …, x_{k}] such that the mutual recursion

s_{i}(n + 1) = P_{i}(s_{1}(n), …, s_{k}(n)), i = 1, …, k

holds.

(iii) An integer sequence s(n) is PRS over ℤ and n if the polynomials also involve n as an additional variable. In other words P_{i} ∈ ℤ[x_{1}, …, x_{k}, y] and

s_{i}(n + 1) = P_{i}(s_{1}(n), …, s_{k}(n), n), i = 1, …, k.

Actually, (ii) and (iii) are equivalent.

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

In fact, the following is true:

Theorem 6. If s(n) is an integer sequence that is polynomially recursive over ℤ and n then s(n) is MC-finite. In particular, this is true also for integer sequences s(n) that are holonomic over ℤ.

The proof is given in Section 4. There we also briefly discuss weaker properties than MC-finiteness, where the modular recurrence holds only for almost all m ∈ ℕ^{+}.

Remark 7.

(i) In general, holonomic sequences are defined over fields 𝔽 rather than the ring ℤ. A good reference is the monograph by Kauers and Paule [34, Chapter 7]. A theorem related to Theorem 6 for holonomic sequences can be found in two papers by Banderier et al. [3, Theorem 7] and [5].

(ii) Cadilhac et al. [14, 15] define polynomially recursive sequences for rational numbers rather than integers, and the polynomials are in ℚ[x_{1}, …, x_{k}].

The following examples, except (v), are from [15].

Example 8.

(i) The sequences a(n) = n! with a(n) = n · a(n − 1) and a(0) = 1 is holonomic over ℤ. It is obviously MC-finite.

(ii) 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 [28] 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].

(iii) The Catalan numbers C_{n} are holonomic: (n + 2)C_{n+1} = (4n + 2)C_{n}. They are not holonomic over ℤ, since they are not MC-finite. Furthermore, they are not polynomially recursive even if we allow rational numbers.

(iv) The sequence n^{n} is not polynomially recursive, but it is MC-finite by the Specker-Blatter theorem below.

(v) We show in Section 4 that the sequence \underline{A086714} given by

a(0) = 4, a(n + 1) = \binom{a(n)}{2}

is not MC-finite but is periodic modulo every odd number.

MC-finite sequences are closed under various arithmetic operations.

Proposition 9. Let a(n), b(n) be MC-finite sequences and c ∈ ℤ.

(i) The sequences c · a(n), a(n) + b(n), a(n) · b(n) are MC-finite.

(ii) If additionally b(n) ∈ ℕ^{+} and tends to infinity, then a(n)^{b(n)} is also MC-finite.

(iii) Let A ⊆ ℕ^{+} 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, & if n ∈ A; \\ n! + 1, & otherwise. \end{cases}

Then b(n) is MC-finite and oscillates. However a(n)^{b(n)} is not MC-finite.

3.2 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 [10, 11, 54]. 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 7.2. In its simplest form, the Specker-Blatter theorem can be stated as follows:

Theorem 10 (Specker-Blatter theorem). Let S_{ϕ}(n) be the number of binary relations R on a set [n] that satisfy a given formula ϕ ∈ CMSOL. The sequence S_{ϕ}(n) is MC-finite or, equivalently, S_{ϕ}^{m}(n) is ultimately periodic for every m.

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 [22]. These combined methods are abbreviated in the sequel by SB.

3.3 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 6 and 10 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.

Example 11. We note that the two meta-theorems cannot always be applied to the same integer sequences.

(i) 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. [15]. However, MC-finiteness can also be established directly without much effort.

(ii) There are polynomially recursive sequences over ℤ (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 10 cannot be applied. Again, MC-finiteness can also be established directly without much effort.

(iii) 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 [39]. Hence Theorem 10 cannot be applied to the sequence \underline{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 10 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 [42] and the references cited therein. For r = 2, 3 this is \underline{A110040}. Recurrences for r = 0, 1, 2 are found easily. For r = 3, 4 explicit recurrences were published by Read and Wormald [48, 49], and for r = 5 by Goulden et al. [30]. The recurrence for r = 5 is linear but very long. Gessel [29] showed that RG(n, r) is holonomic (P-recursive) for every k ∈ ℕ^{+}. We have not checked whether RG(n, r) is holonomic over ℤ. Read showed that RG(n, 4) is polynomially recursive [49], but the equations given there do not show that RG(n, 4) is polynomially recursive over ℤ. It seems that Theorem 10 is the most suitable method to show that for each r the sequence RG(n, r) is MC-finite.

We will use, like in Fischer and Makowsky [21, 24], the logic CMSOL, where we also allow hard-wired constants. Dealing with hard-wired constants is briefly described in Section 7.5.

Clearly, S_{ϕ}(n) is computable by brute force, given ϕ and n. Specker [54], mentions that S_{ϕ}^{m}(n) ≡ S_{ϕ}(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].

4 More on MC-finiteness

4.1 Polynomial recursive sequences

Cadilhac [15] defines a 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), …, a_{d}(0) and the recurrence

a_{i}(n + 1) = P_{i}(a_{1}(n), …, a_{d}(n)),

where P_{i} is a polynomial with rational coefficients. We will only consider recurrences for which a_{i}(n) ∈ ℕ for all i ∈ [d] and n ≥ 0.

Theorem 12 ([15]). Let m be a natural number that is relatively prime to all denominators of coefficients of the defining polynomials P_{1}, …, P_{d}. Then the sequences a_{i}(n) modulo m are eventually periodic.

Proof. Let the polynomials P_{1}, …, P_{d} be given by

P_{k}(x_{1}, …, x_{d}) = ∑_{e∈ℕ^{d}} \frac{s_{ke}}{t_{ke}} ∏_{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 ℘: ℤ → ℤ_{m} be the (mod m) mapping. We extend the definition of ℘ to the polynomials P_{1}, …, P_{d} as follows:

℘(P_{k})(y_{1}, …, y_{d}) = ∑_{e∈ℕ^{d}} \frac{℘(s_{ke})}{℘(t_{ke})} ∏_{i=1}^{d} y_{i}^{e_{i}},

which is well-defined since (t_{ke}, m) = 1. Consequently, ℘(t_{ke}) is invertible in the ring ℤ_{m}. Elementary number theory shows that

℘(P_{k}(x_{1}, …, x_{d})) = ℘(P_{k})(℘(x_{1}), …, ℘(x_{d})),

and so

℘(a_{k}(n + 1)) = ℘(P_{k}(a_{1}(n), …, a_{d}(n))) = ℘(P_{k})(℘(a_{1}(n)), …, ℘(a_{d}(n))).

Now consider the mapping Q: ℤ_{m}^{d} → ℤ_{m}^{d} given by

Q(y_{1}, …, y_{d}) = (℘(P_{1})(y_{1}, …, y_{d}), …, ℘(P_{d})(y_{1}, …, y_{d})).

The foregoing shows that

(℘(a_{1}(n + 1)), …, ℘(a_{d}(n + 1))) = Q(℘(a_{1}(n)), …, ℘(a_{d}(n))).

Using the notation b(n) = (℘(a_{1}(n)), …, ℘(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) ∈ ℤ_{m}^{d}, by the pigeonhole principle, the list b(0), …, 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 ∈ ℕ. Consequently, b(n) is eventually periodic. We conclude that its components, ℘(a_{k}(n)) ≡ a_{k}(n) (mod m), are eventually periodic as well.

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 \underline{A086714}:

a(n + 1) = \binom{a(n)}{2}, a(0) = 4.

and put â(n) ≡ a(n) (mod 2).

Theorem 13. The sequence â(n) is not ultimately periodic.

The same result holds (with the same proof) for any a(0) ≥ 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) → ∞.

4.2 Proof of Theorem 13

Let β(n) ≡ a(n) (mod 2). It is not hard to check that the sequence β(n), …, β(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 β(n), …, β(n + k − 1).

Lemma 14. Let a_{r}, β_{r} be defined as above, except with the initial condition a_{r}(0) = r. For all k ≥ 1, the function

Φ_{k}(r) = β_{r}(0), …, β_{r}(k − 1)

is a bijection between {0, …, 2^{k} − 1} and (0, 1)^{k}.

For example, if k = 3, we get the following bijection:

Φ_{3}(0) = 000  Φ_{3}(1) = 100  Φ_{3}(2) = 010  Φ_{3}(3) = 111
Φ_{3}(4) = 001  Φ_{3}(5) = 101  Φ_{3}(6) = 011  Φ_{3}(7) = 110

Proof. The proof is by induction on k. The result is clear when k = 1, so suppose k > 1.

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

Indeed, suppose that

\binom{a}{2} ≡ \binom{b}{2} (mod 2^{k−1})

for a, b ∈ {0, …, 2^{k} − 1}. Then a(a − 1) ≡ b(b − 1) (mod 2^{k}), and so

2^{k} | 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} | a − b. Since a, b ∈ {0, …, 2^{k} − 1}, in this case a = b.

If a, b have different parities then a − b is odd and so 2^{k} | a + b − 1, and so b ≡ 1 − a (mod 2^{k}) is uniquely defined, and has a parity different from a.

We can now prove Theorem 13. First we notice that \binom{a}{2} > a for a ≥ 4, and so a(n) → ∞. Now suppose that the sequence β is ultimately periodic, say with period β(N), …, β(N + ℓ − 1).

Lemma 14 implies that for every k ≥ 1, the sequence a(n) (mod 2^{k}) has period

a(N) (mod 2^{k}), …, a(N + ℓ − 1) (mod 2^{k}),

and in particular,

a(N) ≡ a(N + ℓ) (mod 2^{k}).

We reach a contradiction by choosing k such that 2^{k} > a(N + ℓ).

4.3 Normal sequences

Let s(n) be an integer sequence, b ∈ ℕ^{+}, and s^{b}(n) ≡ s(n) (mod b). The sequence s^{b}(n) is normal if, when it is partitioned into substrings of length ℓ ≥ 1, then each of the b^{ℓ} possible strings of [b]^{ℓ} appear in s^{b}(n) with equal limiting frequency. It is absolutely normal if it is normal for every b. The sequence s^{b}(n) ≡ s(n) (mod b) can be viewed as a real number r_{b} written in base b. A classical theorem from 1922 by Émile Borel says that almost all reals are absolutely normal. This is discussed in Everest et al. [19]. The theorem below shows that MC-finite integer sequences are very rare.

Let PR_{b} be the set of integer sequences s^{b}(n) with s^{b}(n) ≡ s(n) (mod b) for some integer sequence s(n). PR_{b} is the projection of all integer sequences to sequences over ℤ_{b}. We think of PR_{b} as a set of reals with the usual topology and its Lebesgue measure. Let UP_{b} ⊆ PR_{b} be the set of sequences s^{b}(n) ∈ PR_{b} that are ultimately periodic.

Proposition 15.

(i) Almost all reals are absolutely normal.

(ii) s(n) is MC-finite iff for every b ∈ ℕ^{+} the sequence s^{b}(n) is ultimately periodic

(iii) If s^{b}(n) is normal for some b, then s(n) is not MC-finite.

(iv) UP_{b} ⊆ PR_{b} has measure 0.

Proving that a specific sequence is normal is usually difficult. Here is a challenge:

Conjecture 16. The binary sequence β(n) ≡ a(n) (mod 2) from Theorem 13 is normal with b = 2.

5 Immediate consequences of the Specker-Blatter theorem

5.1 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 FOLformula. Therefore, we immediately get from Theorem 10 that:

Theorem 17. The Bell numbers B(n) are MC-finite.

The Bell numbers do satisfy some known congruences. For m = p a prime, they satisfy the Touchard congruence

B(p + n) ≡ B(n) + B(n + 1) (mod 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 [13, 9].

Proposition 18. For every n ∈ ℕ^{+}

(\frac{n}{e ln n})^{n} ≤ B(n).

Furthermore, for every ϵ > 0 there is n_{0}(ϵ) such that for all n ≥ n_{0}(ϵ)

B(n) ≤ (\frac{n}{e^{1−ϵ} ln n})^{n} .

Flajolet et al. [26, Proposition VIII.3] 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 [35]. There, and in Banderier et al. [4], some variations of Bell numbers are also studied:

Definition 19.

(i) B(n)_{k,m} counts the number of partitions of [n] that have k blocks modulo m.

(ii) B(n)^{±} = B(n)_{0,2} − B(n)_{1,2} are the Uppuluri-Carpenter numbers \underline{A000587}.

(iii) B(n)^{bc} counts the number of bicolored partitions of [n], that is, the partitions of [n] where the blocks are colored with two non-interchangeable colors C_{1}, C_{2}, \underline{A001861}.

Theorem 20. The sequences B(n), B(n)_{k,m}, B(n)^{±}, B(n)^{bc} are not holonomic, hence not C-finite, but they are MC-finite.

Proof. In Klazar [35], and in Banderier et al. [4] is shown that they are not holonomic. To see that they are MC-finite, we apply Theorem 10.

(i) B(n)_{k,m} is definable in CMSOL. We say that there is a set X ⊆ [n] that intersects every block in exactly one element, and the size of the set X is k (mod m).

(ii) B(n)^{±} is the difference of two MC-finite sequences, hence MC-finite.

(iii) 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} ⊆ [n] partition [n], and each of them is closed under E.

5.2 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 [46]. They are all definable in FOL, and we have

Proposition 21. B(n) = E(n) ≤ LQ(n) ≤ P (n) ≤ Q(n) ≤ T (n).

Proof. E(n) ≤ LQ(n): We can turn an equivalence relation into a linear quasi-order by linearly ordering the equivalence classes.

LQ(n) ≤ 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) ≤ Q(n): Each partial order is also a quasi-order.

Q(n) ≤ T (n): Each quasi-order is transitive.

Hence we get using the Specker-Blatter theorem and Proposition 21:

Theorem 22. The sequences B(n) = E(n), LQ(n), P (n), Q(n) and T (n) are MC-finite but not C-finite.

5.3 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) = ∑_{k} S(n, k).

Theorem 23. For fixed k = k_{0} the sequence S(n, k_{0}) is C-finite, and hence MC-finite.

This can be seen by observing that S(n, k_{0}) has the following rational generating function:

∑_{n=0}^{∞} S(n, k_{0})x^{n} = \frac{x^{k_{0}}}{(1 − x)(1 − 2x) ⋯ (1 − k_{0}x)}.

Details can be found in Graham et al. [31, 7.47].

5.4 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), \underline{A001286}, introduced by I. Lah [37] in the context of actuarial science. Good references for Lah numbers are the monographs by Graham et al. [31], and by Charalambides [16]. The Lah numbers are also coefficients expressing rising factorials x^{(n)} in terms of falling factorials x_{(n)}.

Proposition 24.

x^{(n)} = ∑_{k=1} Lah(n, k)x_{(k)} and x_{(n)} = ∑_{k=1}(−1)^{n−k}Lah(n, k)x^{(k)}.

Guo [33] gives six proofs of Proposition 24. Furthermore we define Lah(n) = ∑_{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 equi-comparable if both u ≤ v and v ≤ u. This is again definable in first order logic FOL.

There are explicit formulas:

Proposition 25.

Lah(n, k) = \frac{n!}{k!} · \binom{n − 1}{k − 1} = ∑_{j=0}^{n} s(n, j)S(j, k)  (1)

and

Lah(n) = ∑_{k} Lah(n, k) = n! ∑_{k} \frac{1}{k!} · \binom{n − 1}{k − 1}.  (2)

where s(n, j) are the Stirling numbers of the first kind.

For details the reader may consult Comtet [17].

There is also a recurrence relation:

Lah(n + 1, k) = Lah(n, k − 1) + (n + k)Lah(n, k).  (3)

But again this is not enough to establish C-finiteness or MC-finiteness, since it is a recurrence involving both n and k.

Theorem 26. Both Lah(n) and Lah(n, k_{0}) are MC-finite but not C-finite.

Proof. It follows directly from Equation (1), and also from Equation (3), that for k = k_{0} fixed the sequence Lah(n, k_{0}) is not C-finite. MC-finiteness again follows using Theorem 10.

Note however that the recurrence relation given in Equation (3) does not have constant coefficients.

5.5 Summary so far

Table 1 summarizes the results that are direct consequences of the growth arguments or non-holonomicity (NH), and the Specker-Blatter theorem 10 (SB).

Sequence  C-  Proof  Theorem MC- Proof Theorem
finite  finite
S(n) = B(n)  no  Growth 22  yes  SB  17
S(n, k_{o})  yes  gen.fun 23  yes  gen.fun 23
B(n)^{±}  no  NH  20  yes  SB  20
B(n)^{bc}  no  NH  20  yes  SB  20
LQ(n)  no  Growth 22  yes  SB  22
Q(n)  no  Growth 22  yes  SB  22
P (n)  no  Growth 22  yes  SB  22
T (n)  no  Growth 22  yes  SB  22
Lah(n) = LQ(n) no  Growth 26  yes  SB  26
Lah(n, k_{0})  no  Growth 26  yes  SB  26

Table 1: Direct consequences of the Specker-Blatter theorem.

6 Restricted set partitions

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 positional restrictions, which impose conditions on the positions of the elements of [n], where [n] is equipped with its natural order. The second are size restrictions, which impose conditions on the size of the blocks or their number.

6.1 Global positional restrictions

Definition 27. Let A and B be two blocks of a partition of [n].

(i) A and B are crossing if there are elements a_{1}, a_{2} ∈ A and b_{1}, b_{2} ∈ B such that a_{1} < b_{1} < a_{2} < b_{2} or b_{1} < a_{1} < b_{2} < a_{2}.

(ii) Let min A, max A, min B, max B the smallest and the largest elements in A and B. A and B are overlapping if min A < min B < max A < max B or min B < min A < max B < max A.

(iii) If A and B are overlapping they are also crossing, but not conversely.

(iv) As shown in Roman [51], the number B(n)^{nc} of non-crossing set partitions over [n] is one of the interpretations of the Catalan numbers,

(v) The Bessel number B(n)^{B}, \underline{A006789}, is the number of non-overlapping set partitions over [n]. It was introduced by Flajolet and Schott [25].

The Catalan numbers C(n) are not holonomic and not MC-finite. Banderier et al. [4] 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 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 [12], various recent papers look at local positional restrictions one can impose on Stirling and Lah numbers, for instance the publications [56, 44, 8, 7]. They are local because they only put restrictions on the positions of a fixed number of elements of [n] with their natural order.

6.2 Local positional and size restrictions

Recall that we use [n] to denote the set {1, 2, …, 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, …, r are called 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 hard-wired constants, i.e., constant symbols a_{i}, 1 ≤ i ≤ r with a fixed interpretation by elements of [n + r].

We define S_{r}(n) = B_{r}(n) by

S_{r}(n) = ∑_{k} S_{r}(n, k).

Nyul [44] and Shattuck [53] define the sequences Lah_{r}(n, k), \underline{A143497}, and Lah_{r}(n) analogously with the condition that a_{1} < a_{2} < ⋯ < a_{r} are in different blocks.

Let A ⊆ ℕ. 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 \underline{A232472}.

A set A ⊆ ℕ is (ultimately) periodic if there exist p, n_{0} ∈ ℕ^{+} such that for all n ∈ ℕ (n ≥ n_{0}) we have n ∈ A iff n + p ∈ A. In other words, the characteristic function χ_{A}(n) of A is ultimately periodic in the usual sense, χ_{A}(n) = χ_{A}(n + p) (n ≥ n_{0}).

6.3 Main results for restricted set partitions

Our results for restricted set partitions are summarized in Tables 2, 3, 4, and 5 below. The abbreviation FM, SB* and NH refer respectively to the proof method of Fischer and Makowsky [23, 21], 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 4 also hold for LQ_{A,r}, the r-Fubini numbers, and other similarly defined sequences.

Sequence  C-  Proof  Theorem MC- Proof Theorem
finite  finite
S_{A}(n) = B_{A}(n)  no  Growth 33  yes  SB* 30
S_{A}(n, k_{0})  yes  FM  46  yes  FM  46
Lah_{A}(n) = LQ_{A}(n) no  Growth 35  yes  SB* 30
Lah_{A}(n, k_{0})  no  Growth 35  yes  SB* 30

Table 2: With ultimately periodic A only.

Sequence  C-  Proof  Theorem MC- Proof Theorem
finite  finite
S_{r}(n) = B_{r}(n) no  Growth 33  yes  SB* 37
S_{r}(n, k_{0})  yes  FM  46  yes  FM  46
Lah_{r}(n, k_{0})  no  Growth 35  yes  SB* 37

Table 3: With hard-wired constants only.

Sequence  C-  Proof  Theorem MC- Proof Theorem
finite  finite
S_{A,r}(n) = B_{A,r}(n) no  Growth 31  yes  SB* 37
S_{A,r}(n, k_{0})  yes  FM  46  yes  FM  46
Lah_{A,r}(n, k_{0})  no  Growth 31  yes  SB* 37

Table 4: With ultimately periodic A and hard-wired constants.

Sequence  C-  Proof Theorem MC- Proof Theorem
finite  finite
B(n)^{B}  no  NH  [4]  ???  ???  —
B(n)^{nc} = C(n) no  NH  [51]  no  [51]  [4]

Table 5: With global positional restrictions.

7 Proofs for the restricted cases

For the analysis of MC-finiteness in the restricted cases we need some additional tools.

7.1 An explicit computation of S_{A}(n, k)

Let A ⊆ ℕ. 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 = ℕ^{+} 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 [16, Theorem 8.6]. Stanley proves it in very different notation in [55, Chapter 1, Exercise 45].

We introduce some suitable notation. Let A ⊆ ℕ. 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}, …, L_{k}) of elements of A ordered in non-decreasing order, with ∑_{i=1}^{k} = n, i.e.,

V (A, k) = {(l_{1}, l_{2}, …, l_{k}) ∈ A^{k} : 0 < l_{1} ≤ l_{2} ≤ ⋯ ≤ l_{k}, ∑_{i=1}^{k} l_{i} = n}.

For (l_{1}, l_{2}, …, l_{k}) ∈ V (A, k) define g(m; l_{1}, l_{2}, …, l_{k}) to be the number of times m appears in the k-tuple (l_{1}, l_{2}, …, l_{k}), and

f(l_{1}, l_{2}, …, l_{k}) = ∏_{m∈(l_{1},l_{2},...,l_{k})} g(m; l_{1}, l_{2}, …, l_{k})!.

Next we define the sequence (c_{i}) inductively as follows:

c_{1} = n and c_{i+1} = c_{i} − l_{i}.

Hence c_{i} = n − ∑_{j=1}^{i−1} l_{j}.

Theorem 28. Let A ⊆ ℕ. Then

S_{A}(n, k) = ∑_{(l_{1},l_{2},...,l_{k})∈V (A,k)} \frac{1}{f(l_{1}, l_{2}, …, l_{k})} ∏_{i=1}^{k} \binom{c_{i}}{l_{i}}.

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}, …, l_{k}) ∈ 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}, …, l_{k}) to account for double counting of tuples with equal entries.

7.2 Ultimate periodicity of A

Recall that a formula with a modular counting quantifier C_{b,m}xϕ(x) is true in a structure 𝔅 if the cardinality of the set of elements in 𝔅 that satisfy ϕ(x), satisfies

|{a ∈ B : ϕ(a)}| ≡ b (mod m).

CMSOL is the logic obtained from MSOL by extending it with all the modular counting quantifiers C_{b,m}. In [22] the Specker-Blatter theorem was extended to hold for CMSOL, as already stated in Theorem 10. CMSOL is also needed to prove the following lemma:

Lemma 29. Let A be ultimately periodic and ψ(x) be a formula of CMSOL. Then there is a sentence ψ_{A} ∈ CMSOL such that in every finite structure 𝔅 we have

𝔅 ⊧ ψ_{A} iff |{b ∈ B : ψ(b)}| ∈ A.

Proof. If

A = A_{a,m} = {n ∈ ℕ : n ≡ a (mod m)}

the formula ψ_{A} is the sentence C_{a,m}xψ(x).

Next we observe that if A is ultimately periodic, then there are finitely many a_{1}, …, a_{k} and q such that A = ⋃_{i=0}^{k} A_{i} with A_{0} ⊆ [q] and

A_{i} = {n > q : n ≡ a_{i} (mod m)}.

We proceed in steps:

(i) ∃^{≥k}xψ(x) := ∃x_{1}, …, x_{k} ⋀_{i=1}^{k} ψ(x_{i}) ∧ ⋀_{1≤i<j≤k}(x_{i} ≠ x_{j}) says that there are at least k elements that satisfy ψ(x).

(ii) ∃^{=k}xψ(x) := ∃^{≥k}xψ(x) ∧ ¬∃^{≥k+1}xψ(x) says that there are exactly k such elements.

(iii) ψ_{A_{0}} := (∃^{<q}xψ(x) → ⋁_{j∈A_{0}} ∃^{=j}xψ(x)) says that if the number of elements satisfying ψ(x) is at most q then the number of such elements has exactly one of the cardinalities in A_{0}.

(iv) ψ_{A_{i}} := ∃^{≥q+1}xψ(x) ∧ C_{a,m}xψ(x) says that, if the number of elements satisfying ψ(x) is bigger or equal than q, then the number such elements equals a_{i} (mod m).

(v) ψ_{A}(x) := ⋁_{i=0}^{k} ψ_{A_{i}}(x) is the required formula.

Theorem 10 together with Lemma 29 immediately gives the following result:

Theorem 30. 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.

7.3 Growth arguments

We first discuss growth arguments for B_{A}(n) = S_{A}(n), Lah_{A}(n), and Lah_{A}(n, k_{0}).

Theorem 31. Let A ⊆ ℕ 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.

Proof. First we prove it for B_{A}(n) and

A = A_{m} = {n ∈ ℕ : n ≡ 0 (mod m)}.

Let P_{1}, …, 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) ≥ P (n) ≥ (\frac{n}{e ln n})^{n}

or, equivalently,

P_{A}(n) ≥ P (⌊n/m⌋) ≥ (⌊n/m⌋e ln⌊n/m⌋)^{⌊n/m⌋} ,

which still grows superexponentially.

Next we assume that

A = A_{k,a,m} = {n ∈ ℕ : n ≡ a (mod m) for n ≥ 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 ∈ ℕ^{+} such that A_{k,a,m} ⊆ A.

For Lah_{A}(n) and Lah_{A}(n, k_{0}) we proceed similarly using Proposition 25.

Next we discuss growth for Lah(n, k_{0}), Lah(n) = ∑_{k} Lah(n, k) and Lah_{r}(n, k_{0}). We have seen in Proposition 18 that

(\frac{n}{e ln n})^{n} ≤ B(n) ≤ (\frac{n}{e^{1−o(1)} ln n})^{n} .

We now prove a lemma.

Lemma 32. B_{r}(n) ≥ B(n).

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.

From Propositions 1, 21, and 32, we get the following result:

Theorem 33. The sequences B(n) and B_{r}(n) are not C-finite.

Lemma 34. For k_{0}, r fixed, the Lah number Lah(n, k_{0}) satisfies the following:

(i) Lah(n, k_{0}) = \binom{n−1}{k_{0}−1} \frac{n!}{k_{0}!},

(ii) Lah(n) ≥ Lah(n, k_{0}), and

(iii) Lah_{r}(n, k_{0}) ≥ Lah(n, k_{0}).

Proof. (i) is from [37]. (ii) follows from (i), and (iii) is proved like Lemma 32.

This immediately gives

Theorem 35. Let k_{0} be fixed. The sequences Lah(n, k_{0}), Lah_{r}(n, k_{0}), and Lah(n) = ∑_{k} Lah(n, k) are not C-finite.

7.4 Hard-wired constants

Recall that a constant is 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 [20]. Fischer and Makowsky announced recently that it is also false for one ternary relation [24].

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 ≠ 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 ∈ [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 7.5 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 [24] proved the most general version.

Theorem 36. Let τ_{r} be a vocabulary with finitely many binary and unary relation symbols, and r hard-wired constants. Let ϕ be a formula of CMSOL(τ_{r}). Then S_{ϕ}(n) is MC-finite.

Corollary 37. 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.

7.5 Eliminating hard-wired constants

Let 𝔖_{r}(n) = ([r + n], a_{1}, …, a_{r}, E) be the structures over [r + n] where E is an equivalence relation and the r elements a_{1}, …, a_{r} are in different equivalence classes. The number S_{r}(n) counts the number of such structures on [r + n].

Let 𝔈_{r}(n) be a structure over [n] that consists of the following:

(i) The relation E(x, y) is an equivalence relation over [n]; (ii) There are r unary relations U_{1}, …, U_{r} on [n]; (iii) The sets U_{i}(x) are disjoint; (iv) Each U_{i}(x) is either empty or consists of exactly one equivalence class of E; Let E_{r}(n) be the number of such structures over [n]. Lemma 38. For every r, n ∈ ℕ^{+} there is a bijection f between the structures 𝔈_{r}(n) over [n] and the structures 𝔖_{r}(n) over [r + n], hence we have E_{r}(n) = S_{r}(n). Proof. Given a structure 𝔖_{r}(n) we define f(𝔖_{r}(n)) as follows:

(i) The universe of f(𝔖_{r}(n)) is {r + 1, …, r + n}. (ii) If for i ≤ r the set {i} is a singleton equivalence class, we put U_{i} = ∅. If there is an

equivalence class E_{i} that strictly contains {i}, we define U_{i} = E′_{i} = E_{i} \ {i}. (iii) E′ is the equivalence relation induced by E over {r + 1, …, r + n}. Conversely, given a structure E_{r}(n) = ([n], E, U_{1}, …, U_{r}) we define g(E_{r}(n)) as follows:

(i) The universe of g(E_{r}(n)) is [n+r] and the equivalence relation E′ is defined by defining its equivalence classes.

(ii) If U_{i} is empty for some i ∈ [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} ∪ {i}. (iii) If C is an equivalence class of E such that U_{i} ≠ C for all i ∈ [r], then C is an equivalence

class for E′. It is now easy to check that f, g are bijections and inverses of each other. Remark 39.

(i) 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.

(ii) 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| ∈ A. This means that in a structure 𝔈_{A,r}(n) the equivalence classes C satisfy |C| ∈ A, if they do not contain a U_{i}. Otherwise they satisfy |C| ∈ A′ where A′ = {a − 1 : a ∈ A}. If A is ultimately periodic, so is A′ and both are definable in CMSOL.

(iii) 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.

8 Proving C-finiteness

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

8.1 Counting partitions with a fixed number of blocks

Let G = (V (G), E(G)) be a graph, and k_{0} ∈ ℕ. We look at partitions P_{1}, …, P_{k_{0}} ⊆ V (G) of V (G) that can be described in the logic CMSOL. The following are three typical examples:

Example 40.

(i) The underlying sets of G[P_{i}(G)] form a partition of V (G) without further restrictions.

(ii) For each i ≤ k_{0} the induced graph G[P_{i}(G)] is edgeless (proper coloring).

(iii) Let C be a graph property. For each i ≤ k_{0} the set G[P_{i}(G)] is in C (C-coloring).

We look at the counting function

f_{ϕ}(G) = |{P_{1}, …, P_{k_{0}} ⊆ V (G) : ϕ(P_{1}, …, P_{k_{0}})}|,

defined using an CMSOL-formula ϕ.

Let A ⊆ ℕ be an ultimately periodic set. We also look at the restricted counting function

f_{ϕ,A}(G) = |{P_{1}, …, P_{k_{0}} : ϕ(P_{1}, …, P_{k_{0}}) and |P_{i}| ∈ A}|.

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

8.2 Iteratively constructed graphs

Definition 41.

(i) A k-colored graph is a graph G together with subsets V_{i} ⊆ V (G), i ∈ [k] such that V_{i} ∩ V_{j} = ∅ for i ≠ j.

(ii) A basic operation on k-colored graphs is one of the following:

• Add_{i}: add a new vertex of color i to G.

• Recolor_{i,j}: recolor all vertices with color i to color j in G.

• Uncolor_{i}: remove the color of all vertices with color i. Uncolored vertices cannot be recolored again.

• AddEdges_{i,j}: add an edge between every vertex with color i and every vertex with color j in G.

• DeleteEdges_{i,j}: delete all edges between vertices with color i and vertices with color j from G.

(iii) A unary operation F on graphs is elementary if F is a finite composition of basic operations on k-colored graphs (with k fixed).

(iv) We say that a sequence of graphs {G_{n}} is 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.

Example 42. The following sequences are iteratively constructed:

(i) 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.

(ii) 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.

(iii) The cycles C_{n}, n ≥ 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.

Remark 43. In Fischer and Makowsky [23] there was an additional operation allowed:

• Duplicate: Add a disjoint copy of G to G.

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 [23].

8.3 The FM method

In this framework Fischer and Makowsky [23] proved the following result.

Theorem 44 (The FM-theorem). Let G_{n} be an iteratively constructed sequence of graphs, A ⊆ ℕ be ultimately periodic, and define

f_{ϕ}(G_{n}) = |{P_{1}, …, P_{k_{0}} ⊆ V (G_{n}) : ϕ(P_{1}, …, P_{k_{0}})}|

= ∑_{\begin{matrix}P_{1},...,P_{k_{0}}⊆V (G_{n}): \\ ϕ(P_{1},...,P_{k_{0}}) \end{matrix}} 1;

f_{ϕ,A}(G_{n}) = |{P_{1}, …, P_{k_{0}} ⊆ V (G_{n}) : ϕ(P_{1}, …, P_{k_{0}}) and |P_{i}| ∈ A}|

= ∑_{\begin{matrix}P_{1},...,P_{k_{0}}⊆V (G_{n}): \\ ϕ(P_{1},...,P_{k_{0}}) and |P_{i}|∈A \end{matrix}} 1,

where ϕ ∈ CMSOL. Then the sequences f_{ϕ}(G_{n}) and f_{ϕ,A}(G_{n}) are C-finite.

Remark 45. We use unary predicates for the partition, to make sure that the formula ϕ 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 46 below we have k_{1} = k_{0} − r.

We now use Theorem 44 to prove the following result:

Theorem 46. Let A be ultimately periodic, r, k_{0} ∈ ℕ. 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.

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 = ℕ.

We have to show that S_{A,r}(n, k_{0}) is of the form f_{ϕ,A}(G_{n}). We define an iteratively constructed sequence of graphs G = (V (G), E(G), v_{1}, …, v_{r}) with r distinct vertices as follows. G_{0} = (K_{r}, v_{1}, …, v_{r}). G_{n+1} = G_{n} ⊔ K_{1}.

Now take ϕ(P_{1}, …, P_{k_{0}}, v_{1}, …, v_{r}), which says that the P_{i}’s form a partition and for each i ≤ r the distinguished vertex v_{i} belongs to P_{i}(G).

Further details are given in Section 9.

9 Proof of Theorem 44 and its applications

In order to prove Theorem 44 we use Theorem 49 below. For this we have to introduce the definition of CMSOL-definable graph polynomials.

9.1 CMSOL-definable graph polynomials

Definition 47. Let ℤ be the ring of integers. We consider polynomials over ℤ[x̄]. For a CMSOL-formula for graphs ϕ(v̄) with v̄ = (v_{1}, …, v_{s}), define card_{G}(ϕ) to be the cardinality of subsets of V (G)^{s} defined by ϕ. The extended CMSOL graph polynomials are defined recursively. We first define the extended CMSOL-monomials. Let ϕ(v̄) ∈ CMSOL. An extended CMSOL-monomial is a term of one of the following possible forms:

• x^{card_{G}(ϕ)} where x is one of the variables of x̄.

• x_{(card_{G}(ϕ))} i.e., the falling factorial of x.

• \binom{x}{card_{G}(ϕ)}.

• ∏_{v̄∈V (G)^{s}:ϕ(v)} t(x̄)

Here v̄ ranges over tuples of vertices of G, t(x̄) is a term in ℤ[x̄], and x̄ are indeterminates of the polynomial.

The 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

∑_{U:ϕ(U)} t(x̄),

where ϕ is a CMSOL-formula with free set variables U, and t(x̄) is a term in the indeterminates x̄. They are also closed under multiplication over elements of V (G)^{s} of the form

∏_{v̄∈V (G)^{s}:ϕ(v)} t(x̄).

Lemma 48. The counting functions from Theorem 44, namely,

f_{ϕ}(G_{n}) = |{P_{1}, …, P_{k_{0}} ⊆ V (G_{n}) : ϕ(P_{1}, …, P_{k_{0}})}|

= ∑_{\begin{matrix}P_{1},...,P_{k_{0}}⊆V (G_{n}): \\ ϕ(P_{1},...,P_{k_{0}}) \end{matrix}} 1,

f_{ϕ,A}(G_{n}) = |{P_{1}, …, P_{k_{0}} ⊆ V (G_{n}) : ϕ(P_{1}, …, P_{k_{0}}) and |P_{i}| ∈ A}|

= ∑_{\begin{matrix}P_{1},...,P_{k_{0}}⊆V (G_{n}): \\ ϕ(P_{1},...,P_{k_{0}}) and |P_{i}|∈A \end{matrix}} 1

are CMSOL-definable graph polynomials without indeterminates, provided ϕ ∈ CMSOL and A is ultimately periodic.

We first state a theorem from Fischer and Makowsky [23, Theorem 1]:

Theorem 49. Let F be an elementary operation on graphs, {G_{n} : n ∈ ℕ} 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}, …, p_{k} ∈ ℤ[x̄] such that for sufficiently large n,

P (G_{n+k+1}) = ∑_{i=1}^{k} p_{i}P (G_{n+i}).

Proof of Theorem 44. Take for P the counting functions from Lemma 48 and apply Theorem 49.

9.2 Proofs of C-Finiteness

Now we give the details for the proof of Theorem 46. However, instead of using Theorem 44, we use Theorem 49 directly by exhibiting an appropriate iteratively constructible sequence of graphs.

Proposition 50. Fix k_{0} ∈ ℕ. Then S(n, k_{0}) is a C-finite sequence.

Proof. Let P be the graph property P = {K_{n} : n ≥ 1} of cliques with at least one vertex and define G_{n} = K_{n}. Note that a P-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_{P}(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 42 or Fischer and Makowsky [23, Proposition 2]. Hence H_{P} is an extended CMSOL graph polynomial and we can use Theorem 49.

Proposition 51. Fix k_{0} ∈ ℕ. Then S_{r}(n, k_{0}) is a C-finite sequence.

Proof. Let P be the graph property of edgeless graphs with at least one vertex, i.e., P = {K̄_{n} : n ≥ 1}, and define G_{n} = K_{r} ∪ K̄_{n}. Note that a P-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}) ⊆ V (G_{n}) is in a different color class, so H_{P}(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_{P} is again an extended CMSOL graph polynomial and we can use Theorem 49.

Proposition 52. Let A ⊆ ℕ, and k_{0} ∈ ℕ. Then S_{A}(n, k_{0}) is a C-finite sequence if and only if A is ultimately periodic.

Proof. First we note that S_{A}(n, 1) = 1 iff n ∈ 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 P be the graph property of cliques with vertex size in A, i.e., P = {K_{n} : n ∈ A}, and define G_{n} = K_{n}. Note that a P-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_{P}(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_{P} is again an extended CMSOL graph polynomial and we can use Theorem 49.

Proposition 53. Let A ⊆ ℕ, and k_{0} ∈ ℕ. Then S_{A,r}(n, k_{0}) is a C-finite sequence if and only if A is ultimately periodic.

Proof. We note that S_{A}(n, 1) = 1 iff n ∈ A. If A is not ultimately periodic, then also S_{A}(n, 1) is not C-finite. Assume that A is ultimately periodic. Let P be the graph property of edgeless graphs with vertex size in A, i.e., P = {K̄_{n} : n ∈ A}, and define G_{n} = K_{r} ∪ K̄_{n}. Note that a P-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}) ⊆ V (G_{n}) is in a different color class, so H_{P}(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_{P} is again an extended CMSOL graph polynomial and we can use Theorem 49.

10 Conclusions and further research

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 6, MC-finiteness follows from the existence of polynomial recurrence relations with coefficients in ℤ. In Theorem 10, 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 10 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 36. A proof of a special case of this theorem is given in Section 7. The general case can be found in [24]. Our new results are summarized in Tables 2–5.

We did not investigate in depth whether MC-finiteness of the examples in Tables 2–5 can be established directly or, alternatively, by exhibiting suitable polynomial recurrence schemes in order to apply Theorem 6.

Problem 54. Are the Bessel numbers B(n)^{B} MC-finite?

Problem 55. Find systems of mutual polynomial recurrences for all the examples in Tables 2–4.

Instead of set partition functions we can also count the number of, say, partial orders where

(i) the set of r special elements are in a particular CMSOL definable configuration, such as prescribed comparability and incomparability, and

(ii) the set of integers A indicates the possible cardinalities of certain definable sets, such as antichains or maximal linearly ordered sets.

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_{ϕ}(n). The reader not familiar with complexity of computation should consulta Arora and Barak [2] or Papadimitriou [45]. For a complete picture there is always the Complexity Zoo [1].

Clearly, S_{ϕ}(n) is computable by brute force, given ϕ and n. In fact, for ϕ ∈ FOL the problem is in ♯P. For ϕ ∈ CMSOL it is in ♯PH, the analogue of ♯P for problems definable in second-order logic, or equivalently, in the polynomial hierarchy. As noted in Makowsky and Pnueli [40, Proposition 11], there are arbitrarily complex problems in PH already definable in MSOL. However, S_{ϕ}^{m}(n) is in MOD_{m}P, respectively in MOD_{m}PH, the corresponding modular counting classes introduced by Beigel and Gill in [6]. It is still open how exactly MOD_{m}P is related to ♯P. Green et al. [32] introduced a counting complexity class MP ⊆ P^{♯P} and showed that for each m the complexity classes MOD_{m}P are low for MP. A complexity class B is low for a complexity class A if A^{B} ⊆ A. In other words, using B as an oracle for A does not yield more computational power. The reader further interested in details about complexity classes can consult the Complexity Zoo [1] as a guide to the literature.

Specker [54] mentions that S_{ϕ}^{m}(n) ≡ S_{ϕ}(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].

Problem 56. Given ϕ ∈ FOL and m, find algorithms for computing S_{ϕ}(n) and S_{ϕ}^{m}(n) and determine upper and lower bounds for them. One may assume that n is encoded in unary.

Problem 57. Same as Problem 56 for ϕ ∈ CMSOL.

Problem 58. Inspired by the remarks above, the following might be a worthwhile project: Investigate the complexity classes ♯PH and MOD_{m}PH and their mutual relationships.

11 Acknowledgments

The study of restricted set partition functions arose from questions in Rakita’s PhD thesis [47]. 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.

References

[1] Complexity Zoo. Electronic resource, available at https://complexityzoo.net/

Complexity_Zoo.

[2] Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

[3] Cyril Banderier, Jean-Luc Baril, and Céline Moreira Dos Santos, Right-jumps and pattern avoiding permutations, Discrete Math. Theor. Comput. Sci. 18 (2017), #12.

[4] Cyril Banderier, Mireille Bousquet-Mélou, Alain Denise, Philippe Flajolet, Daniele Gardy, and Dominique Gouyou-Beauchamps, Generating functions for generating trees, Discrete Math. 246 (2002), 29–55.

[5] Cyril Banderier and Florian Luca, On the period (mod m) of polynomially-recursive sequences: a case study, J. Integer Sequences 22 (2019), Article 19.5.2.

[6] Richard Beigel and John Gill, Counting classes: Thresholds, parity, mods, and fewness, Theoret. Comput. Sci. 103 (1992), 3–23.

[7] Beáta Bényi, Miguel Méndez, José L Ramírez, and Tanay Wakhare, Restricted r-Stirling numbers and their combinatorial applications, Appl. Math. Comput. 348 (2019), 186– 205.

[8] Beáta Bényi and José L. Ramírez, Some applications of s-restricted set partitions, Period. Math. Hungar. 78 (2019), 110–127.

[9] Daniel Berend and Tamir Tassa, Improved bounds on Bell numbers and on moments of sums of random variables, Probab. Math. Statist. 30 (2010), 185–205.

[10] Christian Blatter and Ernst Specker, Le nombre de structures finies d’une théorie á charactère fini, Sciences Mathématiques, Fonds Nationale de la Recherche Scientifique, Bruxelles (1981), 41–44.

[11] Christian Blatter and Ernst Specker, Recurrence relations for the number of labeled structures on a finite set, In In Logic and Machines: Decision Problems and Complexity, Vol. 171 of Lecture Notes in Comput. Sci., Springer, 1984, pp. 43–61.

[12] Andrei Z. Broder, The r-Stirling numbers, Discrete Math. 49 (1984), 241–259.

[13] Nicolaas Govert de Bruijn, Asymptotic Methods in Analysis, Vol. 4, Courier Corporation, 1981.

[14] Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk, and Géraud Sénizergues, On polynomial recursive sequences, In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Vol. 168 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 117:1–117:17. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2020.

[15] Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk, and Géraud Sénizergues, On polynomial recursive sequences, Electronically available at https://

doi.org/10.1007/s00224-021-10046-9, 2021. To appear in Theory Comput. Syst.

[16] Charalambos A. Charalambides, Enumerative Combinatorics, Chapman and Hall/CRC, 2018.

[17] Louis Comtet, Advanced Combinatorics: The Art of Finite and Infinite Expansions, Springer, 2012.

[18] Eldar Fischer and Johann A. Makowsky, Counting the number of finite topologies, manuscript in preparation, 2023.

[19] Graham Everest, Alfred J. van der Poorten, Igor Shparlinski, and Thomas Ward, Recurrence Sequences, Vol. 104 of Mathematical Surveys and Monographs, American Mathematical Society, 2003.

[20] Eldar Fischer, The Specker-Blatter theorem does not hold for quaternary relations, J. Combin. Theory Ser. A 103 (2003), 121–136.

[21] Eldar Fischer, Tomer Kotek, and Johann A. Makowsky, Application of logic to combinatorial sequences and their recurrence relations. In Model Theoretic Methods in Finite Combinatorics, Vol. 558 of Contemporary Mathematics. American Mathematical Society, 2011, pp. 1–42.

[22] Eldar Fischer and Johann A. Makowsky, The Specker-Blatter theorem revisited, In COCOON’03, Vol. 2697 of Lecture Notes in Comput. Sci., Springer, 2003, pp. 90–101.

[23] Eldar Fischer and Johann A. Makowsky, Linear recurrence relations for graph polynomials, In Pillars of Computer Science, Vol. 4800 of Lecture Notes in Comput. Sci., Springer, 2008, pp. 266–279.

[24] Eldar Fischer and Johann A. Makowsky, Extensions and limits of the Specker-Blatter theorem. Arxiv preprint arXiv:2206.12135, 2022. Available at https://arxiv.org/

abs/2206.12135.

[25] Philippe Flajolet and René Schott, Non-overlapping partitions, continued fractions, Bessel functions and a divergent series, European J. Combin. 11 (1990), 421–432.

[26] Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[27] OEIS Foundation, The on-line encyclopedia of integer sequences, 2023. Available at

https://oeis.org/.

[28] Stefan Gerhold, On some non-holonomic sequences, Electron. J. Combin. 11 (2004), #R87.

[29] Ira M. Gessel, Symmetric functions and P-recursiveness., J. Comb. Theory Ser. A 53 (1990), 257–285.

[30] Ian P. Goulden, David M. Jackson, and James W. Reilly, The Hammond series of a symmetric function and its application to P-recursiveness, SIAM J. Alg. Discrete Methods 4 (1983), 179–193.

[31] Ronald L Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, Addison-Wesley, 1989.

[32] Frederic Green, Johannes Kobler, Kenneth W Regan, Thomas Schwentick, and Jacobo Torán, The power of the middle bit of a #P function, J. Comput. System Sci. 50 (1995), 456–467.

[33] Bai-Ni Guo and Feng Qi, Six proofs for an identity of the Lah numbers, Online J. Anal. Comb. 10 (2015), 1–5.

[34] Manuel Kauers and Peter Paule, The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates, Springer, 2011.

[35] Martin Klazar, Bell numbers, their relatives, and algebraic differential equations, J. Combin. Theory Ser. A 102 (2003), 63–87.

[36] Thomas Koshy, Catalan Numbers with Applications, Oxford University Press, 2008.

[37] Ivo Lah, A new kind of numbers and its application in the actuarial mathematics, Bol. Inst. Actuár. Port. 9 (1954), 7–15.

[38] Johann A. Makowsky, Application of logic to integer sequences: a survey, In Logic, Language, Information and Computation, WoLLIC 2010, Vol. 6188 of Lecture Notes in Comput. Sci., Springer, 2010, pp. 34–41.

[39] Johann A. Makowsky and Tomer Kotek, Connection matrices and the definability of graph parameters, Log. Methods Comput. Sci. 10 (2014), 1–33.

[40] Johann A. Makowsky and Yachin B. Pnueli, Arity and alternation in second-order logic, Ann. Pure Appl. Logic 78 (1996), 189–202.

[41] Toufik Mansour, Combinatorics of Set Partitions, CRC Press, 2012.

[42] Brendan D. McKay, Applications of a technique for labelled enumeration, Congr. Numer. 40 (1983), 207–221.

[43] István Mező, Combinatorics and Number Theory of Counting Sequences, CRC Press, 2019.

[44] Gábor Nyul and Gabriella Rácz, The r-Lah numbers, Discrete Math. 338 (2015), 1660– 1666.

[45] Christos Papadimitriou, Computational Complexity, Addison-Wesley, 1994.

[46] Götz Pfeiffer, Counting transitive relations, J. Integer Sequences 7 (2004), Article 04.3.2.

[47] Vsevolod Rakita, On generating and Harary polynomials of graphs, PhD thesis, IIT– Israel Institute of Technology, May 2023.

[48] Ronald C. Read, Some unusual enumeration problems, Ann. New York Acad. Sci. 175 (1970), 314–326.

[49] Ronald C. Read and Nicholas C. Wormald, Number of labeled 4-regular graphs, J. Graph Theory 4 (1980), 203–212.

[50] James A. Reeds and Neil J. A. Sloane, Shift register synthesis (modulo m), SIAM J. Comput. 14 (1985), 505–513.

[51] Steven Roman, An Introduction to Catalan Numbers, Springer, 2015.

[52] Géraud Sénizergues, Sequences of level 1, 2, 3, …, k, …, In Computer Science in Russia, Vol. 4649 of Lecture Notes in Comput. Sci., Springer, 2007, pp. 24–32.

[53] Mark Shattuck, Generalized r-Lah numbers, Proc. Indian Acad. Sci. (Math. Sci.) 126 (2016), 461–478.

[54] Ernst Specker, Application of logic and combinatorics to enumeration problems. In Ernst Specker Selecta, Springer, 1990, pp. 324–350.

[55] Richard P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth and Brooks, 1986.

[56] Carl G. Wagner, Generalized Stirling and Lah numbers, Discrete Math. 160 (1996), 199–218.

2020 Mathematics Subject Classification: Primary 05A99; Secondary 05A10, 05A18, 05A99, 03C13, 11Y55. Keywords: set partition function, C-Finiteness, MC, finiteness, supercongruence, monadic second-order logic, Specker-Blatter theorem.

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

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 Journal of Integer Sequences, August 4 2023.

Return to Journal of Integer Sequences home page.