Periodicity of the Last Digits of Some Combinatorial Sequences^{1}

István Mező Escuela Politécnica Nacional Departamento de Matemática Ladrón de Guevara E11-253 Quito, Ecuador

                    istvan.mezo@epn.edu.ec

Abstract In 1962 O. A. Gross proved that the last digits of the Fubini numbers (or surjective numbers) have a simple periodicity property. We extend this result to a wider class of combinatorial numbers coming from restricted set partitions.

1 The Stirling numbers of the second kind and the Fubini numbers

The nth Fubini number or surjection number [18, 22, 31, 34, 35], F_{n}, counts all the possible partitions of n elements such that the order of the blocks matters. The \left\{{n \atop k}\right\} Stirling number of the second kind with parameters n and k enumerates the partitions of n elements into k blocks. Thus, F_{n} has the following expression:

F_{n} = ∑_{k=0}^{n} k!\left\{{n \atop k}\right\}.  (1)

The first Fubini numbers are presented in the next table:

1This scientific work was financed by Proyecto Prometeo de la Secretaría Nacional de Ciencia, Tecnología e Innovación (Ecuador).

\begin{matrix}F_{1} & F_{2} & F_{3} & F_{4} & F_{5} & F_{6} & F_{7} & F_{8} & F_{9} & F_{10} \\ 1 & 3 & 13 & 75 & 541 & 4 683 & 47 293 & 545 835 & 7 087 261 & 102 247 563 \end{matrix}

We may realize that the last digits form a periodic sequence of length four. This is true up to infinity. That is, for all n ≥ 1

Congruence 1.

F_{n+4} ≡ F_{n} (mod 10).

A proof was given by Gross [20] which uses backward differences. Later we give a simple combinatorial proof.

We note that if the order of the blocks does not matter, we get the Bell numbers [11]:

B_{n} = ∑_{k=0}^{n} \left\{{n \atop k}\right\}.

This sequence does not possess this “periodicity property”.

Now we introduce other classes of numbers which do share this periodicity.

2 The r-Stirling and r-Fubini numbers

The r-Stirling number of the second kind with parameters n and k is denoted by \left\{{n \atop k}\right\}_{r} and enumerates the partitions of n elements into k blocks such that all the first r elements are in different blocks. So, for example, {1, 2, 3, 4, 5} can be partitioned into {1, 4, 5} ∪ {2, 3} but {1, 2} ∪ {3, 5} ∪ {4} is forbidden, if r ≥ 2. An introductory paper on r-Stirling numbers is due to Broder [5]. A good source of combinatorial identities on r-Stirling numbers is a book of Charalambides [6]. (Note that in this book these numbers are called noncentral Stirling numbers.)

Similarly to (1) we can introduce the r-Fubini numbers as

F_{n,r} = ∑_{k=0}^{n}(k + r)!\left\{{n + r \atop k + r}\right\}_{r}.  (2)

(It is worthwile to shift the indices, since the upper and lower parameters have to be at least r, so n and k can run from zero in the formula.)

We note that the literature of these numbers is rather thin. From the analytical point of view they were discussed by Corcino and his co-authors [12]. The present author with Nyul [28] is preparing a manuscript which studies these numbers in a combinatorial way.

The first 2-Fubini and 3-Fubini numbers are

\begin{matrix}F_{1,2} & F_{2,2} & F_{3,2} & F_{4,2} & F_{5,2} & F_{6,2} & F_{7,2} & F_{8,2} \\ 10 & 62 & 466 & 4 142 & 42 610 & 498 542 & 6 541 426 & 95 160 302 \end{matrix}

and

\begin{matrix}F_{1,3} & F_{2,3} & F_{3,3} & F_{4,3} & F_{5,3} & F_{6,3} & F_{7,3} & F_{8,3} \\ 42 & 342 & 3 210 & 34 326 & 413 322 & 5 544 342 & 82 077 450 & 1 330 064 406 \end{matrix}

We see that the sequence of the last digits is also periodic with period four: Congruence 2.

F_{n+4,r} ≡ F_{n,r} (mod 10) (n, r ≥ 1).

If the order of the blocks does not interest us, we get the r-Bell numbers:

B_{n,r} = ∑_{k=0}^{n} \left\{{n + r \atop k + r}\right\}_{r}.

These numbers were discussed combinatorially in a paper of the present author [26] and analytically by Corcino and his co-authors [13, 14], and also by Dil and Kurt [15]. The table of these numbers [26] shows that there is possibly no periodicity in the last digits of the r-Bell numbers.

3 Restricted Stirling numbers and three derived sequences

Let us go further and introduce another class of Stirling numbers. The \left\{{n \atop k}\right\}_{≤m} restricted Stirling number of the second kind [1, 8, 9, 10] gives the number of partitions of n elements into k subsets under the restriction that none of the blocks contain more than m elements. The notation reflects this restrictive property.

The sum of restricted Stirling numbers gives the restricted Bell numbers [30]:

B_{n,≤m} = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{≤m}.

Their tables are as follows:

\begin{matrix}B_{1,≤2} & B_{2,≤2} & B_{3,≤2} & B_{4,≤2} & B_{5,≤2} & B_{6,≤2} & B_{7,≤2} & B_{8,≤2} & B_{9,≤2} & B_{10,≤2} & B_{11,≤2} \\ 1 & 2 & 4 & 10 & 26 & 76 & 232 & 764 & 2 620 & 9 496 & 35 696 \end{matrix}

\begin{matrix}B_{1,≤3} & B_{2,≤3} & B_{3,≤3} & B_{4,≤3} & B_{5,≤3} & B_{6,≤3} & B_{7,≤3} & B_{8,≤3} & B_{9,≤3} & B_{10,≤3} & B_{11,≤3} \\ 1 & 2 & 5 & 14 & 46 & 166 & 652 & 2 780 & 12 644 & 61 136 & 312 676 \end{matrix}

