Motzkin Numbers: an Operational Point of View

M. Artioli

ENEA — Bologna Research Center

Via Martiri di Monte Sole, 4

40129 Bologna

Italy

marcello.artioli@enea.it

G. Dattoli

ENEA — Frascati Research Center Via Enrico Fermi 45 00044 Frascati, Rome

Italy

giuseppe.dattoli@enea.it

S. Licciardi

Dept. of Mathematics and Computer Science

University of Catania Viale A. Doria 6 95125, Catania

Italy and

ENEA — Frascati Research Center Via Enrico Fermi 45 00044 Frascati, Rome

Italy

silvia.licciardi@dmi.unict.it

S. Pagnutti

ENEA — Bologna Research Center

Via Martiri di Monte Sole, 4

40129, Bologna

Italy

simonetta.pagnutti@enea.it

Abstract The Motzkin numbers can be derived as coefficients of hybrid polynomials. Such an identification allows the derivation of new identities for this family of numbers, and offers a tool to investigate previously unnoticed links with the theory of special functions and with the relevant treatment in terms of operational means. The use of umbral methods opens new directions for further developments and generalizations, which leads, e.g., to the identification of new Motzkin-associated forms.

1 Introduction

The telephone numbers (T_{n}), also called convolution numbers, provide a very well-known example of the link between special numbers and special polynomials. The (T_{n}) can be expressed in terms of the coefficients of Hermite polynomials (h_{s}) [1, pp. 85–86]. Two of the present authors (M. A. and G. D.) have recently pointed out [2] that the Padovan and Perrin numbers [3, 4] can be recognized as associated with particular values of two-variable Legendre polynomials [5].

The Motzkin numbers plays a significant role in combinatorics (see, e.g., Bernhart [6]), Donaghey and Shapiro pointed out fourteen different manifestations of these numbers [7]. Blasiak et al. and Dattoli et al. have studied [8, 9] the connection between Motzkin numbers and a family of hybrid polynomials and the relevant properties of Motzkin numbers.

In a recent paper, Zhao and Qi [10] discussed similar results employing the link between Motzkin and Catalan numbers.

The hybrid polynomials are defined as follows [9]:

P_{n}^{(q)}(x, y) = n! ∑_{r=0}^{⌊ \frac{n}{2} ⌋} \frac{x^{n−2r}y^{r}}{(n − 2r)!r!(r + q)!},  (1)

and the relevant generating function is

∑_{n=0}^{∞} \frac{t^{n}}{n!}P_{n}^{(q)}(x, y) = \frac{I_{q}(2\sqrt{y} t)}{(\sqrt{y} t)^{q}}e^{xt},  (2)

where I_{q}(x) is the modified Bessel function of the first kind of order q.

Within the present framework, the Motzkin number sequence can be specified as follows [8]:

\begin{matrix}m_{n} = P_{n}^{(1)}(1, 1) = ∑_{s=0}^{n} m_{n,s}, \\ m_{n,s} = \binom{n}{s} f_{s}, \\ f_{s} = \frac{s!}{Γ (\frac{s}{2} + 2) Γ (\frac{s}{2} + 1)} |cos (s\frac{π}{2} )| , \end{matrix}  (3)

where the coefficients m_{n,s} can be represented as the triangle reported in the following table, in which m_{n,2} corresponds, in the On-Line Encyclopedia of Integer Sequences (OEIS), to the sequence \underline{A000217}, m_{n,4} to \underline{A034827}, m_{n,6} to \underline{A000910}, and so on.

m_{n,s} coefficients  m_{n} Motzkin
Parameter  s  ∑_{s=0}^{n} m_{n,s}
0 1 2 3 4 5 6 7
n  0 1  1
1 1 0  1
2 1 0 1  2
3 1 0 3 0  4
4 1 0 6 0 2  9
5 1 0 10 0 10 0  21
6 1 0 15 0 30 0 5  51
7 1 0 21 0 70 0 35 0  127

Table 1: Motzkin numbers and their coefficients

According to Eq. (2), the Motzkin numbers can also be defined as the coefficients of the following series expansion

∑_{n=0}^{∞} \frac{t^{n}}{n!}m_{n} = \frac{I_{1}(2t)}{t}e^{t}.  (4)

In what follows we show how some progress in the study of the relevant properties can be achieved by the use of the umbral notation.

2 Motzkin numbers and the umbral calculus

