Touchard Polynomials, Partial Bell Polynomials and Polynomials of Binomial

Type

Miloud Mihoubi and Mohammed Said Maamra^{1} University of Science and Technology Houari Boumediene (USTHB) Faculty of Mathematics PB 32 El Alia, 16111, Algiers Algeria

                    miloudmihoubi@gmail.com
                       mmihoubi@usthb.dz
                       mmaamra@yahoo.fr

Abstract Touchard generalized the Bell polynomials in order to give some combinatorial interpretation on permutations. Chrysaphinou introduced and studied a class of polynomials related to Touchard’s generalization. In the present paper, we establish some relations between Touchard polynomials, Bell polynomials and the polynomials of binomial type. Several identities and relations with Stirling numbers are obtained.

1 Introduction

Among the partition polynomials, the partial Bell polynomials, introduced by Bell [3], play an important role in different application frameworks. Several properties and identities are given, see [5, 7, 9, 10]. Another partition polynomials, called Touchard polynomials, introduced by Touchard [11], present an extension of the partial Bell polynomials. Some algebraic, combinatorial and probabilistic properties of these polynomials are studied by Touchard [11], Chrysaphinou [6], Charalambides [5], Kuzmin and Leonova [8]. In this paper, we give some relations between Touchard polynomials and partial Bell polynomials. We exploit these relations and the polynomials of binomial type to derive some identities for these polynomials.

1Research supported by LAID3 Laboratory of USTHB University.

In this context, let (x_{i}; i ≥ 1) and (y_{i}; i ≥ 1) be two sequences of real numbers. The Touchard polynomials

T_{n,k}(x_{j}; y_{j}) := T_{n,k}(x_{1}, …, x_{n}; y_{1}, …, y_{n}), n ≥ k ≥ 0,

are defined by their bivariate generating function

∑_{n≥0}∑^{n} ; k=0T_{n,k}(x_{j}; y_{j})u^{k} \frac{t^{n}}{n!} = exp(u∑_{i≥1}x_{i} \frac{t^{i}}{i!} + ∑_{i≥1}y_{i} \frac{t^{i}}{i!}).

The vertical generating function of Touchard polynomials, for fixed k, is given by

∑_{n≥k}T_{n,k}(x_{j}; y_{j})\frac{t^{n}}{n!} = \frac{1}{k!}(∑_{i≥1}x_{i} \frac{t^{i}}{i!})^{k} exp(∑_{i≥1}y_{i} \frac{t^{i}}{i!}), k = 0, 1, ….

The partial Bell polynomials are given by

B_{n,k}(x_{j}) := B_{n,k}(x_{1}, …, x_{n}) = T_{n,k}(x_{1}, …, x_{n}; 0, …, 0), n ≥ k ≥ 0.

The polynomials of binomial type (f_{n}(x)) are defined by

∑_{n≥0}f_{n}(x)\frac{u^{n}}{n!} = (∑_{n≥0}f_{n}(1)\frac{u^{n}}{n!} )^{x}, with f_{0}(x) = 1 and f_{1}(x) ≠ 0 for x ≠ 0.

For a real number a we consider in the following the sequence (f_{n}(x; a)) defined by

f_{n}(x; a) := \frac{x}{an + x}f_{n} (an + x) .

The sequence (f_{n}(x; a)) is also of binomial type, see [9], and for more details on sequences of binomial type see [1]. We use the following notation and hypothesis:

D ≡ \frac{d}{dx}, D^{k} ≡ \frac{d^{k}}{dx^{k}} , D_{x=x_{0}}^{k} ≡ \frac{d^{k}}{dx^{k}} |_{x=x_{0}}.

For n < 0, we set f_{n}(x) = 0, T_{n,k}(x_{j}; y_{j}) = 0 and B_{n,k}(x_{j}) = 0.

For x ∈ ℝ, where ℝ is the set of real numbers, we set

\binom{x}{k} := \frac{x(x − 1) ⋯ (x − k + 1)}{k!} for k = 1, 2, …, \binom{x}{0} = 1 and \binom{x}{k} = 0 otherwise.

