Computer Modeling in Engineering & Sciences

DOI: 10.32604/cmes.2022.019941

ARTICLE

Partial Bell Polynomials, Falling and Rising Factorials, Stirling Numbers, and Combinatorial Identities

Siqintuya Jin1, Bai-Ni Guo2,* and Qi Feng3,*

1College of Mathematics and Physics, Inner Mongolia Minzu University, Tongliao, 028043, China
2School of Mathematics and Informatics, Henan Polytechnic University, Jiaozuo, 454010, China
3School of Mathematical Sciences, Tiangong University, Tianjin, 300387, China
*Corresponding Authors: Bai-Ni Guo. Email: bai.ni.guo@gmail.com; Feng Qi. Email: qifeng618@gmail.com
Received: 25 October 2021; Accepted: 24 January 2022

1  Preliminaries

In this paper, we use the notation

ℕ={1,2,…},   ℕ−={−1,−2,…}, ℕ0={0,1,2,…},ℤ={0,±1,±2,…},  ℝ=(−∞,∞),   ℂ={x+iy:x,y∈ℝ,i=−1}.

The partial Bell polynomials, also known as the Bell polynomials of the second kind, in combinatorics can be denoted and defined by

𝐁n,k(x1,x2,…,xn−k+1)=∑1≤i≤n−k+1,ℓi∈{0}∪N,∑i=1n−k+1iℓi=n,∑i=1n−k+1ℓi=kn!∏i=1n−k+1ℓi!∏i=1n−k+1(xii!)ℓi(1)

for n≥k∈N0. See TheoremA on page 134 in [1]. The partial Bell polynomials satisfy the identity

𝐁n,k(abx1,ab2x2,…,abn−k+1xn−k+1)=akbn𝐁n,k(x1,x2,…,xn−k+1)(2)

for n≥k∈N0. See page 135 in [1].

The double factorial of negative odd integers −(2k+1) is defined by

(−2k−1)!!=(−1)k(2k−1)!!=(−1)k2kk!(2k)!,k∈N0.

The falling factorial ⟨z⟩n and the rising factorial (z)n for n∈N0 and z∈C can be defined by