\begin{matrix}B_{1,≤4} & B_{2,≤4} & B_{3,≤4} & B_{4,≤4} & B_{5,≤4} & B_{6,≤4} & B_{7,≤4} & B_{8,≤4} & B_{9,≤4} & B_{10,≤4} & B_{11,≤4} \\ 1 & 2 & 5 & 15 & 51 & 196 & 827 & 3 795 & 18 755 & 99 146 & 556 711 \end{matrix}

If we eliminate the first elements B_{1,≤2} and B_{1,≤3}, B_{2,≤3}, B_{3,≤3} we can see that these sequences, for m = 2, 3, seem to be periodic of length five: Congruence 3.

B_{n,≤2} ≡ B_{n+5,≤2} (mod 10) (n > 1).
B_{n,≤3} ≡ B_{n+5,≤3} (mod 10) (n > 3).

The third table shows that such kind of congruence cannot be proven if m = 4. The proof of the above congruence for m = 2, 3 is contained in the 5.3 subsection. We will also explain why this property fails to hold whenever m > 3.

What happens, if we take restricted Fubini numbers, as

F_{n,≤m} = ∑_{k=0}^{n} k!\left\{{n \atop k}\right\}_{≤m}?  (3)

The next congruences hold.

Congruence 4.

F_{n,≤1} ≡ 0 (mod 10) (n > 4),
F_{n,≤m} ≡ 0 (mod 10) (n > 4, m = 2, 3, 4),  (4)
F_{n,≤m} ≡ 0 (mod 2) (n > m, m > 4).  (5)

The first congruence is trivial, since F_{n,≤1} = n!. The others will be proved in subsection 5.4.

If we consider restricted Stirling numbers of the first kind, a similar conjecture can be phrased. These numbers with parameter n, k and m count all the permutations on n elements with k cycles such that all cycles contain at most m items. Let us denote these numbers by \left[{n \atop k}\right]_{≤m}. Then let

A_{n,≤m} = ∑_{k=0}^{n} \left[{n \atop k}\right]_{≤m}.

We may call these as restricted factorials, since if m = n (there is no restriction) we get that A_{n,≤m} = n!. Note that the sequence (n!) is clearly periodic in the present sense, because n! ≡ 0 (mod 10) if n > 4. The tables

\begin{matrix}A_{1,≤3} & A_{2,≤3} & A_{3,≤3} & A_{4,≤3} & A_{5,≤3} & A_{6,≤3} & A_{7,≤3} & A_{8,≤3} & A_{9,≤3} & A_{10,≤3} & A_{11,≤3} \\ 1 & 2 & 6 & 18 & 66 & 276 & 1 212 & 5 916 & 31 068 & 171 576 & 1 014 696 \end{matrix}

\begin{matrix}A_{1,≤4} & A_{2,≤4} & A_{3,≤4} & A_{4,≤4} & A_{5,≤4} & A_{6,≤4} & A_{7,≤4} & A_{8,≤4} & A_{9,≤4} & A_{10,≤4} & A_{11,≤4} \\ 1 & 2 & 6 & 24 & 96 & 456 & 2 472 & 14 736 & 92 304 & 632 736 & 4 661 856 \end{matrix}

suggest that A_{n,≤m} is perhaps periodic of order five. The next result can be phrased as follows:

Congruence 5.

A_{n,≤m} ≡ A_{n+5,≤m} (mod 10) (n > 2, m = 2, 3, 4).

Our argument presented in the subsection 5.5 will show that the restricted factorial numbers all terminate with digit 0 if n > 4 and m > 4, this is the reason why we excluded above the case m > 4.

Note that A_{n,≤2} = B_{n,≤2} and this number equals to the number of involutions on n elements. (Involution is a permutation π such that π^{2} = 1, the identity permutation.).

4 The associated Stirling numbers

At the end we turn to the definition of the associated Stirling numbers. The m-associated Stirling number of the second kind with parameters n and k, denoted by \left\{{n \atop k}\right\}_{≥m}, gives the number of partitions of an n element set into k subsets such that every block contains at least m elements [11, p. 221].

The associated Bell numbers are

B_{n,≥m} = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{≥m}.

The tables for m = 2, 3, 4 (B_{n,≥1} = B_{n}, the nth Bell number) follow.

\begin{matrix}B_{1,≥2} & B_{2,≥2} & B_{3,≥2} & B_{4,≥2} & B_{5,≥2} & B_{6,≥2} & B_{7,≥2} & B_{8,≥2} & B_{9,≥2} & B_{10,≥2} & B_{11,≥2} \\ 0 & 1 & 1 & 4 & 11 & 41 & 162 & 715 & 3 425 & 17 722 & 98 253 \end{matrix}

\begin{matrix}B_{1,≥3} & B_{2,≥3} & B_{3,≥3} & B_{4,≥3} & B_{5,≥3} & B_{6,≥3} & B_{7,≥3} & B_{8,≥3} & B_{9,≥3} & B_{10,≥3} & B_{11,≥3} \\ 0 & 0 & 1 & 1 & 1 & 11 & 36 & 92 & 491 & 2 557 & 11 353 \end{matrix}

\begin{matrix}B_{1,≥4} & B_{2,≥4} & B_{3,≥4} & B_{4,≥4} & B_{5,≥4} & B_{6,≥4} & B_{7,≥4} & B_{8,≥4} & B_{9,≥4} & B_{10,≥4} & B_{11,≥4} \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 36 & 127 & 337 & 793 \end{matrix}

Here one cannot observe periodicity in the last digits. However, this is not the case, if we take the associated Fubini numbers, where the order of the blocks counts:

F_{n,≥m} = ∑_{k=0}^{n} k!\left\{{n \atop k}\right\}_{≥m}.

Since F_{n,≥1} = F_{n}, the nth Fubini number, we present the table of these numbers for m = 2, 3, 4:

\begin{matrix}F_{1,≥2} & F_{2,≥2} & F_{3,≥2} & F_{4,≥2} & F_{5,≥2} & F_{6,≥2} & F_{7,≥2} & F_{8,≥2} & F_{9,≥2} & F_{10,≥2} & F_{11,≥2} \\ 0 & 1 & 1 & 7 & 21 & 141 & 743 & 5 699 & 42 241 & 382 153 & 3 586 155 \end{matrix}

\begin{matrix}F_{1,≥3} & F_{2,≥3} & F_{3,≥3} & F_{4,≥3} & F_{5,≥3} & F_{6,≥3} & F_{7,≥3} & F_{8,≥3} & F_{9,≥3} & F_{10,≥3} & F_{11,≥3} \\ 0 & 0 & 1 & 1 & 1 & 21 & 71 & 183 & 2 101 & 13 513 & 64 285 \end{matrix}

\begin{matrix}F_{1,≥4} & F_{2,≥4} & F_{3,≥4} & F_{4,≥4} & F_{5,≥4} & F_{6,≥4} & F_{7,≥4} & F_{8,≥4} & F_{9,≥4} & F_{10,≥4} & F_{11,≥4} \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 71 & 253 & 673 & 1 585 \end{matrix}

The next special values are trivial:

F_{0,≥m} = 1, F_{n,≥m} = 0 (0 < n < m), F_{m,≥m} = 1.

We will prove that the associated Fubini numbers are always odd, when n ≥ m: Congruence 6.

F_{n,≥m} ≡ 1 (mod 2) (n ≥ m),

and that the last digits form a periodic sequence of length 20: Congruence 7.

F_{n,≥m} ≡ F_{n+20,≥m} (mod 10) (n ≥ 5, m = 2, 3, 4, 5).

This last congruence is rather unusual, because the length of the period is 20, larger than for the other treated sequences, and, in addition, if m = 1 (Fubini number case), the period is just 4.

5 Proof of the congruences

Now we start to give the proofs of the above congruences.

5.1 The Fubini numbers – Congruence 1

We prove Congruence 1 of Gross, which states that

F_{n+4} ≡ F_{n} (mod 10).

Let n > 4. By the definition,

F_{n+4} − F_{n} = ∑_{k=0}^{n+4} k!\left\{{n + 4 \atop k}\right\} − ∑_{k=0}^{n} k!\left\{{n \atop k}\right\} =

∑_{k=5}^{n+4} k!\left\{{n + 4 \atop k}\right\} − ∑_{k=5}^{n} k!\left\{{n \atop k}\right\} + ∑_{k=0}^{4} k!\left\{{n + 4 \atop k}\right\} − ∑_{k=0}^{4} k!\left\{{n \atop k}\right\} ≡

\left\{{n + 4 \atop 0}\right\} + \left\{{n + 4 \atop 1}\right\} + 2\left\{{n + 4 \atop 2}\right\} + 6\left\{{n + 4 \atop 3}\right\} + 24\left\{{n + 4 \atop 4}\right\}

−\left\{{n \atop 0}\right\} − \left\{{n \atop 1}\right\} − 2\left\{{n \atop 2}\right\} − 6\left\{{n \atop 3}\right\} − 24\left\{{n \atop 4}\right\} (mod 10).

Because of the special values \left\{{n \atop 0}\right\} = 0, \left\{{n \atop 1}\right\} = 1, the first two members cancel. The remaining terms are divisible by two, so it is enough to prove that

5 |(\left\{{n + 4 \atop 2}\right\} + 3\left\{{n + 4 \atop 3}\right\} + 12\left\{{n + 4 \atop 4}\right\} − \left\{{n \atop 2}\right\} − 3\left\{{n \atop 3}\right\} − 12\left\{{n \atop 4}\right\}) .

The special values [4, p. 12.]

\left\{{n \atop 2}\right\} = 2^{n−1} − 1, \left\{{n \atop 3}\right\} = \frac{1}{2} (3^{n−1} − 2^{n} + 1) , \left\{{n \atop 4}\right\} = \frac{1}{6}4^{n−1} − \frac{1}{2}3^{n−1} + 2^{n−2} − \frac{1}{6}

give that

\left\{{n + 4 \atop 2}\right\} − \left\{{n \atop 2}\right\} = 2^{n+3} − 1 − (2^{n−1} − 1) = 15 · 2^{n−1},
3\left\{{n + 4 \atop 3}\right\} − 3\left\{{n \atop 3}\right\} = \frac{3}{2} (3^{n−1}(3^{4} − 1) − 2^{n}(2^{4} − 1)) ,
12\left\{{n + 4 \atop 4}\right\} − 12\left\{{n \atop 4}\right\} = \frac{12}{2} (\frac{1}{3}4^{n−1}(4^{4} − 1) − 3^{n−1}(3^{4} − 1) + 2^{n−2}(2^{4} − 1)) .

All of these numbers – independently from n – are divisible by 5, so we proved the periodicity of Fubini numbers.

5.2 The r-Fubini numbers – Congruence 2

The generalization of the congruence of Gross to the r-Stirling case states that

F_{n+4,r} ≡ F_{n,r} (mod 10) (n, r ≥ 1).

Definition (2) immediately gives that if r > 5, 10 | F_{n,r} for all n > 0, so the periodicity is trivial. If r = 1, we get back the ordinary Fubini numbers (up to a shifting), so we can restrict ourselves to 2 ≤ r ≤ 4. So