Also, for all nnnegative integers n, m we put

1_{(m|n)} = \begin{cases}1, if m divides n; \\ 0, otherwise; \end{cases} and 1_{(n≥m)} = \begin{cases}1, if n ≥ m; \\ 0, otherwise. \end{cases}

2 The main results

In this section, we establish some relations between the Touchard polynomials, partial Bell polynomials and polynomials of binomial type. Furthermore, we use these relations to develop several identities for Touchard polynomials. We start with the following theorem:

Theorem 1. Let n, k, m be integers such that n ≥ k ≥ 1, m ≥ 1; a be a real number and (x_{n}) be a sequence of real numbers. Then

T_{n,k}(x_{j}; −m(j − 1)!a^{j/m}1_{(m|j)}) = B_{n,k}(x_{j}) − am!\binom{n}{m}B_{n−m,k}(x_{j}).

Proof. Let y_{n} = −m(n − 1)!a^{n/m}1_{(m|n)}. For a = 0 the theorem is trivial, otherwise, for |t| < |a|^{−1/m} we have

exp(∑_{i≥1}y_{i} \frac{t^{i}}{i!}) = exp(−∑_{j≥1}a^{j} \frac{t^{mj}}{j} ) = exp(ln(1 − at^{m})) = 1 − at^{m}.

Then

∑_{n≥k}T_{n,k}(x_{j}; y_{j})\frac{t^{n}}{n!} = \frac{1}{k!}(∑_{i≥1}x_{i} \frac{t^{i}}{i!})^{k} exp(∑_{i≥1}y_{i} \frac{t^{i}}{i!})

= \frac{1}{k!}(∑_{i≥1}x_{i} \frac{t^{i}}{i!})^{k}(1 − at^{m})

= ∑_{n≥k}(B_{n,k}(x_{j}) − a\frac{n!}{(n − m)!}B_{n−m,k}(x_{j}))\frac{t^{n}}{n!}.

Hence the theorem is proved.

If we set x_{n} = nf_{n−1}(x; b) in Theorem 1 and use Proposition 1 of [9], we obtain:

Corollary 2. Let (f_{n}(x)) be a sequence of binomial type of polynomials. We have

T_{n,k}(jf_{j−1}(x; b); −m(j − 1)!a^{j/m}1_{(m|j)}) = \frac{n!}{k!}(\frac{f_{n−k}(kx; b)}{(n − k)!} − a\frac{f_{n−m−k}(kx; b)}{(n − m − k)!}).

Example 3. For f_{n}(x) = x^{n} in Corollary 2 we get

T_{n,k}(jx(b(j − 1) + x)^{j−2}; −m(j − 1)!a^{j/m}1_{(m|j)})

= x\frac{n!}{(k − 1)!}(\frac{(b(n − k) + kx)^{n−k−1}}{(n − k)!} − a\frac{(b(n − m − k) + kx)^{n−m−k−1}}{(n − m − k)!} 1_{(n≥m+k)}),

and for f_{n}(x) = n!\binom{x}{n} in Corollary 2 we get

T_{n,k}(xj!\frac{\binom{b(j−1)+x}{j−1}}{b(j − 1) + x}; −m(j − 1)!a^{j/m}1_{(m|j)})

= x\frac{n!}{(k − 1)!}(\frac{\binom{b(n−k)+kx}{n−k}}{b(n − k) + kx} − a\frac{\binom{b(n−m−k)+kx}{n−m−k}}{b(n − m − k) + kx}1_{(n≥m+k)}).

As above, for particular cases of Touchard polynomials, the following proposition gives another expression in term of polynomials of binomial type.

Proposition 4. Let b, α be two real numbers and (f_{n}(x)) be a sequence of binomial type of polynomials. We have

T_{n,k}(jf_{j−1}(x); αDf_{j}(0)) = \binom{n}{k}f_{n−k}(kx + α),

or more generally

T_{n,k}(jx\frac{f_{j−1}(b(j − 1) + x)}{b(j − 1) + x}; α\frac{f_{j}(bj)}{bj})

= \binom{n}{k}(kx + α)\frac{f_{n−k}(b(n − k) + kx + α)}{b(n − k) + kx + α}, b ≠ 0.