In order to simplify most of the algebra associated with the study of the properties of the Motzkin numbers, and to get new relevant identities, we introduce a formalism successfully exploited elsewhere [11] based on of the umbral calculus [12].

To this aim, we note that the function

C_{q}(x) = \frac{I_{q}(2\sqrt{x})}{(\sqrt{x})^{q}} = ∑_{r=0}^{∞} \frac{x^{r}}{r!(q + r)!}  (5)

can be cast in the form

C_{q}(x) = ĉ^{q} ∘ e^{ĉx},  (6)

where ĉ is an umbral operator defined according to the equation

ĉ^{μ} = \frac{1}{Γ(μ + 1)},  (7)

with μ real and not necessarily integer.

We define the following composition rule

ĉ^{μ} ∘ ĉ^{ν} = ĉ^{μ+ν},  (8)

and we let Ĉ = {ĉ^{α}, α ∈ ℂ} denote the set of ĉ-operators. Then the pair (Ĉ, ∘) satisfies the Abelian group property. The mathematical foundations of the theory of ĉ-operators can be traced back to those underlying the Borel transform and have been carefully discussed [12].

The use of this formalism allows one to restyle the hybrid polynomials in the form

P_{n}^{(q)}(x, y) = ĉ^{q} ∘ H_{n}(x, ĉ y),  (9)

where

H_{n}(x, y) = n! ∑_{r=0}^{⌊ \frac{n}{2} ⌋} \frac{x^{n−2r}y^{r}}{(n − 2r)!r!}  (10)

are the two-variable Hermite-Kampé de Fériét polynomials of order 2.

We can accordingly use the wealth of properties of this family of polynomials to derive further and new relations regarding those of the Motzkin numbers family.

Indeed, by recalling the generating function [9]

∑_{n=0}^{∞} \frac{t^{n}}{n!}H_{n+l}(x, y) = H_{l}(x + 2yt, y)e^{xt+yt^{2}},  (11)

we find

∑_{n=0}^{∞} \frac{t^{n}}{n!}m_{n+l} = ĉ ∘ H_{l}(1 + 2ĉt, ĉ)e^{t+ĉt^{2}},  (12)

which, after using Eqs. (8), (10), and (6), finally yields

\begin{matrix}∑_{n=0}^{∞} \frac{t^{n}}{n!}m_{n+l} = μ_{l}(t) e^{t}, \\ μ_{l}(t) = l! ∑_{r=0}^{⌊ \frac{l}{2} ⌋} \frac{1}{r!} ∑_{s=0}^{l−2r} \frac{2^{s}}{s!(l − 2r − s)!} \frac{I_{s+r+1}(2t)}{t^{r+1}}. \end{matrix}  (13)

Furthermore, the same procedure and the use of the Hermite polynomial duplication formula [13]

H_{2n}(x, y) = ∑_{r=0}^{n} \binom{n}{r}^{2}r! (2y)^{r} (H_{n−r}(x, y))^{2} ,  (14)

yields the following identity for Motzkin numbers

\begin{aligned}m_{2n} & = ĉ ∘ ∑_{r=0}^{n} r! \binom{n}{r}^{2}(2ĉ)^{r} ∘ H_{n−r}(1, ĉ) ∘ H_{n−r}(1, ĉ) = \\ & = ∑_{r=0}^{n} \binom{n}{r}^{2}2^{r}r!(n − r)! ∑_{s=0}^{⌊ \frac{n−r}{2} ⌋} \frac{m_{n−r}^{(r+s+1)}}{(n − r − 2s)!s!}, \end{aligned}  (15)

where

m_{n}^{(q)} = P_{n}^{(q)}(1, 1) = ĉ^{q} ∘ H_{n}(1, ĉ)  (16)

are associated Motzkin numbers [8].

The identification of Motzkin numbers as in Eq. (16), along with the use of the recurrences of Hermite polynomials, yields, e.g., the identities

\begin{matrix}m_{n+1}^{(q)} = m_{n}^{(q)} + 2 n m_{n−1}^{(q+1)}, \\ m_{n+p} = ∑_{s=0}^{min[n,p]} 2^{s}s! \binom{p}{s} \binom{n}{s}M_{p−s, n−s, s}, \\ M_{p, n, t} = p! ∑_{r=0}^{⌊ \frac{p}{2} ⌋} \frac{m_{n}^{(t+r+1)}}{(p − 2r)!r!}, \end{matrix}  (17)