F_{n+4,r} − F_{n,r} ≡^{r=2} 2\left\{{n + 4 + r \atop r}\right\}_{r} + 6\left\{{n + 4 + r \atop r + 1}\right\}_{r} + 24\left\{{n + 4 + r \atop r + 2}\right\}_{r}

− 2\left\{{n + r \atop r}\right\}_{r} − 6\left\{{n + r \atop r + 1}\right\}_{r} − 24\left\{{n + r \atop r + 2}\right\}_{r},

≡^{r=3} 6\left\{{n + 4 + r \atop r}\right\}_{r} + 24\left\{{n + 4 + r \atop r + 1}\right\}_{r}

− 6\left\{{n + r \atop r}\right\}_{r} − 24\left\{{n + r \atop r + 1}\right\}_{r},

≡^{r=4} 24\left\{{n + 4 + r \atop r}\right\}_{r} − 24\left\{{n + r \atop r}\right\}_{r} (mod 10).

We need the following special values:

\left\{{n + r \atop r}\right\}_{r} = r^{n},  (6)
\left\{{n + r \atop r + 1}\right\}_{r} = (r + 1)^{n} − r^{n},  (7)
\left\{{n + r \atop r + 2}\right\}_{r} = \frac{1}{2}(r + 2)^{n} − (r + 1)^{n} + \frac{1}{2}r^{n}.  (8)

The first identity can be proven easily: the left hand side counts the partitions of n + r elements into r subsets such that the first r elements are in different subsets. Such partitions can be formed in the following way: we put the first r elements into singletons and the remaining n elements go to these r blocks independently: we have r^{n} possibilities.

The proof of the second special value is similar, but now we have an additional block. We put again our first r elements into r different blocks, and the remaining n elements go to these and to the additional block. Up to now we have (r + 1)^{n} possibilities. But the last block cannot be empty, so we have to exclude the cases when all the n elements go to the first r partition. The number of such cases is r^{n}. These considerations give (7).

The left hand side of the third identity is the number of partitions of n + r elements into r + 2 blocks with the usual restriction. Let us suppose that the two additional blocks contain k elements from n. We can choose these elements in \binom{n}{k} ways and then we construct a partition with the two blocks: \left\{{k \atop 2}\right\} possibilities. (Note that k ≥ 2.) The remaining n − k elements go to the first r block independently in r^{n−k} ways. We sum on k to get

\left\{{n + r \atop r + 2}\right\}_{r} = ∑_{k=2}^{n} \binom{n}{k}\left\{{k \atop 2}\right\}r^{n−k}.

Since \left\{{k \atop 2}\right\} = 2^{k−1} − 1, the binomial theorem yields the desired identity.

We go back to prove our congruence of the r-Fubini numbers. Since the others are simpler and similar, we deal only with the case r = 2; we prove that

F_{n+4,r} − F_{n,r} ≡ 2\left\{{n + 4 + r \atop r}\right\}_{r} + 6\left\{{n + 4 + r \atop r + 1}\right\}_{r} + 24\left\{{n + 4 + r \atop r + 2}\right\}_{r}

−2\left\{{n + r \atop r}\right\}_{r} − 6\left\{{n + r \atop r + 1}\right\}_{r} − 24\left\{{n + r \atop r + 2}\right\}_{r} ≡ 0 (mod 10).

It is enough to prove that the paired terms with the same lower parameter are divisible by five. Our special r-Stirling number values imply that

\left\{{n + 4 + r \atop r}\right\}_{r} − \left\{{n + r \atop r}\right\}_{r} = 2^{n}(2^{4} − 1),
\left\{{n + 4 + r \atop r + 1}\right\}_{r} − \left\{{n + r \atop r + 1}\right\}_{r} = 3^{n}(3^{4} − 1) − 2^{n}(2^{4} − 1),
\left\{{n + 4 + r \atop r + 2}\right\}_{r} − \left\{{n + r \atop r + 2}\right\}_{r} = \frac{1}{2}4^{n}(4^{4} − 1) − 3^{n}(3^{4} − 1) + \frac{1}{2}2^{n}(2^{4} − 1).

For any n > 0, these values are all divisible by five, so we are done.

5.3 The restricted Bell numbers – Congruence 3

Let us prove Congruence 3. Miksa, Moser and Wyman [30] proved that

Congruence 8.

B_{n+p,≤m} ≡ B_{n,≤m} (mod p) (m < p)

holds for any prime p. In particular, if p = 5, we have that

Congruence 9.

B_{n+5,≤m} ≡ B_{n,≤m} (mod 5) (m = 2, 3, 4).

Utilizing (9), we can prove the periodicity of the last digits if we prove that B_{n,≤m} is even. This will hold just when m = 2 or 3.

A theorem of Miksa, Moser, and Wyman [30, Theorem 2.] says that

B_{n+1,≤m} = B_{n,≤m} + \binom{n}{1}B_{n−1,≤m} + \binom{n}{2}B_{n−2,≤m} + ⋯ + \binom{n}{m − 1}B_{n−m+1,≤m}. (9)

In particular, if m = 2, we have

B_{n+1,≤2} = B_{n,≤2} + \binom{n}{1}B_{n−1,≤2},

and if m = 3, then

B_{n+1,≤3} = B_{n,≤3} + \binom{n}{1}B_{n−1,≤3} + \binom{n}{2}B_{n−2,≤3}.

These show that if two (resp. three) consecutive terms are even, then all the rest are also even. Checking the tables given above, we have, in particular, that B_{n,≤2} is even for all n ≥ 2 and B_{n,≤3} is even for all n ≥ 4.

Taking the above considerations, Congruence 3 is proven.

Although B_{n,≤4} does not share this property for small n, it can happen that for a large n three consecutive terms are even. This would imply the periodicity from that index. For larger m this is not enough, because Congruence 9 does not hold for these m.

5.3.1 A formula for the restricted Bell numbers