Proof. Let

1 + ∑_{n≥1}f_{n}(x)\frac{t^{n}}{n!} = exp(x∑_{i≥1}y_{i} \frac{t^{i}}{i!})

be the exponential generating function of the sequence (f_{n}(x)) and x_{n} = nf_{n−1}(x). Necessarily y_{n} = Df_{n}(0). We have

∑_{n≥k}T_{n,k}(x_{j}; αy_{j})\frac{t^{n}}{n!} = \frac{1}{k!}(∑_{i≥1}x_{i} \frac{t^{i}}{i!})^{k} exp(α∑_{i≥1}y_{i} \frac{t^{i}}{i!})

= \frac{t^{k}}{k!} exp((kx + α)∑_{i≥1}y_{i} \frac{t^{i}}{i!})

= \frac{t^{k}}{k!}∑_{n≥0}f_{n}(kx + α)\frac{t^{n}}{n!}

= ∑_{n≥k}\binom{n}{k}f_{n−k}(kx + α)\frac{t^{n+k}}{n!} .

Then, we obtain

T_{n,k}(jf_{j−1}(x); αDf_{j}(0)) = \binom{n}{k}f_{n−k}(kx + α).

To finish the proof, replace f_{n}(x) by f_{n}(x; b) in the last identity.

Example 5. For f_{n}(x) = x^{n} in Proposition 4 we get

T_{n,k}(xj(b(j − 1) + x)^{j−2}; α(j − 1)(bj)^{j−2}) = \binom{n}{k}(kx + α)(b(n − k) + kx + α)^{n−k−1},

and for f_{n}(x) = n!\binom{x}{n} in Proposition 4 we get

T_{n,k}(\frac{j!x}{b(j − 1) + x}\binom{b(j − 1) + x}{j − 1}; α(−1)^{j−1}(j − 1)!)

= \frac{n!}{k!} \frac{kx + α}{n(n − k) + kx + α}\binom{n(n − k) + kx + α}{n − k}.

Hence we may state the following:

Corollary 6. Let r, s, p be a nonnegative integers, r ≥ 1, and (x_{n}) be a sequence of real numbers with x_{1} = 1. We have

T_{n,k}(\frac{js}{(r(j − 1) + s)} \frac{B_{(r+1)(j−1)+s, r(j−1)+s}(x_{i})}{\binom{(r+1)(j−1)+s}{r(j−1)+s}}; \frac{p}{rj} \frac{B_{(r+1)j, rj}(x_{i})}{\binom{(r+1)j}{rj}})

= \binom{n}{k}\frac{ks + p}{r(n − k) + ks + p} \frac{B_{(r+1)(n−k)+ks+p, r(n−k)+ks+p}(x_{i})}{\binom{(r+1)(n−k)+ks+p}{r(n−k)+ks+p}}.

Proof. For x_{2} ≠ 0, let \{f_{n}(x)\} be a sequence of binomial type such that f_{n}(1) = \frac{x_{n+1}}{n+1} .

From the known identity B_{n,k}(jf_{j−1}(1)) = \binom{n}{k}f_{n−k}(k) we get

f_{n}(k) = \binom{n + k}{k}^{−1}B_{n+k,k}(x_{i}), n ≥ 0, k ≥ 1.

Take b = r, x = s and α = p in Proposition 4 to get

T_{n,k}(js\frac{f_{j−1}(r(j − 1) + s)}{r(j − 1) + s}; p\frac{f_{j}(rj)}{rj}) = \binom{n}{k}(ks + p)\frac{f_{n−k}(r(n − k) + ks + p)}{r(n − k) + ks + p}.

Therefore, it suffices to use the identity f_{n}(k) = \binom{n+k}{k}^{−1}B_{n+k,k}(x_{i}) to express in the last identity f_{i−1}(r(i − 1) + s) and f_{n−k}(r(n − k) + ks + p) by the partial Bell polynomials. For the case x_{2} = 0 the corollary remains true by continuity.

