For any integers $n\geq k\geq 0$, let $S(n, k)$ denote the number of partitions of a set with $n$ elements into $k$ nonempty blocks. It is clear that $S(n, k)>0$ for all $1\leq k\leq n$, and $S(n, k)=0$ for $1\leq n< k$. Put $S(0, 0)=1$ and $S(0, k)=0$ for $k\geq 1$, $S(n, 0)=0$ for $n\geq 1$. These numbers were introduced by Stirling in his book "Methodus Differentialis" (see [3-5]). Now they are called as the Stirling numbers of the second kind. These numbers satisfy the recurrence relation

$ S(n, k)=S(n-1, k-1)+kS(n-1, k) \ (n, k\geq 1). $

The number of all partitions of a set with $n$ elements is

$ B(n)= \sum\limits_{k=1}^nS(n, k), $

called also a Bell number (or exponential number), related contents can be found in many papers or books. For example, see [6-8].

These numbers satisfy the recurrence formula

$ \begin{eqnarray} B(n+1)= \sum\limits_{k=0}^{n} \binom{n}{k}B(k), \end{eqnarray} $

(1.1)

where $B(0)=1$ by definition.

The generating function of $B(n)$ is given by

$ \begin{eqnarray} \sum\limits_{n=0}^{\infty} \frac{B(n)}{n!}\cdot t^n= \exp\left(e^t-1\right), \end{eqnarray} $

(1.2)

where $\exp(y)=e^y$.