Although we do not need them, we also can prove easily the following properties:

B_{n,≤m} = B_{n} (n ≤ m),
B_{n,≤m} = B_{n} − ∑_{k=1}^{n−m} \binom{n}{m + k}B_{n−m−k} (m < n ≤ 2m).

Here B_{n} is the nth Bell number, defined by

B_{n} = ∑_{k=0}^{n} \left\{{n \atop k}\right\}.

The case n ≤ m is trivial, since n < m means that there is no restriction, so we get back the Bell numbers indeed. If m < n ≤ 2m, from the number of all the partitions on n elements (which is B_{n}), we have to exclude the tilted cases, i.e., when one of the blocks contains more than m elements. There can be only one such block, say A. If A contains m + k elements (0 < k ≤ n − m), we have to choose these elements coming to A; there are \binom{n}{m+k} cases. In the other blocks there are n − (m + k) elements, which can be partitioned in B_{n−m−k} ways. If we substract all of these possibilities parametrized by k, we are done.

In particular, we have that

B_{m+1,≤m} = B_{m+1} − 1 (m > 1),
B_{m+2,≤m} = B_{m+2} − 1 − (m + 2) (m > 1).

5.4 The restricted Fubini numbers – Congruence 4

The number F_{n,≤m} (see (3)) counts the ordered partitions on n elements, where the blocks in each partition cannot contain more than m elements. We can give the next interpretation as well. There are F_{n,≤m} ways to classify n persons in a competition where draws are allowed but no more than m persons can have the same position. This helps us to find a simple recursion for F_{n,≤m}: from the n persons k will go to the first place (1 ≤ k ≤ m) and the remaining competitors will classified to the rest of the positions in F_{n−k,≤m} ways. In formula,

F_{n,≤m} = \binom{n}{1}F_{n−1,≤m} + \binom{n}{2}F_{n−2,≤m} + ⋯ + \binom{n}{m}F_{n−m,≤m}.  (10)

Hence we see that to determine F_{n,≤m} we need the previous m members of the sequence. In particular, when m = 2, 3, 4, to get divisibility by 10, it is enough to see that there are two, three, four consecutive terms divisible by 10. This is satisfied, thus we have justified (4).

Proving (5), we use the definition of the restricted Fubini numbers directly:

F_{n,≤m} = ∑_{k=0}^{n} k!\left\{{n \atop k}\right\}_{≤m} ≡ \left\{{n \atop 1}\right\}_{≤m} (mod 2) (n > 0).

The value \left\{{n \atop 1}\right\}_{≤m} is zero if n > m.

5.5 The restricted factorials – Congruence 5

To prove Congruence 5, we begin with the dual of the identity (9):

A_{n+1,≤m} =  (11)
A_{n,≤m} + nA_{n−1,≤m} + n(n − 1)A_{n−2,≤m} + ⋯ + n(n − 1) ⋯ (n − m)A_{n−m+1,≤m}.

The initial values are A_{0,≤m} = A_{1,≤m} = 1.

The proof is as follows. The number A_{n+1,≤m} gives the number of permutations on the set {1, 2, …, n + 1} such that none of the cycles in the permutation contains more than m elements. We pick up the last element, say. This can go to a one element cycle, and the remaining n elements go to a restricted permutations in A_{n,≤m} ways. If the cycle of the last element contains k ≥ 1 additional elements (k < m), we have to form a cycle with these elements, and the remaining elements go to a restricted permutation in A_{n−k,≤m} ways. We choose these elements in \binom{n}{k} ways. But, since the order of the elements in the cycle counts, we multiply \binom{n}{k} with k!. Summing over k = 1, 2, …, m − 1, we are done.

This identity helps us to prove the next congruence, which is the dual of Congruence 8:

Congruence 10.

A_{n+p,≤m} ≡ A_{n,≤m} (mod p) (m < p),

where p is a prime number.

First we prove that Congruence 11.

A_{p,≤m} ≡ 1 (mod p) (m < p).

This can be seen via the following representation:

A_{n,≤m} = ∑_{1a_{1}+2a_{2}+···+ma_{m}=n} \frac{n!}{1^{a_{1}}a_{1}!2^{a_{2}}a_{2}! ⋯ m^{a_{m}}a_{m}!}.

The validity of this representation can be seen easily: if we construct a partition on n elements with cycles containing at most m elements, then we can have, say, a_{1} cycles with one element, a_{2} cycles with two elements, and finally a_{m} cycles with m elements. The order n! of the elements must be divided by the order of the cycles with the same elements (a_{1}! ⋯ a_{m}!) and with the identical arrangements in the separate cycles (1^{a_{1}} ⋯ m^{a_{m}}).

Now Congruence 11 can be justified easily: if m < p, in the denominator p does not appear as a factor, except when a_{1} = p. Therefore in the sum all the terms will congruent to 0 modulo p, and the term corresponding to a_{1} = p, a_{2} = ⋯ = a_{m} = 0 is congruent to 1 modulo p.

Having these results, we can give the proof of Congruence 10 by induction. If n = 0 the result is just Congruence 11, since A_{0,≤m} = 1. Let us suppose that the result holds true for all k ≤ n. By (11) we have that

A_{n+1+p,≤m} =
A_{n+p,≤m} + (n + p)A_{n+p−1,≤m} + (n + p)(n + p − 1)A_{n+p−2,≤m} + ⋯ +
(n + p)(n + p − 1) ⋯ (n + p − m)A_{n+p−m+1,≤m}.

In the factors of the restricted factorials p can be deleted modulo p. This and the induction hypothesis yield that

A_{n+1+p,≤m} ≡
A_{n,≤m} + nA_{n−1,≤m} + n(n − 1)A_{n−2,≤m} + ⋯ +
(n)(n − 1) ⋯ (n − m)A_{n−m+1,≤m} (mod p).