Example 7. By Corollary 6 and the identity B_{n,k}(1!, 2!, …, (q + 1)!, 0, …) = \frac{n!}{k!} \binom{k}{n−k}_{q}, see [2], we get

T_{n,k}(\frac{j!s}{r(j − 1) + s}\binom{r(j − 1) + s}{j − 1}_{q}; \frac{(j − 1)!p}{r}\binom{rj}{j}_{q})

= \frac{n!}{k!} \frac{ks + p}{r(n − k) + ks + p}\binom{r(n − k) + ks + p}{n − k}_{q},

where \binom{k}{n}_{q} is the coefficients defined by (1 + x + x^{2} + ⋯ + x^{q})^{k} = ∑_{n≥0} \binom{k}{n}_{q}x^{n}.

Also, for x_{n} = 1, x_{n} = (−1)^{n−1}(n − 1)!, x_{n} = (n − 1)! or x_{n} = n! we get identities related Touchard polynomials to Stirling numbers of the first and second kind.

The following two propositions give relations between Touchard polynomials and the successive derivatives of polynomials of binomial type.

Proposition 8. Let b be a real number, b ≠ 0, and (f_{n}(x)) be a sequence of binomial type of polynomials. We have

T_{n,k}(Df_{j}(0); xDf_{j}(0)) = \frac{1}{k!}D^{k}f_{n}(x),

or more generally

T_{n,k}(\frac{f_{j}(bj)}{bj}; x\frac{f_{j}(bj)}{bj}) = \frac{1}{k!}D^{k}(\frac{x}{bn + x}f_{n}(bn + x)).

Proof. Let (f_{n}(x)) be a sequence of binomial type defined as in the proof of Proposition 4 and x_{n} = nf_{n−1}(x). We have y_{n} = Df_{n}(0) and

∑_{n≥k}D^{k}f_{n}(x)\frac{t^{n}}{n!} = (∑_{i≥1}y_{i} \frac{t^{i}}{i!})^{k} exp(x∑_{i≥1}y_{i} \frac{t^{i}}{i!}) = k!∑_{n≥k}T_{n,k}(y_{j}; xy_{j})\frac{t^{n}}{n!}.

Then

T_{n,k}(y_{j}; xy_{j}) = T_{n,k}(Df_{j}(0); xDf_{j}(0)) = \frac{1}{k!}D^{k}f_{n}(x).

After that, replace f_{n}(x) by f_{n}(x; b) in the last identity.

Example 9. For f_{n}(x) = x^{n} in Proposition 8 we get

T_{n,k}((bj)^{j−1}; x(bj)^{j−1}) = \frac{n!}{(k!)^{2}} (bn + x)^{n−k−1}(b(n − 1) + x),

and for f_{n}(x) = n!\binom{x}{n} in Proposition 8 we get

T_{n,k}(\frac{j!}{bj} \binom{bj}{j}; x\frac{j!}{bj} \binom{bj}{j}) = \frac{n!}{k!}D^{k}(\frac{x}{bn + x}\binom{bn + x}{n}).

Proposition 10. Let b, α, β be real numbers, r be a positive integer and (f_{n}(x)) be a sequence of binomial type of polynomials. We have

T_{n,k}(jD_{z=0}^{r}(e^{βz}f_{j−1}(x + z)); αDf_{j}(0))

= \frac{(kr)!}{k!}T_{n,kr}(β1_{(j=1)} + jDf_{j−1}(0)1_{(j≥2)}; (kx + α)Df_{j}(0)),

or more generally,

T_{n,k}(jD_{z=0}^{r}(\frac{(x + z)f_{j−1}(b(j − 1) + x + z)}{b(j − 1) + x + z}e^{βz}); α\frac{f_{j}(bj)}{bj})

= \frac{(kr)!}{k!}T_{n,kr}(β1_{(j=1)} + j \frac{f_{j−1}(b(j − 1))}{b(j − 1)}1_{(j≥2)}; (kx + α)\frac{f_{j}(bj)}{bj}).

Proof. Let (f_{n}(x)) be a sequence of binomial type defined as in the proof of Proposition 4 and x_{n} = nD_{z=0}^{r}(e^{βz}f_{n−1}(x + z)). We have y_{n} = Df_{n}(x)(0) and