The numbers $B(n)$ can be represented also as the sum of a convergent series (Dobinski's formula)

$ \begin{eqnarray} B(n)= \frac{1}{e}\sum\limits_{k=0}^{\infty}\frac{k^n}{k!}= \frac{1}{e}\left(\frac{1^n}{1!}+ \frac{2^n}{2!} +\frac{3^n}{3!}+ \cdots\right), \end{eqnarray} $

(1.3)

see Pólya and Szegö [9] for these basic properties.

In this paper, we introduce a new polynomials $B(x, n)$ (called Bell polynomials) as follows

$ \begin{eqnarray} \exp\left(x(e^t-1)\right)=\sum\limits_{n=0}^{\infty} \frac{B(n, x)}{n!}\cdot t^n. \end{eqnarray} $

(1.4)

It is clear that $B(0, x)=1$, $B(1, x)=x$, $B(2, x)=x+x^2$, $B(3, x)=x+3x^2+x^3, \cdots$. If $x=1$, then $B(n, 1)= B(n)$, the well known Bell numbers. About the properties of $B(n, x)$, it seems that none had studied it yet, at least we have not seen any related papers before. The problem is interesting, because it can help us to further understand the properties of Bell numbers.

The main purpose of this paper is using the elementary and combinational methods to study the computational problem of the sums

$ \begin{eqnarray} \sum\limits_{a_1+a_2+\cdots +a_k=n}\frac{B(a_1, x)}{a_1!}\cdot \frac{B(a_2, x)}{a_2!}\cdots \frac{B(a_k, x)}{a_k!}, \end{eqnarray} $

(1.5)

where $\displaystyle\sum_{a_1+a_2+\cdots +a_k=n}$ denotes the summation over all $k$-tuples with non-negative integer coordinates $(a_1, a_2, \cdots, a_k)$ such that $a_1+a_2+\cdots +a_k=n$, and give an exact computational formula for (1.5). That is, we shall prove the following.

Theorem 1  Let $k$ be a positive integer with $k\geq 1$. Then for any positive integer $n\geq 1$, we have the identity

$ \begin{eqnarray*} \sum\limits_{a_1+a_2+\cdots +a_k=n}\frac{B(a_1, x)}{a_1!}\cdot \frac{B(a_2, x)}{a_2!}\cdots \frac{B(a_k, x)}{a_k!}=\frac{ B(n, kx)}{n!}, \end{eqnarray*} $

where the polynomials $B(n, x)$ satisfy the recurrence formula $B(0, x)=1$, $B(1, x)=x$, $B(2, x)= x+x^2$, $B(3, x)=x+3x^2+x^3$, and

$ B(n+1, x)=\displaystyle x\cdot \sum\limits_{i=0}^n\binom{n}{i}\cdot B(i, x)\ \ {\rm{for}\; \text{all}} \; \; {n\geq 1}. $

For the polynomials $B(n, x)$, we also have a similar Dobinski's formula.

Theorem 2  For any positive integer $n\geq 1$, we have the identities

$ \begin{eqnarray*} B(n, x)= \frac{1}{e^x}\sum\limits_{m=0}^{\infty}\frac{x^m\cdot m^n}{m!}= \frac{1}{e^x}\left(\frac{x^1\cdot1^n}{1!}+ \frac{x^2\cdot 2^n}{2!} +\frac{x^3\cdot3^n}{3!}+ \cdots\right). \end{eqnarray*} $

From Theorem 1 and the recurrence formula of $B(n, x), $ we may immediately deduce the following congruence.

Corollary 1  Let $p$ be an odd prime. Then for any positive integer $k\geq 1$ with $(k, p)=1$, we have the congruence

$ k\cdot B(p, x)\equiv B(p, kx)\bmod p \ \ {\rm{and}}\ \ B'(p, x)\equiv 1\bmod p $

Corollary 2  For any positive integer $n$, we have the identity

$ B(n+1, x)= x\cdot\left(B'(n, x)+B(n, x)\right) \ \ {\rm{or}}\ \ \displaystyle B'(n, x)=\sum\limits_{i=0}^{n-1}\binom{n}{i}\cdot B(i, x), $

where $B'(n, x)= \frac{\partial B(n, x)}{\partial x}$.

In this section, we shall complete the proofs of our theorems. First we give a sample lemma, which are necessary in the proof of our theorems. Hereinafter, we shall use some elementary number theory contents and properties of power series, all of these can be found in references [1] and [2], so they will not be repeated here.

Lemma  For any real number $x$, let function $f(t)=\exp\left(x(e^t-1)\right)$, then we have $f^{(n)}(0)=B(n, x)$ for all integers $n\geq 0$, where $f^{(n)}(t)$ denotes the $n^{th}$ derivative of $f(t)$ for variable $t$.

Proof  We prove this lemma by complete induction. It is clear that $f(0)=1=B(0, x)$, $f'(t)=xe^t\cdot \exp\left(x(e^t-1)\right)=xe^t\cdot f(t)$, and $f'(0)=x=B(1, x)$. So the lemma is true for $n=0, 1$. Assume that $f^{(n)}(0)=B(n, x)$ for all $0\leq n\leq r$. Then note that $f'(t)=xe^t\cdot f(t)$, so from the properties of derivative (Newton-Leibnitz formula), we have

$ \begin{eqnarray} f^{(r+1)}(t)&=& \left(xe^t\cdot f(t)\right)^{r}= x\cdot \sum\limits_{i=0}^r\binom{r}{i}\cdot \left(e^t\right)^{(r-i)}\cdot f^{(i)}(t) \nonumber\\ &=& x\cdot \sum\limits_{i=0}^r\binom{r}{i}\cdot e^t\cdot f^{(i)}(t). \end{eqnarray} $

(2.1)

Applying (2.1) and inductive hypothesis, we have

$ \begin{eqnarray*} f^{(r+1)}(0)= x\cdot \sum\limits_{i=0}^r\binom{r}{i}\cdot f^{(i)}(0)=x\cdot \sum\limits_{i=0}^r\binom{r}{i}\cdot B(i, x)= B(r+1, x). \end{eqnarray*} $

That is, $f^{(r+1)}(0)=B(r+1, x)$.

Now the lemma follows from the complete induction.

Proof of Theorem 1  For any positive integer $k\geq 2$, it is clear that $f^k(t)=\exp\left(kx(e^t-1)\right)$, then from (1.4), we have

$ \begin{eqnarray} f^k(t)&=& \left(\exp\left(x(e^t-1)\right)\right)^k=\left(\sum\limits_{n=0}^{\infty} \frac{B(n, x)}{n!}\cdot t^n\right)^k\nonumber\\ &=&\sum\limits_{n=0}^{\infty}\left(\sum\limits_{a_1+a_2+\cdots +a_k=n}\frac{B(a_1, x)}{a_1!}\cdot \frac{B(a_2, x)}{a_2!}\cdots \frac{B(a_k, x)}{a_k!}\right)\cdot t^n. \end{eqnarray} $

(2.2)

On the other hand, let $g(t)=f^k(t)=\exp(kx(e^t-1))$, then from the definition of the power series and lemma, we also have

$ \begin{eqnarray} f^k(t)&=&g(t)=\sum\limits_{n=0}^{\infty}\frac{g^{(n)}(0)}{n!}\cdot t^n=\sum\limits_{n=0}^{\infty}\frac{B(n, kx)}{n!}\cdot t^n. \end{eqnarray} $

(2.3)

Combining (2.2) and (2.3) we may immediately deduce the identity

$ \begin{eqnarray*} \sum\limits_{a_1+a_2+\cdots +a_k=n}\frac{B(a_1, x)}{a_1!}\cdot \frac{B(a_2, x)}{a_2!}\cdots \frac{B(a_k, x)}{a_k!}=\frac{ B(n, kx)}{n!}. \end{eqnarray*} $

This proves Theorem 1.

Proof of Theorem 2  Applying the power series $ e^y= \sum\limits_{n=0}^{\infty}\frac{1}{n!}\cdot y^n, $ we have

$ \begin{eqnarray} f(t)&=&\frac{1}{e^x} \exp\left(xe^t\right)= \frac{1}{e^x}\cdot \sum\limits_{m=0}^{\infty}\frac{x^m}{m!}\cdot e^{mt}=\frac{1}{e^x}\cdot \sum\limits_{m=0}^{\infty}\frac{x^m}{m!}\cdot \left(\sum\limits_{n=0}^{\infty}\frac{m^n}{n!}\cdot t^n\right)\nonumber\\ &=&\frac{1}{e^x}\cdot\sum\limits_{n=0}^{\infty}\frac{1}{n!}\left(\sum\limits_{m=0}^{\infty}\frac{x^m\cdot m^n}{m!} \right)\cdot t^n. \end{eqnarray} $

(2.4)

Comparing the coefficients of $t^n$ in (1.4) and (2.4), we may immediately deduce the identity

$ B(n, x)=\frac{1}{e^x}\sum\limits_{m=0}^{\infty}\frac{x^m\cdot m^n}{m!}= \frac{1}{e^x}\left(\frac{x^1\cdot1^n}{1!}+ \frac{x^2\cdot 2^n}{2!} +\frac{x^3\cdot3^n}{3!}+ \cdots\right). $

This proves Theorem 2.

Proof of Corollary 1  Let $p$ be an odd prime, take $n=p+1$ in Theorem 1, then from the properties of $B(n, x)$ and Theorem 1, we have

$ \begin{eqnarray*} \sum\limits_{a_1+a_2+\cdots +a_k=p+1}\frac{B(a_1, x)}{a_1!}\cdot \frac{B(a_2, x)}{a_2!}\cdots \frac{B(a_k, x)}{a_k!}=\frac{ B(p+1, kx)}{(p+1)!} \end{eqnarray*} $

or

$ (p+1)!\sum\limits_{a_1+a_2+\cdots +a_k=p+1}\frac{B(a_1, x)}{a_1!}\cdot \frac{B(a_2, x)}{a_2!}\cdots \frac{B(a_k, x)}{a_k!} =\\ kx\cdot \sum\limits_{i=0}^p\binom{p}{i}\cdot B(i, kx). $

(2.5)

It is clear that $\binom{p}{i}\equiv 0\bmod p$ for all $1\leq i\leq p$. So we have

$ kx\cdot \sum\limits_{i=0}^p\binom{p}{i}\cdot B(i, kx)\\ \equiv kx B(0, kx)+ kx B(p, kx)\equiv kx+ kx B(p, kx)\bmod p. $

(2.6)

Note that $k\geq 2$ and $a_1+a_2+\cdots +a_k=p+1$, so if there are three of $a_1$, $a_2$, $\cdots$, $a_k$ are positive integers, then

$ \begin{eqnarray} \frac{(p+1)!}{a_1!\cdot a_2!\cdots a_k!}\equiv 0 \bmod p. \end{eqnarray} $

(2.7)

If there are only two of $a_1$, $a_2$, $\cdots$, $a_k$ are positive integers, and both of them are greater than one, then we also have

$ \begin{eqnarray} \frac{(p+1)!}{a_1!\cdot a_2!\cdots a_k!}\equiv 0 \bmod p. \end{eqnarray} $

(2.8)

If there are only two of $a_1$, $a_2$, $\cdots$, $a_k$ are positive integers, and one is $p$, another is $1$, then we also have

$ \begin{eqnarray} \frac{(p+1)!}{a_1!\cdot a_2!\cdots a_k!}\equiv 1 \bmod p. \end{eqnarray} $

(2.9)

If only one of $a_1$, $a_2$, $\cdots$, $a_k$ are positive integers, then it must be $p+1$. This time we have

$ \begin{eqnarray} \frac{(p+1)!}{a_1!\cdot a_2!\cdots a_k!}\equiv 1 \bmod p. \end{eqnarray} $

(2.10)

Combining (2.5)-(2.10) and note that identity

$ B(n+1, x)=\displaystyle x\cdot \sum\limits_{i=0}^n\binom{n}{i}\cdot B(i, x)\ \ {\rm{for~~ all}}\ \ n\geq 1, $

we have

$ k\cdot B(p+1, x) + 2\binom{k}{2}\frac{(p+1)!}{p!}\cdot B(1, x)\cdot B(p, x)\equiv kx+ kx B(p, kx)\bmod p $

or

$ k\cdot B(p, x)\equiv B(p, kx)\bmod p. $

This proves the first congruence of Corollary 1. The second congruence follows from the second identity of Corollary 2 with $n=p$.

Proof of Corollary 2  Let $f(t, x)=\exp\left(x(e^t-1)\right)$, then from (1.4), we have

$ \begin{eqnarray} (e^t-1)f(t, x)= \frac{\partial f(t, x)}{\partial x}= \sum\limits_{n=0}^{\infty}\frac{B'(n, x)}{n!}\cdot t^n. \end{eqnarray} $

(2.11)

On the other hand, from the definition of $f(t, x), $ we also have

$ \begin{eqnarray} &&(e^t-1)f(t, x)=e^tf(t, x)-f(t, x)= \frac{1}{x}\frac{\partial f(t, x)}{\partial t} -f(t, x)\nonumber\\ &=& \frac{1}{x}\sum\limits_{n=0}^{\infty} \frac{B(n+1, x)}{n!} \cdot t^n- \sum\limits_{n=0}^{\infty}\frac{B(n, x)}{n!}\cdot t^n. \end{eqnarray} $

(2.12)

Comparing the coefficients of $t^n$ in (2.11) and (2.12), we may immediately deduce the identity

$ \begin{eqnarray} B(n+1, x)=x\cdot\left(B'(n, x)+ B(n, x)\right). \end{eqnarray} $

(2.13)

Note that the recurrence formula $ B(n+1, x)=\displaystyle x\cdot \sum_{i=0}^n\binom{n}{i}\cdot B(i, x), $ from (2.13) we may immediately deduce the identity $ B'(n, x)=\sum\limits_{i=0}^{n-1}\binom{n}{i}\cdot B(i, x). $ This completes the proofs of our all results.