in which the second identity has been derived from the Nielsen formula for H_{n+m}(x, y) [14].

3 Final comments

In this paper we have shown that a fairly straightforward extension of a formalism put forward in [8] permits non-trivial progress in the theory of Motzkin numbers. Further relations can be easily obtained by applying the method we have envisaged as, e.g.,

∑_{s=0}^{n} m_{n−s} m_{s} = 2 (n + 1) m_{n}^{(2)},  (18)

which represents a discrete self-convolution of Motzkin numbers.

The associated Motzkin numbers, originally introduced [8], have been defined here on purely algebraic grounds (see Eq. 16). Strictly speaking they are not integers and therefore they are not amenable to a combinatorial interpretation; however, redefining them as

m̃_{n}^{(q)} = \frac{(n + q)!}{n!}P_{n}^{(q)}(1, 1),  (19)

we obtain for q = 2 the sequences in OEIS \underline{A014531}, while for q = 3 the sequences \underline{A014532}, and so on.

A more appropriate interpretation in combinatorial terms can be obtained by following, e.g., the procedures indicated [15] and deserves further investigations, out of the scope of the present paper.

We have mentioned in the introduction the theory of telephone numbers T (n) [16, pp. 65– 67], whose importance in chemical graph theory has been recently emphasized [17]. As is well known, they can be expressed in terms of ordinary Hermite polynomials; however, the use of the two-variable extension is more effective. Indeed, they can be expressed as T (n) = H_{n}(1, \frac{1}{2}) .

The use of Hermite polynomial properties, such as the index duplication formula, yields

T (2n) = ∑_{r=0}^{n} \binom{n}{r}^{2} r! T (n − r)^{2}.  (20)

The use of the Hermite numbers h_{s} [18] allows the derivation of the following additional expression

\begin{matrix}T (n) = ∑_{s=0}^{n} t_{n,s}, \\ t_{n,s} = \binom{n}{s} h_{s} (\frac{1}{2}) , \\ h_{s}(y) = y^{\frac{s}{2}} Γ (\frac{s}{2} + 2) f_{s} = \frac{y^{\frac{s}{2}} s!}{Γ (\frac{s}{2} + 1)} |cos (s \frac{π}{2} )| . \end{matrix}  (21)

The coefficients t_{n,s} of the telephone numbers can be arranged in the following triangle, in which the numbers belonging to the column s = 4, (3, 15, 45, 105, 210, 378, …) are identified, in the OEIS, with the sequence \underline{A050534} and the column in s = 6, (15, 105, 420, 1260, 3150, …), with \underline{A240440}.

t_{n,s} coefficients  T (n) telephone numbers
Parameter  s  ∑_{s=0}^{n} t_{n,s}
0 1 2 3 4 5 6 7
n  0 1  1
1 1 0  1
2 1 0 1  2
3 1 0 3 0  4
4 1 0 6 0 3  10
5 1 0 10 0 15 0  26
6 1 0 15 0 45 0 15  76
7 1 0 21 0 105 0 105 0  232

Table 2: Telephone number coefficients

The use of the identification with two-variable Hermite polynomials opens further perspectives. By exploiting the polynomials (see [1, pp. 85–86] and references therein)

H_{n}^{(m)}(x, y) = n! ∑_{r=0}^{⌊ \frac{n}{m} ⌋} \frac{x^{n−mr}y^{r}}{(n − mr)!r!},  (22)

we can introduce the following generalization of telephone numbers

T_{n}^{(m)} = H_{n}^{(m)} (1, \frac{1}{m}) ,  (23)

with generating function

∑_{n=0}^{∞} \frac{t^{n}}{n!}T_{n}^{(m)} = e^{t+ \frac{1}{m} t^{m}},  (24)

which satisfy the recurrence

T_{n+1}^{(m)} = T_{n}^{(m)} + \frac{n!}{(n − m + 1)!}T_{n−m+1}^{(m)}.  (25)

In the case of m = 3 the numbers T_{n}^{(3)} = (1, 1, 1, 3, 9, 21, 81, 351, 1233, …) are identified with OEIS sequence \underline{A001470}, while for m = 4, the series (1, 1, 1, 1, 7, 31, 91, 211, 1681, 12097, …), corresponds to \underline{A118934}. For m = 5 the associated series appears to be \underline{A052501}, but should be more appropriately identified with the coefficients of the expansion (23). Finally the sequence m = 6 is not reported in OEIS.