The sum equals to A_{n+1,≤m}, and Congruence 10 has been proven.

Finishing up the proof of Congruence 5, we apply (11) when m = 3, 4 (the m = 2 case is done by the A_{n,≤2} = B_{n,≤2} correspondence) to get

A_{n+1,≤3} = A_{n,≤3} + nA_{n−1,≤3} + n(n − 1)A_{n−2,≤3},
A_{n+1,≤4} = A_{n,≤4} + nA_{n−1,≤4} + n(n − 1)A_{n−2,≤4} + n(n − 1)(n − 2)A_{n−3,≤4}.

These show that if respectively three and four consecutive terms are even, the rest are even as well. Checking the given tables for these sequences this is justified. Specializing Congruence 10 with p = 5, Congruence 5 is proven.

To terminate this section, we additionally prove the next congruence.

Congruence 12.

A_{n,≤m} ≡ 0 (mod 10) (n > m > 4).

Identity (11) shows that to determine A_{n,≤m} we need m consecutive terms terminating with A_{n−1,≤m}. Moreover, A_{n,≤m} = n! if n ≤ m which is congruent to 0 modulo 10 whenever m > 4. Hence, again by the recursion, it is enough to prove that

A_{m+1,≤m} ≡ A_{m+2,≤m} ≡ A_{m+3,≤m} ≡ A_{m+4,≤m} ≡ 0 (mod 10).  (12)

First, we consider the case

A_{m+1,≤m} =
A_{m,≤m} + mA_{m−1≤m} + m(m − 1)A_{m−2,≤m} + ⋯ + m(m − 1) ⋯ 2A_{1,≤m} =
m! + m(m − 1)! + m(m − 1)(m − 2)! + ⋯ + m(m − 1) ⋯ 2 · 1! = m · m!.

If m > 4, this is already congruent to 0 modulo 10. Let us continue with

A_{m+2,≤m} =
A_{m+1,≤m} + (m + 1)A_{m≤m} + (m + 1)mA_{m−1,≤m} + ⋯ + (m + 1)m ⋯ 3A_{2,≤m} =
m · m! + (m + 1)m! + (m + 1)m(m − 1)! + ⋯ + (m + 1)m ⋯ 3 · 2!

All the factors are divisible by 10, because m > 4. Hence, together with the last point, we proved the first two congruence of (12). The remaining cases can be treated similarly.

5.6 Associated Fubini numbers – Congruences 6 and 7

Now we turn to the parity of the sequences F_{n,≥m}, that is, we prove Congruence 6:

F_{n,≥m} ≡ \left\{{n \atop 0}\right\}_{≥m} + \left\{{n \atop 1}\right\}_{≥m} (mod 2).

The first Stirling number term is zero if n > 0, and the second one is 1 if n ≥ m, otherwise it is zero as well.

The proof of Congruence 7 needs to be separated into the different cases when m = 2, 3, 4, 5.

First, let m = 2. Then we can prove the following special values for associated Stirling numbers of the second kind:

\left\{{n \atop 2}\right\}_{≥2} = \frac{1}{2}(2^{n} − 2n − 2),  (13)
\left\{{n \atop 3}\right\}_{≥2} = \frac{1}{6}(3^{n} − 3 · 2^{n}) − \frac{1}{2}n(2^{n−1} − 1) + \frac{1}{2}(n^{2} + 1),  (14)
\left\{{n \atop 4}\right\}_{≥2} = \frac{4^{n}}{24} − \frac{3^{n}}{18}(n + 3) − \frac{1}{6}(n^{3} + 2n + 1) + \frac{2^{n}}{16}(n^{2} + 3n + 4).  (15)

These relations hold for n ≥ 4, 6, 8, respectively. To see why the first relation holds, let us form a partition of n elements into two blocks such that these blocks contain at least two elements. We can sort our elements into the two blocks in 2^{n} ways, and then sort out the tilted partitions. A partition is tilted if one of the blocks does not contain any element (two possibilities), or one of the blocks contains just one element; which is 2n possibilities. Since the order of the blocks does not matter, we divide by two. This consideration gives (13).

Relation (14) can be proven as follows. We pick one of the blocks from the three and select at least two elements putting them into this block, but we cannot select more than n − 4 items to assure us that in the other blocks remain at least 2 + 2 elements. Let k be the number of the selected items. The two unpicked blocks can be considered as a partition on n − k elements with two blocks: \left\{{n−k \atop 2}\right\}_{≥2} possibilities. Hence we get our intermediate relation:

\left\{{n \atop 3}\right\}_{≥2} = \frac{1}{3} ∑_{k=2}^{n−4} \binom{n}{k}\left\{{n − k \atop 2}\right\}_{≥2}.

We divided by 3, because to pick the initial block we had three equivalent possibilities. The order of the blocks does not count. Finally, substituting the special value (13), after some sum binomial manipulations we are done.

We note that the above identity can be generalized as follows:

\left\{{n \atop k}\right\}_{≥m} = \frac{1}{k} ∑_{k=m}^{n−(k−1)m} \binom{n}{k}\left\{{n − k \atop k − 1}\right\}_{≥m} (n ≥ km).  (16)

The just presented generalization is applicable to prove (15), too.

Now let us go back to the proof of Congruence 7 with m = 2.

F_{n+20,≥2} − F_{n,≥2} = ∑_{k=0}^{n+20} k!\left\{{n + 20 \atop k}\right\}_{≥2} − ∑_{k=0}^{n} k!\left\{{n \atop k}\right\}_{≥2} ≡