\frac{1}{k!}(∑_{i≥1}x_{i} \frac{t^{i}}{i!})^{k} = (∑_{i≥1}iD_{z=0}^{r}(e^{βz}f_{i−1}(x + z))\frac{t^{i}}{i!})^{k}

= \frac{t^{k}}{k!}F (t)^{kx}(D_{z=0}^{r}(e^{βz}F (t)^{z}))^{k}

= \frac{t^{k}}{k!}F (t)^{kx}(β + ln F (t))^{kr}

= \frac{t^{k}}{k!}D_{z=0}^{kr}(e^{βz}F (t)^{kx+z})

= \frac{1}{k!}(βt + ∑_{i≥2}iy_{i−1} \frac{t^{i}}{i!})^{kr} exp(kx∑_{i≥1}y_{i} \frac{t^{i}}{i!}).

Then

∑_{n≥k}T_{n,k}(x_{j}; αy_{j})\frac{t^{n}}{n!} = \frac{1}{k!}(∑_{i≥1}x_{i} \frac{t^{i}}{i!})^{k} exp(α∑_{i≥1}y_{i} \frac{t^{i}}{i!})

= \frac{1}{k!}(βt + ∑_{i≥2}iy_{i−1} \frac{t^{i}}{i!})^{kr} exp((kx + α)∑_{i≥1}y_{i} \frac{t^{i}}{i!})

= \frac{(kr)!}{k!}∑_{n≥k}T_{n,kr}(β1_{(j=1)} + jy_{j−1}1_{(j≥2)}; (kx + α)y_{j})\frac{t^{n}}{n!}.

Then, we obtain

T_{n,k}(jD_{z=0}^{r}(e^{βz}f_{j−1}(x + z)); αDf_{j}(0))

= \frac{(kr)!}{k!}T_{n,kr}(β1_{(j=1)} + jy_{j−1}1_{(j≥2)}; (kx + α)Df_{j}(0)).

To finish the proof, replace f_{n}(x) by f_{n}(x; b) in the last identity.

Example 11. For f_{n}(x) = x^{n} in Proposition 10 we get

T_{n,k}(jD_{z=0}^{r}((x + z)(b(j − 1) + x + z)^{j−2}e^{βz}); α(bj)^{j−1})

= \frac{(kr)!}{k!}T_{n,kr}(β1_{(j=1)} + j(b(j − 1))^{j−2}1_{(j≥2)}; (kx + α)(bj)^{j−1}).

Proposition 12. Let (x_{n}) and (y_{n}) be two sequences of real numbers and r be a positive integer. We have

B_{n,k}(\frac{r}{\binom{j+r−1}{r−1}}T_{j+r−1,r}(x_{i}; y_{i})) = \begin{matrix}( & {kr \atop k} & ) \\ ( & {n+(r−1)k \atop (r−1)k} & ) \end{matrix}T_{n+(r−1)k,kr}(x_{i}; ky_{i})

Proof. Starting with the vertical generating function of Touchard polynomials to get

(∑_{n≥r}T_{n,r}(x_{i}; y_{i})\frac{t^{n}}{n!})^{k} = \frac{1}{(r!)^{k}} (∑_{i≥1}x_{i} \frac{t^{i}}{i!})^{kr} exp(k∑_{i≥1}y_{i} \frac{t^{i}}{i!})

= \frac{(kr)!}{(r!)^{k}} ∑_{n≥kr}T_{n,kr}(x_{i}; ky_{i})\frac{t^{n}}{n!}.

Then

T_{n,kr}(x_{i}; ky_{i}) = \frac{(r!)^{k}k!}{(kr)!}B_{n,k}(\underbrace{0, …, 0}_{r−1}, T_{r,r}(x_{i}; y_{i}), T_{r+1,r}(x_{i}; y_{i}), …),

and from [5, p. 450] we have

B_{n,k}(0, …, 0, a_{r}, a_{r+1}, …) = \frac{n!}{(n − (r − 1)k)!}B_{n−(r−1)k,k}(\frac{i!a_{i+r−1}}{(i + r − 1)!}).

