Abstract
We derive new congruences bounding r-Bell and derangement polynomials, which generalize the existing ones, while the presented approach is significantly simpler and, at the same time, more informative. Namely, we provide precise identities that imply the congruences and explain somehow their nature.
We’re sorry, something doesn't seem to be working properly.
Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.
Avoid common mistakes on your manuscript.
1 Introduction
The Bell numbers \(B_n\) represent number of partitions of a given set of n elements and are one of the most classical objects in combinatorics. The r-Bell numbers \(B_{n,r}\) extend this definition and count partitions of a set of \(n+r\) elements such that r chosen elements are separated [13]. They appear also naturally when dealing with congruences of classical Bell numbers, which will be shown in the sequel. If we restrict the partitions to consist of exactly \(k+r\) sets, their number is given by the r-Stirling numbers of the second kind \(\left\{ \begin{array}{c} n \\ k \end{array}\right\} _{r}\) (see [2,3,4]), which lets us write \(B_{n,r}=\sum _{k=0}^n\left\{ \begin{array}{c} n \\ k \end{array}\right\} _{r}\). The framework of this paper is slightly more general. Precisely, we focus on the r-Bell polynomials given by
Clearly, we have \(B_{n,r}(1)=B_{n,r}\). Furthermore, for \(r=0\) we obtain the Bell polynomials, known also as Touchard or exponential polynomials. Some of the most intensively studied features of these polynomials are their divisibility properties (see, among others, [7, 8, 10, 12, 15, 19,20,21,22]). The goal of the paper is to find precise identities that directly lead to some known as well as some new congruences. This method is not only more constructive and informative, but also, at least in this case, turns out to be significantly shorter.
The history of research on congruences for Bell number is very long and goes back to 1933 and the famous Touchard congruence [21]
valid for any natural n and prime p. More recently, Sun and Zagier [19] showed that
where \(\mathbb {Z}_p\) denotes the ring of p-adic integers and \(D_n(x)\) is the derangement polynomial defined by
In particular, \(D_n(0)=D_n\) is the n-th derangement number. The especially interesting property of (1) is that besides the term \(x^p\) the right-hand side does not depend on p, which had been earlier conjectured by the first author of [19] in the case \(x=1\). Later on, this result has been generalized in several directions. In [20] and [15] the authors considered \(B_{n+k}\) and \(B_{k,r}\), respectively, instead of \(B_k\) on the left-hand side of the congruence, while in [18] the sum in (1) is considered up to \(p^a-1\), where a is any positive integer. In this paper, we unify all those results by providing the following equivalence (see Theorem 2)
In particular, for \(x=1\) we obtain
As a by-product we prove also another interesting congruences (see Theorem 1):
where \(r\ge 1\). The first one holds for \(r=0\) as well and this special case has been already known for \(a=1\) [19].
Nevertheless, we would like to turn the Reader’s attention to the methods employed. Precisely, we derive exact identities that immediately imply the congruences. This brings in much more information and explains somehow the nature of the congruences. Furthermore, such approach is very effective which makes the proofs surprisingly short and easily accessible. Note also that a similar conception has already appeared in [16], where the author recovered (1) for \(x=1\). In order to explain the basic idea let us observe that by the simple congruence \({p-1\atopwithdelims ()k} \equiv (-1)^k\ (\text{ mod } p)\), valid for any prime p and any integer \(0\le k \le p-1\), and by Fermat’s little theorem, the sum on the left-hand side of (1) for \(a=1\) is equivalent to
Then, it is enough to focus on the polynomials \(B_{p-1,m}(x)\). In fact, we find their representation by means of derangement polynomials for p being not only a prime number. Additionally, this relation is a motivation to study the r-Bell polynomials even if one is interested only in classical Bell polynomials.
2 Preliminaries
2.1 r-Bell polynomials
We define the r-Stirling number of the second kind \(\left\{ \begin{array}{c} n \\ k \end{array}\right\} _r\) as the number of partitions of the set \(\{ 1, 2, \ldots , n+r\}\) into \(k+r\) non-empty disjoint subsets, such that the numbers \(1, 2 ,\ldots , r\) are in distinct subsets. They were introduced and described in details by A. Z. Broder in [2] (see also [3, 4]). Another way to define them is the expansion
where \(x^{\underline{k}}=x(x-1)\cdot ...\cdot (x-k+1)\) is the falling factorial. In fact, following the notation from [2] we should write \(\left\{ \begin{array}{c} n+r \\ k+r \end{array}\right\} _r\) instead of \(\left\{ \begin{array}{c} n \\ k \end{array}\right\} _r\), but this seems more complicated and incompatible with other notation as, for example, the notation of r-Bell numbers. The convention we propose has already appeared in [15], and an analogous one was used in [3, 4]. The r-Stirling numbers satisfy the recurrence
and are expressed by the elementary sum
The r-Bell polynomial \(B_{n,r}(x)\) is given by
Its exponential generating function takes the form
Thus, we have \(B_{n,r}(x)=\frac{d^n}{dt^n}\mathcal B_r(t,x)\Big |_{t=0}\) and the general Leibniz rule gives us
Using the recurrence for r-Stirling numbers one can easily verify that
Consequently, calculating the n-th derivative of both sides at \(t=0\), we get
See [3] eq. (3.22–3.23) for the case \(x=0\). Applying additionally the formula (3), we arrive at so called Spivey formula for r-Bell polynomials. This simple proof seems to be new, even in the classical case \(r=0\) (cf. [1, 9, 11, 14, 17, 23]).
2.2 Derangement polynomials
Derangement polynomials \(D_n(x)\), \(n\ge 0\), also called x-factorials of n (see [6] for some details), are defined by the formula
For \(x=0\) they reduce to the standard derangement numbers \(D_n=D_n(0)\). From the definition and by the binomial inverse we get
The following recurrence relation holds
from which one may conclude the formula for exponential generating function:
3 Results
It is known that for any natural numbers n, m we have \(D_{n+m}(x)\equiv (x-1)^mD_n(x)\ (\text{ mod }\ n)\). Below, we present precise recurrence formula that directly implies this congruence.
Proposition 1
For \(m,n\ge 0\) we have
Proof
Using the exponential generating function (6) of derangement polynomials we may write
Considering the term corresponding to \(k=0\) separately, we get
as required. \(\square \)
In the next proposition we provide a representation of r-Bell polynomials by means of derangement polynomials. Despite of its simple form, the author has not found it in the literature. See (9) in [5] for a similar equivalence, which is additionally restricted to \(x=1\),
Proposition 2
For any \(n,\ge 0\) we have
Proof
From (2) we have
\(\square \)
We will see that this identity immediately yields congruence relations between r-Bell and derangement polynomials. First, let us note that it was shown in [19] (formally, it was done only for \(x=1\), but justification works for any \(x\in \mathbb {R}\)) that (1) follows
We extend this congruence into r-Bell polynomials, while considering \(p^a\) instead of p in the indices. In particular, taking \(r=0\) and \(a=1\), it gives a new, straightforward proof of (7).
Theorem 1
For any prime p and non-negative intigers \(a,r\ge 0\) we have
If, additionally, \(r\ge 1\), it holds
Proof
It is enough to prove the first congruence, as the other one follows by Proposition 1.
We start with considering the case \(a=1\). Due to (3) and Proposition 1 we may narrow our attention to \(0\le r\le p-1\). From Wilson’s theorem, Proposition 2 and Fermat’s little theorem we have
For \(r=0\), the excluded index in the last sum is \(i=0\), while for \(r\ge 1\) it is \(i=p-r\). Hence, by (5) and Proposition 1 we get for \(r\ge 1\)
as required. For \(r=0\) we proceed analogously, or just refer to (7).
What has left is to extend the result into all \(a\ge 0\). For this purpose, we employ the congruence ([15], Theorem 5)
where \(n,m\ge 0\). Namely, applying it several times, and using the equality \(B_{0,r}(x)=1\), we get
which ends the proof. \(\square \)
Fixing \(x=1\) in the above theorem, we obtain the following congruences bonding r-Bell and derangement numbers
Corollary 1
For any prime p and \(a,r\ge 0\) we have
If, additionally, \(r\ge 1\), it holds
Now we will give a simple argument recovering and generalizing Theorem 6 from [15], Theorem 1.1 from [18] and, as a special case, the congruence (1). First, let us rewrite (3) into the form
where we just separated the term for \(k=0\). Since \({p^a-1 \atopwithdelims ()k}\equiv (-1)^k\) and \(m^{p^a-1}\equiv 1\) \((\text{ mod }\ p)\) for \(0\le k \le p-1 \) and \(p\not \mid m\), see Lemma 2.1 in [18] and the Fermat–Euler theorem, respectively, and using the latter congruence form Theorem 1, we obtain
Corollary 2
For any integers \(a,m\ge 1\) and any prime number \(p\not \mid m\), we have
where \(\mathbb {Z}_p\) denotes the ring of p-adic integers.
As a final step, we will generalize the above congruence by replacing \(B_{k,r}\) with \(B_{n+k,r}\) for a natural number n. Precisely, by virtue of (4), we get
and consequently
One can identify the inner sum as the one from Corollary 2, which leads to
Theorem 2
For any integers \(a, m\ge 1\), \(n\ge 0\) and any prime number \(p\not \mid m\), we have
where \(\mathbb {Z}_p\) denotes the ring of p-adic integers.
Note that taking \(r=0, a=1\) or \(n=0,a=1\) we recover the main result of [20] and Theorem 6 from [15], respectively. On the other hand, for \(n=r=0\), we obtain the main result of [18].
For \(x=1\) the above-given theorem reduces to
Corollary 3
For any integers \(a,m\ge 1\), \(n\ge 0\) and any prime number \(p\not \mid m\), we have
Change history
19 October 2020
In the original article there were capitalization errors in two of the references. The corrected references follow:
References
Belbachir, H., Mihoubi, M.: A generalized recurrence for Bell polynomials: an alternate approach to Spivey and Gould-Quaintance formulas. Eur. J. Comb. 30(5), 1254–1256 (2009)
Broder, A.Z.: The \(r\)-Stirling numbers. Discret. Math. 49(3), 241–259 (1984)
Carlitz, L.: Weighted Stirling numbers of the first and second kind I. Fibonacci Q. 18(2), 147–162 (1980)
Carlitz, L.: Weighted Stirling numbers of the first and second kind II. Fibonacci Q. 18(3), 242–257 (1980)
Clarke, R.J., Sved, M.: Derangements and Bell numbers. Math. Mag. 66(5), 299–303 (1993)
Eriksen, N., Freij, R., Wästlund, J.: Enumeration of derangements with descents in prescribed positions. Electron. J. Comb. 16(1), Research Paper 32, 19 (2009)
Gertsch, A., Robert, A.M.: Some congruences concerning the Bell numbers. Bull. Belg. Math. Soc. Simon Stevin 3(4), 467–475 (1996)
Gessel, I.: Congruences for Bell and tangent numbers. Fibonacci Q. 19(2), 137–144 (1981)
Gould, H.W., Quaintance, J.: Implications of Spivey’s Bell number formula. J. Integer Seq. 11(3), 7 (2008)
Kahale, N.: New modular properties of Bell numbers. J. Comb. Theory Ser. A 58(1), 147–152 (1991)
Katriel, J.: On a generalized recurrence for Bell numbers. J. Integer Seq. 11(3), 4 (2008)
Lunnon, W.F., Pleasants, P.A.B., Stephens, N.M.: Arithmetic properties of Bell numbers to a composite modulus I. Acta Arith. 35(1), 1–16 (1979)
Mező, I.: The \(r\)-Bell numbers. J. Integer Seq. 14(1), 14 (2011)
Mező, I.: The dual of Spivey’s Bell number formula. J. Integer Seq. 15(2), 5 (2012)
Mező, I., Ramírez, J.L.: Divisibility properties of the \(r\)-Bell numbers and polynomials. J. Number Theory 177, 136–152 (2017)
Mu, Q.: A new proof of the sun-zagier congruence. Nanjing Univ. J. Math. Biquarterly 35(1), 39–43 (2018)
Spivey, M.Z.: A generalized recurrence for Bell numbers. J. Integer Seq. 11(2), 3 (2008)
Sun, Z.W.: A new extension of the sun-zagier result involving bell numbers and derangement numbers. arxiv:2006.16089 (2020)
Sun, Z.W., Zagier, D.: On a curious property of Bell numbers. Bull. Aust. Math. Soc. 84(1), 153–158 (2011)
Sun, Y., Wu, X., Zhuang, J.: Congruences on the Bell polynomials and the derangement polynomials. J. Number Theory 133(5), 1564–1571 (2013)
Touchard, J.: Propriétés arithmétiques de certains nombres récurrents. Ann. Sot. Sci. Bruxelles Ser. A 53, 21–31 (1933)
Tsumura, H.: On some congruences for the Bell numbers and for the Stirling numbers. J. Number Theory 38(2), 206–211 (1991)
Xu, A.: Extensions of Spivey’s Bell number formula. Electron. J. Comb. 19(2), 8 (2012)
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Acknowledgements
The author would like to thank the anonymous reviewer for turning attention to the article [18], which resulted in substantial enhancement of the results in the paper.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The author was supported by the National Science Centre Grant No. 2015/18/E/ST1/00239.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Serafin, G. Identities behind some congruences for r-Bell and derangement polynomials. Res. number theory 6, 39 (2020). https://doi.org/10.1007/s40993-020-00216-y
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s40993-020-00216-y