≡ \left\{{n + 20 \atop 0}\right\}_{≥2} + \left\{{n + 20 \atop 1}\right\}_{≥2} + 2\left\{{n + 20 \atop 2}\right\}_{≥2} + 6\left\{{n + 20 \atop 3}\right\}_{≥2} + 24\left\{{n + 20 \atop 4}\right\}_{≥2}

−\left\{{n \atop 0}\right\}_{≥2} − \left\{{n \atop 1}\right\}_{≥2} − 2\left\{{n \atop 2}\right\}_{≥2} − 6\left\{{n \atop 3}\right\}_{≥2} − 24\left\{{n \atop 4}\right\}_{≥2} (mod 10).

The first terms with lower parameters 0 and 1 are cancelled by the respective terms in the second line. What remains is

F_{n+20,≥2} − F_{n,≥2} = \frac{1}{6} ( − 320 · 3^{n}(1939523823 + 87169610n)+

15 (219902325555 · 2^{2n+1} − 8(1547 + 6n(39 + 2n))+
3 · 2^{n}(92833928 + n(8808038 + 209715n)))) .

An induction shows that this is always divisible by 5 if n ≥ 5.

Now let us fix m = 3. The special values for the associated Stirling numbers with small lower parameters are

\left\{{n \atop 2}\right\}_{≥3} = \frac{1}{2} (2^{n} − 2 − 2n − 2\binom{n}{2}) ,
\left\{{n \atop 3}\right\}_{≥3} = \frac{1}{16} (24 − 3 · 2^{3+n} + 8 · 3^{n} + 12n − 9 · 2^{n} · n+

42n^{2} − 3 · 2^{n} · n^{2} − 12n^{3} + 6n^{4}) ,

\left\{{n \atop 4}\right\}_{≥3} = −3^{−2+n}(n^{2} + 5n + 18)+

\frac{1}{64} (2^{2n+5} + 3 · 2^{n}(64 + 42n + 19n^{2} + 2n^{3} + n^{4}) −

16(8 − 32n + 112n^{2} − 91n^{3} + 43n^{4} − 9n^{5} + n^{6})) .

The first identity can be proven by the following combinatorial argument: we separate the n elements into two blocks in 2^{n} ways. The blocks have to contain at least two elements, so we substract the cases when one of the blocks is empty (2 possibilities), contains one element (2n cases), or contains two elements (2\binom{n}{2} cases). The order of the blocks is indifferent so we divide by 2.

The two remaining special values are consequences of (16).

Following the argument we presented above calculating F_{n+20,≥2} − F_{n,≥2}, one can prove Congruence 7 for m = 3.

The rest of the cases (when m = 4, 5) can be treated similarly, however, the calculations are more involved technically.

At the end we note that it is easy to prove the corresponding formula of (10) with respect to the associated Fubini numbers.

F_{n,≥m} = \binom{n}{n}F_{0,≥m} + \binom{n}{n − 1}F_{1,≥m} + ⋯ + \binom{n}{m}F_{n−m,≥m} (n ≥ m).

6 Closing remarks

In the present paper we discussed the modular properties (mostly in base 10) of several combinatorial numbers coming from restricted set partitions and cycle decomposition of permutations. In our case the restriction means that large or small blocks/cycles are not permitted (restricted and associated Stirling numbers, respectively) or the first elements are in different blocks/cycles (r-Stirlings).

6.1 Other bases

It is sure that the proven congruences are not the only ones of this style. For instance, the above used approach can also be applied to prove that the last digits of the Fubini numbers are periodic of length 4 not just in the decimal base but in bases 2, 3, 4, 5, 6, 8 as well:

F_{n+4} ≡ F_{n} (mod 2, 3, 4, 5, 6, 8) (n > 4),

from which Congruence 1 already follows.

What is more, in base 3 we have that

F_{n+3} ≡ F_{n} + \begin{cases}1, & if n is even; \\ 2, & if n is odd. \end{cases}

Such kind of results probably exists for the other sequences of this paper, like the r-Fubini numbers.

Other class of results was proved by Kauffman [23], who revealed periodicity of the Fubini numbers with higher modulus. Namely, she proved that

F_{n+20} ≡ F_{n} (mod 100) (n > 1),
F_{n+100} ≡ F_{n} (mod 1 000) (n > 2),
F_{n+500} ≡ F_{n} (mod 10 000) (n > 3).

These together with the Gross congruence

F_{n+4} ≡ F_{n} (mod 10)

suggest that there might be a minimal period m(k) for every 10^{k}, that is,

F_{n+m(k)} ≡ F_{n} (mod 10^{k})

for some function m. Hence m(1) = 4, m(2) = 20, m(3) = 100 and m(4) = 500. It would be interesting to find the function m in general.

6.2 Possible directions of investigation

In the literature there exist other generalizations of the “unrestricted” partitions and permutations (which are enumerated by the classical Stirling numbers of the first and second kind).

In a recent paper Mihoubi and Maamra [29] defined the (r_{1}, …, r_{p})-Stirling numbers which are extensions of the r-Stirling numbers. One could ask about the periodicity and other modular properties of the (r_{1}, …, r_{p})-Fubini numbers. Up to our knowledge, there is no investigation with respect to these numbers, however, there is a manuscript on (r_{1}, …, r_{p})- Bell numbers by Maamra [25].

Another direction of generalization comes from lattice theory. In 1973 Dowling [16] constructed a class of geometric lattices with fixed underlying finite groups. The Whitney numbers of these lattices are generalizations of the Stirling numbers of both kinds with an additional parameter (which is the order of the underlying group). There are several papers dealing with these numbers [2, 3, 7, 21, 27, 32, 33]. The periodicity of these sequences would be an interesting question to deal with. In particular, one could use the papers of Benoumhani [2, 3] who made some short remarks on the new Fubini numbers derived from Whitney numbers.