⟨z⟩n=∏k=0n−1(z−k)={z(z−1)⋯(z−n+1),n∈N1,n=0(3)

and

(z)n=∏ℓ=0n−1(z+ℓ)={z(z+1)⋯(z+n−1),n∈N1,n=0

respectively. It is easy to verify that

(−z)n=(−1)n⟨z⟩n(4)

and

⟨−z⟩n=(−1)n(z)n.(5)

See page 167 in [2] and related texts in the paper [3].

The Stirling numbers of the first kind s(n, k) for n≥k∈N0 can be analytically generated (see page 51 in [1]) by

[ln⁡(1+x)]kk!=∑n=k∞s(n,k)xnn!,|x|<1

and can be explicitly computed (see Corollary 2.3 in [4]) by

|s(n+1,k+1)|=n!∑ℓ1=kn1ℓ1∑ℓ2=k−1ℓ1−11ℓ2⋯∑ℓk−1=2ℓk−2−11ℓk−1∑ℓk=1ℓk−1−11ℓk

for n≥k∈N. The Stirling numbers of the second kind S(n, k) for n≥k∈N0 can be analytically generated (see page 51 in [1]) by

(ex−1)kk!=∑n=k∞S(n,k)xnn!

and can be explicitly computed (see TheoremA on page 204 in [1]) by

S(n,k)={(−1)kk!∑ℓ=0k(−1)ℓ(kℓ)ℓn,n>k∈N0;1,n=k∈N0.(6)

For more information on the Stirling numbers of the first and second kinds s(n, k) and S(n, k), please refer to the papers [5,6] and the monographs [7,8].

The extended binomial coefficient (zw) for z,w∈C is defined in [9] by

(zw)={Γ(z+1)Γ(w+1)Γ(z−w+1),z∉N−,w,z−w∉N−0,z∉N−,w∈N− or z−w∈N−⟨z⟩ww!,z∈N−,w∈N0⟨z⟩z−w(z−w)!,z,w∈N−,z−w∈N00,z,w∈N−,z−w∈N−∞,z∈N−,w∉Z

in terms of the falling factorial ⟨z⟩w, which is defined by (3), and the classical Euler’s gamma function Γ(z), which can be defined (see Chapter3 in [10]) by

Γ(z)=limn→∞n!nz∏k=0n(z+k),z∈C∖{0,−1,−2,…}.

On page 206 in [1] and on page 165 in [7], there are two relations

⟨z⟩n=∑ℓ=0ns(n,ℓ)zℓ,z∈C,n∈N0(7)

and

n!(zn)=∑ℓ=0ns(n,ℓ)zℓ,n∈N0,z∈C.(8)

The falling factorial ⟨z⟩n and the rising factorial (z)n can be represented by

⟨z⟩n=n!(zn)=Γ(z+1)Γ(z−n+1)and(z)n=(−1)nn!(−zn)=Γ(z+n)Γ(z)

for z∈C and n∈N0.

In this paper, we will collect, discuss, and find out several connections, equivalences, closed-form formulas, and combinatorial identities concerning partial Bell polynomials 𝐁n,k, falling factorials ⟨z⟩n, rising factorials (z)n, extended binomial coefficients (zw), and the Stirling numbers of the first and second kinds s(n, k) and S(n, k).

2  Equivalences

Among the Stirling numbers of the first and second kinds s(n, k) and S(n, k), the falling factorial ⟨αℓ⟩n, and extended binomial coefficient (αℓn), there are the following beautiful equivalences.

Theorem 2.1. For n≥k∈N0 and α∈C, we have

∑ℓ=kns(n,ℓ)αℓS(ℓ,k)=(−1)kk!∑ℓ=0k(−1)ℓ(kℓ)⟨αℓ⟩n(9)

and

∑ℓ=kns(n,ℓ)αℓS(ℓ,k)=(−1)kn!k!∑ℓ=0k(−1)ℓ(kℓ)(αℓn).(10)

Proof. In Remark 3.1 of [11], the formula

𝐁n,k(1,1−λ,(1−λ)(1−2λ),…,∏ℓ=0n−k(1−ℓλ))=(−1)kk!∑ℓ=0k(−1)ℓ(kℓ)∏q=0n−1(ℓ−qλ)(11)

for n≥k∈N0 and λ∈C was concluded. An equivalence of the formula (11) is

𝐁n,k(⟨α⟩1,⟨α⟩2,…,⟨α⟩n−k+1)=(−1)kk!∑ℓ=0k(−1)ℓ(kℓ)⟨αℓ⟩n(12)

for n≥k∈N0 and α∈C, which was proved in Theorems 2.1 and 4.1 of [2].

The formulas (11) and (12) can be rewritten respectively as

𝐁n,k(1,1−λ,(1−λ)(1−2λ),…,∏ℓ=0n−k(1−ℓλ))={(−1)kλnn!k!∑ℓ=0k(−1)ℓ(kℓ)(ℓ/λn),λ≠0S(n,k),λ=0

and

𝐁n,k(⟨α⟩1,⟨α⟩2,…,⟨α⟩n−k+1)=(−1)kn!k!∑ℓ=0k(−1)ℓ(kℓ)(αℓn)(13)

for n≥k∈N0 and α,λ∈C, as done in Remark 7 of [12].

Considering the formulas (6), (7), and (8) in the formulas (12) or (13), we can derive

𝐁n,k(⟨α⟩1,⟨α⟩2,…,⟨α⟩n−k+1)=∑j=kns(n,j)αjS(j,k)(14)

for n≥k∈N0 and α∈C.

Combining (12), (13), and (14) results in

𝐁n,k(⟨α⟩1,⟨α⟩2,…,⟨α⟩n−k+1)=(−1)kk!∑ℓ=0k(−1)ℓ(kℓ)⟨αℓ⟩n=(−1)kn!k!∑ℓ=0k(−1)ℓ(kℓ)(αℓn)=∑ℓ=kns(n,ℓ)αℓS(ℓ,k)(15)

for n≥k∈N0 and α∈C. The equivalences in (9) and (10) are thus proved. The proof of Theorem 2.1 is complete.

3  Simpler Closed-Form Formulas

When taking α=±1,±2,12 in (9) and (10) respectively, we can derive several simpler closed-form combinatorial identities.

Theorem 3.1. For n≥k∈N0, we have

∑j=kns(n,j)1jS(j,k)=(0n−k), (16)

∑j=kns(n,j)2jS(j,k)=n!k!(kn−k)22k−n, (17)

∑j=kns(n,j)(12)jS(j,k)=(−1)n+k[2(n−k)−1]!!2n(2n−k−12(n−k)), (18)

∑j=kns(n,j)(−1)jS(j,k)=(−1)nn!k!(n−1k−1), (19)

and

∑j=kns(n,j)(−2)jS(j,k)=(−1)n+kn!k!∑ℓ=0k(−1)ℓ(kℓ)(n+2ℓ−1n).(20)

Proof. By the definition (1), we can easily deduce that, for n≥k∈N0,

𝐁n,k(1,0,…,0)=𝐁n,k(⟨1⟩1,⟨1⟩2,…,⟨1⟩n−k+1)=∑j=kns(n,j)1jS(j,k)=(0n−k),(21)

where we used the relation (15). See also pages 167–168 in [2]. The identity (16), which recovers the first one in (28) below, is thus proved.

In Theorem 5.1 of [13] and in Section 3 of [14], the formula

𝐁n,k(x,1,0,…,0)=12n−kn!k!(kn−k)x2k−n(22)

was established for n≥k∈N0, where we assumed (00)=1 and (pq)=0 for q>p∈N0. Making use of the identity (2), we can derive from the formula (22) that

𝐁n,k(2,2,0,…,0)=𝐁n,k(⟨2⟩1,⟨2⟩2,…,⟨2⟩n−k+1)=∑j=kns(n,j)2jS(j,k)=n!k!(kn−k)22k−n(23)

for n≥k∈N0. The identity (17) is thus verified.

In the proof of Theorem 3.2 in [2], it was obtained that

𝐁n,k(⟨12⟩1,⟨12⟩2,…,⟨12⟩n−k+1)=∑j=kns(n,j)(12)jS(j,k)=(−1)n+k[2(n−k)−1]!!2n(2n−k−12(n−k))(24)

for n≥k∈N0. The identity (18) is thus proved.

Replacing α by −α in (14) and utilizing (5) give

𝐁n,k((α)1,(α)2,…,(α)n−k+1)=(−1)n∑j=kns(n,j)(−α)jS(j,k)(25)

for n≥k∈N0 and α∈C. Taking α=−12 in the formula (25) and making use of the identity

𝐁n,k((−1)!!,1!!,3!!,…,[2(n−k)−1]!!)=[2(n−k)−1]!!(2n−k−12(n−k))

in Section 1.5 of [15] and in Theorem 1.2 of [16], we derive

𝐁n,k((−12)1,(−12)2,…,(−12)n−k+1)=(−1)k2n𝐁n,k((−1)!!,1!!,3!!,…,[2(n−k)−1]!!)=(−1)n∑j=kns(n,j)(12)jS(j,k)=(−1)k2n[2(n−k)−1]!!(2n−k−12(n−k))

for n≥k∈N0. The identity (18) is proved again.

Employing the relation (25) and using the identities

𝐁n,k(1!,2!,3!,…,(n−k+1)!)=n!k!(n−1k−1)

and

𝐁n,k(2!,3!,…,(n−k+2)!)=n!k!∑ℓ=0k(−1)k−ℓ(kℓ)(n+2ℓ−1n)

in Sections 1.3 and 1.9 of [15] and in Lemma 6 of [17], we acquire

𝐁n,k((1)1,(1)2,…,(1)n−k+1)=𝐁n,k(1!,2!,…,(n−k+1)!)=(−1)n∑j=kns(n,j)(−1)jS(j,k)=n!k!(n−1k−1)(26)

and

𝐁n,k((2)1,(2)2,…,(2)n−k+1)=𝐁n,k(2!,3!,…,(n−k)!)=(−1)n∑j=kns(n,j)(−2)jS(j,k)=n!k!∑ℓ=0k(−1)k−ℓ(kℓ)(n+2ℓ−1n).(27)

The identities (19) and (20) are thus derived. The proof of Theorem 3.1 is complete.

Remark 3.1. We can regard those identities from (17) to (20) in Theorem 3.1 as generalizations of the orthogonality relations

∑j=0ns(n,j)S(j,k)=∑j=0nS(n,j)s(j,k)=(0n−k),n≥k∈N0(28)

listed on page 171 in [7].

Theorem 3.2. For n∈N0 and α∈C, we have

∑k=0n(−1)kk!𝐁n,k(⟨α⟩1,⟨α⟩2,…,⟨α⟩n−k+1)=∑k=0n∑ℓ=0k(−1)ℓ(kℓ)⟨αℓ⟩n=n!∑k=0n∑ℓ=0k(−1)ℓ(kℓ)(αℓn)=∑k=0n(−1)kk!∑j=kns(n,j)αjS(j,k)=⟨−α⟩n(29)

and

∑k=0n(−1)kk!𝐁n,k((α)1,(α)2,…,(α)n−k+1)=∑k=0n∑ℓ=0k(−1)ℓ(kℓ)(αℓ)n=(−1)nn!∑k=0n∑ℓ=0k(−1)ℓ(kℓ)(−αℓn)=(−1)n∑k=0n(−1)kk!∑j=kns(n,j)(−α)jS(j,k)=(−α)n.(30)

Proof. Combining (12) and (14) yields

(−1)kk!∑j=kns(n,j)αjS(j,k)=∑ℓ=0k(−1)ℓ(kℓ)⟨αℓ⟩n,n≥k∈N0.

Accordingly, similar to arguments in Lemma 2.2 of [18], we acquire

∑k=0n(−1)kk!∑j=kns(n,j)αjS(j,k)=∑k=0n∑ℓ=0k(−1)ℓ(kℓ)⟨αℓ⟩n=∑ℓ=1n(−1)ℓ[∑k=ℓn(kℓ)]⟨αℓ⟩n=∑ℓ=1n(−1)ℓ(n+1ℓ+1)∑m=0ns(n,m)(αℓ)m=∑m=0ns(n,m)αm∑ℓ=1n(−1)ℓ(n+1ℓ+1)ℓm=∑m=0ns(n,m)(−α)m=⟨−α⟩n

for n∈N, where we used the relation

∑k=ℓn(kℓ)=(n+1ℓ+1),ℓ,n∈N,(31)

which is a special case x = 0 and r=ℓ of the identity

∑k=0n(k+xr)=(n+x+1r+1)−(xr+1)

in the formula (1.48) on pages 27–28 of [8], we used the relation (7) twice, and we used the equality

∑ℓ=1n(−1)ℓ(n+1ℓ+1)ℓm=∑ℓ=1m(−1)ℓ(n+1ℓ+1)ℓm=(−1)m,m,n∈N,(32)

which is a special case r = 1 and p = m of the identity

∑k=0rp−r+1(−1)k(rp+1k)(rp−kr)p=1

in the formula (X.5) on page 132 of [8]. Further applying relations in (15), we conclude those relations in (29).

Replacing α by −α in (29), using the identities (4), (5), and (2) in sequence, and simplifying lead to (30). The proof of Theorem 3.2 is thus complete.

Remark 3.2. The last equality in (29) can be rewritten as

∑k=0n(−1)kk!∑j=kns(n,j)αjS(j,k)=∑j=0ns(n,j)αj∑k=0jS(j,k)[(−1)kk!]=⟨−α⟩n.(33)

Theorem 12.1 on page 171 of [7] reads that, if bα and ak are a collection of constants independent of n, then

an=∑α=0nS(n,α)bαif and only ifbn=∑k=0ns(n,k)ak.

Applying Theorem 12.1 on page 171 in [7] to the second equality in (33), we find

∑k=0nS(n,k)⟨−α⟩k=αn∑j=0nS(n,j)[(−1)jj!].

Considering the explicit formula (6) and utilizing (31) and (32), we arrive at

∑k=0nS(n,k)[(−1)kk!]=∑k=1n∑ℓ=1k(−1)ℓ(kℓ)ℓn=∑ℓ=1n(−1)ℓℓn∑k=ℓn(kℓ)=∑ℓ=1n(−1)ℓℓn(n+1ℓ+1)=(−1)n

for n∈N. Therefore, we obtain

∑k=0nS(n,k)⟨−α⟩k=(−α)n,n∈N0,α∈C,

which is a recovery of the well-known relation

∑k=0nS(n,k)⟨α⟩k=αn,n∈N0,α∈C

in the equation (1.27) on page 19 of [10].

4  Several Combinatorial Identities

In items (3.163) and (3.164) on pages 91–92 of [8], we find two identities

∑k=0n(nk)(k/2ℓ)=nℓ(n−ℓ−1ℓ−1)2n−2ℓ

and

∑k=0n(−1)k(nk)(k/2ℓ)=(−1)ℓ2n−2ℓ[(2ℓ−n−1ℓ−1)−(2ℓ−n−1ℓ)].

Lemma 2.2 in [18] reads that

∑ℓ=0k(−1)ℓ(kℓ)(ℓ/2n)={0,k>n∈N0;(−1)nk![2(n−k)−1]!!(2n)!!(2n−k−12(n−k)),n≥k∈N0.(34)

We can also find some discussions and alternative proofs for these three identities at the sites https://math.stackexchange.com/q/1098257 and https://math.stackexchange.com/q/4235171.

Theorem 4.1. For n,k∈N0, the identities

∑ℓ=0k(−1)ℓ(kℓ)(ℓn)={0,k>n∈N0;(−1)kk!n!(0n−k),n≥k∈N0, (35)

∑ℓ=0k(−1)ℓ(kℓ)(2ℓn)={0,k>n∈N0;(−1)k(kn−k)22k−n,n≥k∈N0, (36)

∑ℓ=0k(−1)ℓ(kℓ)(−ℓn)={0,k>n∈N0;(−1)n+k(n−1k−1),n≥k∈N0, (37)

∑ℓ=0k(−1)ℓ(kℓ)(−2ℓn)={0,k>n∈N0;(−1)n∑ℓ=0k(−1)ℓ(kℓ)(n+2ℓ−1n),n≥k∈N0, (38)

and the identity (34) are valid.

Proof. For the case n≥k∈N0, these identities follow from Theorem 3.1, the equivalence (10), and simplifying.

For the case k>n∈N0, making use of the relation 8 and utilizing the explicit formula (6), we acquire

∑ℓ=0k(−1)ℓ(kℓ)(αℓn)=1n!∑ℓ=0k(−1)ℓ(kℓ)[n!(αℓn)]=1n!∑ℓ=0k(−1)ℓ(kℓ)∑q=0ns(n,q)(αℓ)q=1n!∑q=0ns(n,q)αq∑ℓ=0k(−1)ℓ(kℓ)ℓq=(−1)kk!n!∑q=0ns(n,q)αqS(q,k)

for all k,n∈N0 and α∈C, where 00 was regarded as 1. Therefore, it is clear that

∑ℓ=0k(−1)ℓ(kℓ)(αℓn)=0,k>n∈N0,α∈C.

The proof of Theorem 4.1 is complete.

Remark 4.1. The identity (35) can be simplified as

∑ℓ=0k(−1)ℓ(kℓ)(ℓn)={0,k≠n(−1)k,n=k

for n,k∈N0.

The identities (36), (37), and (39) in Theorem 4.1 are probably new.

Theorem 4.2. For n∈N0, we have

∑k=0n(−1)kk!(0n−k)=(−1)nn!, (39)

∑k=0n(−1)k(kn−k)22k=(−1)n2n(n+1), (40)

∑k=0n(−1)k(n−1k−1)={1,n=0;−1,n=1;0,n≥2, (41)

∑k=0n(−1)k(n+2k−1n)(n+1k+1)={1,n=0;−2,n=1;1,n=2;0,n≥3, (42)

∑ℓ=0n(−1)ℓ(ℓ/2n)(n+1ℓ+1)=(−1)n(2n−1)!!(2n)!!, (43)

∑k=0nk![2(n−k)−1]!!(2n−k−12(n−k))=(2n−1)!!, (44)

and

∑k=1n(2n−k−1n−1)k(k+1)2k=n22n.(45)

Proof. From (29), we conclude that

∑k=0n(−1)kk!𝐁n,k(⟨α⟩1,⟨α⟩2,…,⟨α⟩n−k+1)=⟨−α⟩n.(46)

for n∈N0 and α∈C.

Substituting (21) into (46) gives

∑k=0n(−1)kk!(0n−k)=⟨−1⟩n=(−1)nn!.

The identity (39) is thus proved.

Substituting (23) into (46) results in

∑k=0n(−1)k(kn−k)22k=2n⟨−2⟩nn!=(−1)n2n(n+1).

The identity (40) is verified.

Utilizing the relations (2) and (5), we can reformulate the identity (26) as

𝐁n,k(⟨−1⟩1,⟨−1⟩2,…,⟨−1⟩n−k+1)=(−1)nn!k!(n−1k−1).

Substituting this equality into (46) arrives at

∑k=0n(−1)k(n−1k−1)=(−1)n⟨1⟩nn!={1,n=0;−1,n=1;0,n≥2.

The formula (41) follows.

Utilizing the relations (2) and (5), we can reformulate the identity (27) as

𝐁n,k(⟨−2⟩1,⟨−2⟩2,…,⟨−2⟩n−k+1)=(−1)nn!k!∑ℓ=0k(−1)k−ℓ(kℓ)(n+2ℓ−1n).

Substituting this equality into (46) and employing (31) reveal

(−1)n⟨2⟩nn!=∑k=0n∑ℓ=0k(−1)ℓ(kℓ)(n+2ℓ−1n)=∑ℓ=0n(−1)ℓ(n+2ℓ−1n)∑k=ℓn(kℓ)=∑ℓ=0n(−1)ℓ(n+2ℓ−1n)(n+1ℓ+1)