Then

T_{n,kr}(x_{j}; ky_{j}) = \frac{(r!)^{k}n!k!}{(kr)!(n − (r − 1)k)!}B_{n−(r−1)k,k}(\frac{j!}{(r − 1 + j)!}T_{r−1+j,r}(x_{i}; y_{i})).

Change n by n + (r − 1)k to finish the proof. Example 13. Let r, s, p, q be nonnegative integers with q ≥ 1. Use Application 7 in Proposition 12 to obtain

B_{n,k}(\frac{j!(rs + p)}{r(j − 1) + rs + p}\binom{r(j − 1) + rs + p}{j − 1}_{q})

= \frac{n!}{k!} \frac{k(rs + p)}{r(n − k) + k(rs + p)}\binom{r(n − k) + k(rs + p)}{n − k}_{q}.

From the identity T_{n,r}(i!; (i − 1)!s) = \frac{n!}{r!} \binom{n+s−1}{r+s−1} given in [5, p. 453] we obtain

B_{n,k}(j!\binom{j + r + s − 2}{r + s − 1}) = \frac{n!}{k!}\binom{n + k(r + s − 1) − 1}{k(r + s) − 1}.

From Theorems 15 and 16 given in [4] we have

T_{n,r}((i − 1)!; (i − 1)!s) = \left[{n + s \atop r + s}\right]_{s} and T_{n,r}(1; s1_{(i=1)}) = \left\{{n + s \atop r + s}\right\}_{s}.

These identities and Proposition 12 give

B_{n,k}(\frac{r}{\binom{j+r−1}{r−1}} [ \begin{matrix}j + r + s − 1 \\ r + s \end{matrix} ]_{s}) = \begin{matrix}( & {kr \atop k} & ) \\ ( & {n+(r−1)k \atop (r−1)k} & ) \end{matrix} [ \begin{matrix}n + (r + s − 1)k \\ (r + s)k \end{matrix} ]_{ks} ,
B_{n,k}(\frac{r}{\binom{j+r−1}{r−1}} \{ \begin{matrix}j + r + s − 1 \\ r + s \end{matrix} \}_{s}) = \begin{matrix}( & {kr \atop k} & ) \\ ( & {n+(r−1)k \atop (r−1)k} & ) \end{matrix} \{ \begin{matrix}n + (r + s − 1)k \\ (r + s)k \end{matrix} \}_{ks} .

References

[1] M. Aigner, Combinatorial Theory. Springer, 1979.

[2] H. Belbachir, S. Bouroubi, and A. Khelladi, Connection between ordinary multinomials, generalized Fibonacci numbers, partial Bell partition polynomials and convolution powers of discrete uniform distribution. Ann. Math. Inform. 35 (2008), 21–30.

[3] E. T. Bell, Exponential polynomials. Ann. Math. 35 (1934), 258–277.

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

[5] C. A. Charalambides, Enumerative Combinatorics. Chapman & Hall/CRC, 2001.

[6] O. Chrysaphinou, On Touchard polynomials. Discrete Math. 54 (1985), 143–152.

[7] L. Comtet, Advanced Combinatorics. D. Reidel Publishing Company, Dordrecht-Holland, 1974.

[8] O. V. Kuzmin and O. V. Leonova, Touchard polynomials and their applications. Disc. Math. Appl. 10 (2000), 391–402.

[9] M. Mihoubi, Bell polynomials and binomial type sequences. Discrete Math. 308 (2008), 2450–2459.

[10] M. Mihoubi, The role of binomial type sequences in determination identities for Bell polynomials. To appear, Ars Combin. Preprint available at

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

[11] J. Touchard, Sur les cycles des substitutions, Acta Math. 70 (1939), 243–279.

2010 Mathematics Subject Classification: Primary 05A10; Secondary 05A99, 11B73, 11B75. Keywords: Touchard polynomials; partial Bell polynomials; polynomials of binomial type.

Received October 21 2010; revised version received February 13 2011. Published in Journal of Integer Sequences, March 25 2011.

Return to Journal of Integer Sequences home page.