A relatively new direction of research is the graph theoretical extension of the Stirling and Bell numbers [17, 19, 24]. It could be an interesting question, how to define Fubini numbers in this setting, because there is no block order. However, if it is possible, one could investigate the modular properties of these numbers, too.

7 Acknowledgement

I am grateful to Professor Miklós Bóna, who posed the initial problem on the parity of associated Fubini numbers. This discussion led to a wide group of results presented in this paper.

I am also grateful to the unknown referee for his/her careful reading.

References

[1] D. Applegate and N. J. A. Sloane, The gift exchange problem, preprint,

    http://arxiv.org/abs/0907.0513.

[2] M. Benoumhani, On Whitney numbers of Dowling lattices, Discrete Math. 159 (1996), 13–33.

[3] M. Benoumhani, On some numbers related to Whitney numbers of Dowling lattices, Adv. Appl. Math. 19 (1997), 106–116.

[4] M. Bóna, Combinatorics of Permutations, Chapman&Hall/CRC, 2004.

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

[6] Ch. A. Charalambides, Combinatorial Methods in Discrete Distributions, John Wiley & Sons, 2005.

[7] G.-S. Cheon and J.-H. Jung, r-Whitney numbers of Dowling lattices, Discrete Math. 312 (2012), 2337–2348.

[8] J. Y. Choi and J. D. H. Smith, On the combinatorics of multi-restricted numbers, Ars Combin. 75 (2005), 45–63.

[9] J. Y. Choi and J. D. H. Smith, Recurrences for tri-restricted numbers, J. Combin. Math. Combin. Comput. 58 (2006), 3–11.

[10] J. Y. Choi, L. Long, S.-H. Ng, and J. Smith, Reciprocity for multirestricted numbers, J. Combin. Theory Ser. A 113 (2006), 1050–1060.

[11] L. Comtet, Advanced Combinatorics, D. Reidel Publishing Company, 1977.

[12] R. B. Corcino and M. Hererra, Some convolution-type identities and congruence relation for F_{α,γ}(n, k), NAST 34th Annual Scientific Meeting.

[13] R. B. Corcino and C. B. Corcino, On generalized Bell polynomials, Discrete Dyn. Nat. Soc. Article ID: 623456 (2011).

[14] C. B. Corcino and R. B. Corcino, An asymptotic formula for r-Bell numbers with real arguments, ISRN Discrete Math. 2013 (2013), Article ID 274697.

[15] A. Dil and V. Kurt, Polynomials related to harmonic numbers and evaluation of harmonic number series II, Appl. Anal. Discrete Math. 5 (2011), 212–229.

[16] T. A. Dowling, A class of geometric lattices based on finite groups, J. Combin. Theory Ser. B 14 (1973), 61–86. Erratum: 15 (1973), 211.

[17] B. Duncan and R. Peele, Bell and Stirling numbers for graphs, J. Integer Seq. 12 (2009), Article 09.7.1.

[18] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009.

[19] D. Galvin and D. T. Thanh, Stirling numbers of forests and cycles, Electron J. Combin. 20 (2013), Paper 73.

[20] O. A. Gross, Preferential arrangements, Amer. Math. Monthly 69 (1962), 4–8.

[21] P. Hanlon, The generalized Dowling lattices, Trans. Amer. Math. Soc. 325 (1991), 1–37.

[22] R. D. James, The factors of a square-free integer, Canad. Math. Bull. 11 (1968), 733– 735.

[23] D. H. Kauffman, Note on preferential arrangements, Amer. Math. Monthly. 70 (1963), 62.

[24] Zs. Kereskényi-Balogh and G. Nyul, Stirling numbers of the second kind and Bell numbers for graphs, submitted.

[25] M. S. Maamra and M. Mihoubi, The (r_{1}, …, r_{p})-Bell numbers, preprint,

    http://arxiv.org/abs/1212.3191v1.

[26] I. Mező, The r-Bell numbers, J. Integer Seq. 14 (2011), Article 11.1.1.

[27] I. Mező, A new formula for the Bernoulli polynomials, Result. Math. 58 (2010), 329–335.

[28] I. Mező and G. Nyul, The r-Fubini numbers and r-Eulerian numbers, manuscript.

[29] M. Mihoubi and M. S. Maamra, The (r_{1}, …, r_{p})-Stirling numbers of the second kind, Integers 12 (2012), #A35.

[30] F. L. Miksa, L. Moser, and M. Wyman, Restricted partitions of finite sets, Canad. Math. Bull. 1 (1958) 87–96.

[31] H. Prodinger, Ordered Fibonacci partitions, Canad. Math. Bull. 26 (1983), 312–316.

[32] M. Rahmani, Some results on Whitney numbers of Dowling lattices, Arab J. Math. Sci., to appear.

[33] J. B. Remmel and M. Wachs, Rook theory, generalized Stirling numbers and (p, q)- analogues, Electron. J. Comb. 11 (2004), #R84.

[34] S. M. Tanny, On some numbers related to the Bell numbers, Canad. Math. Bull. 17 (1975), 733–738.

[35] D. J. Velleman and G. S. Call, Permutations and combination locks, Math. Mag. 68 (1995), 243–253.

2010 Mathematics Subject Classification: Primary 05A18; Secondary 11B73. Keywords: Stirling number, r-Stirling number, restricted Stirling number, associated restricted Stirling number, restricted partition, Fubini number, restricted Bell number, restricted factorial, associated Fubini number.

(Concerned with sequences \underline{A000085}, \underline{A000296}, \underline{A000670}, \underline{A001680}, \underline{A001681}, \underline{A006505}, \underline{A032032}, \underline{A057693}, \underline{A057837}, \underline{A070945}, and \underline{A102233}.)

Received August 21 2013; revised version received December 4 2013. Published in Journal of Integer Sequences, December 5 2013.

Return to Journal of Integer Sequences home page.