A more detailed analysis of this family of numbers and the relevant interplay with Motzkin will be discussed elsewhere.

References

[1] J. Riordan, Introduction to Combinatorial Analysis, Dover, 2002.

[2] M. Artioli and G. Dattoli, Geometric interpretation of Perrin and Padovan numbers, Wolfram Demonstrations Project, Sept. 14, 2016. Available at

    https://tinyurl.com/ydhxuk2h.

[3] A. G. Shannon, P. G. Anderson, and A. F. Horadam, Properties of Cordonnier, Perrin and Van der Laan numbers, Internat. J. Math. Ed. Sci. Tech. 37 (2006), 825–831.

[4] R. Padovan, Dom Hans Van Der Laan and the Plastic Number, in Kim Williams and Jose Francisco Rodrigues, eds., Nexus IV: Architecture and Mathematics, Kim Williams Books, 2002, pp. 181–193.

[5] M. Artioli and G. Dattoli, Geometry of two-variable Legendre polynomials, Wolfram Demonstrations Project, Jan. 25, 2016. Available at https://tinyurl.com/ybrhlyou.

[6] F. R. Bernhart, Catalan, Motzkin, and Riordan numbers, Discrete Math. 204 (1999), 73–112.

[7] R. Donaghey and L. W. Shapiro, Motzkin numbers, J. Comb. Theory A 23 (1977), 291–301.

[8] P. Blasiak, G. Dattoli, A. Horzela, K. A. Penson, and K. Zhukovsky, Motzkin numbers, central trinomial coefficients and hybrid polynomials, J. Integer Sequences 11 (2008), Article 08.1.1.

[9] G. Dattoli, S. Lorenzutta, P. E. Ricci, and C. Cesarano, On a family of hybrid polynomials, J. Integral Transforms and Special Functions 15 (2004), 485–490.

[10] J.-L. Zhao and F. Qi, Two explicit formulas for the generalized Motzkin numbers, J. Inequal. Appl. (2017), Paper No. 44.

[11] G. Dattoli, E. di Palma, E. Sabia, K. Górska, A. Horzela, and K. A. Penson, Operational versus umbral methods and the Borel transform, Int. J. Appl. and Comput. Math. 3 (2017), 3489–3510.

[12] S. Roman, The theory of the umbral calculus, J. Math. Anal. Appl. 87 (1982), 1–58.

[13] L. C. Andrews, Special Functions for Engineers and Applied Mathematicians, Macmillan, 1985.

[14] N. Nielsen, Recherches sur les polynômes d’Hermite, Mathematisk-Fysiske Meddelelser 1 (1918), Det. Kgl. Danske Videnskabernes Selskab.

[15] C. Banderier, C. Krattenthaler, A. Krinik, D. Kruchinin, V. Kruchinin, D. Nguyen, and M. Wallner, Explicit formulas for enumeration of lattice paths: basketball and the kernel method, to appear in Dev. Math., Springer, 2017. Available at

http://www.mat.univie.ac.at/~kratt/artikel/basket.pdf.

[16] D. E. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching, Addison-Wesley, 1973.

[17] R. Hatz, M. Korpinen, V. Hanninen, and L. Halonen, Generalized intermolecular interaction tensor applied to long-range interactions in hydrogen and coinage metal (Cu, Ag, and Au) clusters, J. Phys. Chem. A 119 (2015), 11729–11736.

[18] G. Dattoli, B. Germano, M. R. Martinelli, and P. E. Ricci, Lacunary generating functions of Hermite polynomials and symbolic methods, Ilirias J. of Math. 4 (2015), 16–23.

2010 Mathematics Subject Classification: Primary 11B99; Secondary 33C45, 05A10, 47A05, 05A40. Keywords: Motzkin number, special functions, combinatorics, operator theory, umbral calculus.

(Concerned with sequences \underline{A000217}, \underline{A000910}, \underline{A001470}, \underline{A014531}, \underline{A014532}, \underline{A034827}, \underline{A050534}, \underline{A052501}, \underline{A118934}, and \underline{A240440}.)

Received February 26 2018; revised versions received May 16 2018; June 2 2018; August 25 2018. Published in Journal of Integer Sequences, August 26 2018.

Return to Journal of Integer Sequences home page.