A Relationship between the Partial Bell Polynomials and Alternating Run Polynomials

Yanan Feng, Zhe Wang

School of Mathematics and Statistics, Northeastern University at Qinhuangdao, Qinhuangdao, China.

DOI: 10.4236/ojdm.2023.132005                

Abstract

In this note, we first derive an exponential generating function of the alternating run polynomials. We then deduce an explicit formula of the alternating run polynomials in terms of the partial Bell polynomials.

Keywords

Alternating Run Polynomials, Bell Polynomials, Permutations

1. Introduction

Let ${\mathfrak{S}}_n$ be the symmetric group of all permutations of $\left[n\right]$ , where $\left[n\right]$ = {1, 2, … , $n$ }. An alternating run of a permutation $\sigma =\sigma \left(1\right)\sigma \left(2\right)\cdots \sigma \left(n\right)\in {\mathfrak{S}}_n$ is a continuous maximal monotone increasing or decreasing sequence. For example, the permutation 3175246 has four alternating runs 31, 17, 752 and 246. Let $R\left(n\mathrm{,}k\right)$ denote the number of permutations in ${\mathfrak{S}}_n$ with k alternating runs. The study of alternating runs of permutations was initiated by André [1] , who found that the numbers $R\left(n\mathrm{,}k\right)$ satisfy the recurrence relation

$R\left(n,k\right)=kR\left(n-1,k\right)+2R\left(n-1,k-1\right)+\left(n-k\right)R\left(n-1,k-2\right)$ (1)

for $n\mathrm{,}k\ge 1$ , where $R\left(\mathrm{1,0}\right)=1$ and $R\left(\mathrm{1,}k\right)=0$ for $k\ge 1$ . The reader is referred to [2] [3] [4] for the recent studies on this topic. For $n\ge 1$ , we define $R_n\left(x\right)={\displaystyle {\sum }_{k=1}^{n-1}}R\left(n,k\right)x^k$ . Then by using (1), one can deduce the following recurrence relation

$R_{n+2}\left(x\right)=x\left(nx+2\right)R_{n+1}\left(x\right)+x\left(1-x^2\right){R^{\prime }}_{n+1}\left(x\right),$ (2)

with initial value $R_1\left(x\right)=1$ . The first few terms of $R_n\left(x\right)$ ’s are given as follows:

$R_2\left(x\right)=2x,$

$R_3\left(x\right)=2x+4x^2,$

$R_4\left(x\right)=2x+12x^2+10x^3,$

$R_5\left(x\right)=2x+28x^2+58x^3+32x^4.$

In a series of papers [5] [6] [7] , Carlitz studied the generating functions for the numbers $R\left(n\mathrm{,}k\right)$ . In particular, Carlitz [5] proved that

${\displaystyle \underset{n=0}{\overset{\infty }{\sum }}}\frac{z^n}{n!}{\displaystyle \underset{k=0}{\overset{n}{\sum }}}R\left(n+1,k\right)x^{n-k}=\frac{1-x}{1+x}{\left(\frac{\sqrt{1-x^2}+\sin \left(z\sqrt{1-x^2}\right)}{x-\cos \left(z\sqrt{1-x^2}\right)}\right)}^2.$ (3)

As a dual of (3), the first result of this note is the following.

Theorem 1. Let $R\left(x,t\right)={\displaystyle {\sum }_{n=0}^{\infty }}{R}_{n+1}\left(x\right)\frac{t^n}{n!}$ , we have

$R\left(x\mathrm{,}t\right)=\frac{\left(x-1\right)\left(1+\cosh z\right)}{\left(x+1\right)\left(1-\cosh z\right)},$

where $z=\text{arccosh}\left(\frac{1}{x}\right)-t\sqrt{1-x^2}$ .

Let ${\left\{x_i\right\}}_{n\ge 1}$ be a sequence of variables. The partial Bell polynomials $B_{n,k}=:$ $B_{n,k}\left(x_1,x_2,\cdots ,x_{n-k+1}\right)$ are defined by the generating function

${\displaystyle \underset{n\ge k}{\sum }}{B}_{n,k}\frac{t^n}{n!}=\frac{1}{k!}{\left({\displaystyle \underset{i\ge 1}{\sum }}{x}_i\frac{t^i}{i!}\right)}^k,$

or equivalently defined by the series expansion

$\exp \left(u{\displaystyle \underset{j\ge 1}{\sum }}{x}_j\frac{t^j}{j!}\right)=1+{\displaystyle \underset{n\ge 1}{\sum }}\frac{t^n}{n!}{\displaystyle \underset{k=1}{\overset{n}{\sum }}}{u}^k{B}_{n,k}\left(x_1,x_2,\cdots ,x_{n-k+1}\right),$

with $B_{0,0}=1$ and $B_{n,0}=0$ for $n>0$ . We refer the reader to [8] [9] [10] for some applications of the partial Bell polynomials.

Corollary 1. Let $B_{n\mathrm{,}k}$ be the partial Bell polynomials. When $x_i={\left(1-x^2\right)}^{\lfloor \left(i-1\right)/2\rfloor }$ for each $i\ge 1$ , we have

$R_{n+1}\left(x\right)=2x{\displaystyle \underset{k=1}{\overset{n}{\sum }}}{\left(-1\right)}^{n-k}k!{\left(1+x\right)}^{k-1}{B}_{n,k}.$

Proof. Let $z=\text{arccosh}\left(1/x\right)-t\sqrt{1-x^2}$ . By Theorem 1, we get

$x\left(\cosh z-1\right)$

$\begin{array}{l}=\cosh \left(-t\sqrt{1-x^2}\right)+x\sinh \left(-t\sqrt{1-x^2}\right)\sinh \left(\text{arccosh}\left(1/x\right)\right)-x\\ =\frac{1}{2}\left({\text{e}}^{-t\sqrt{1-x^2}}+{\text{e}}^{t\sqrt{1-x^2}}\right)+\frac{\sqrt{1-x^2}}{2}\left({\text{e}}^{-t\sqrt{1-x^2}}-{\text{e}}^{t\sqrt{1-x^2}}\right)-x\\ =1-x+{\displaystyle \underset{i=1}{\overset{\infty }{\sum }}}{\left(-1\right)}^i{y}_i\frac{t^i}{i\mathrm{<mo>\; !\; </mo>}}\mathrm{,}\end{array}$

where $y_i={\left(1-x^2\right)}^{\lfloor \left(i+1\right)/2\rfloor }.$ Therefore,

$\begin{array}{c}R\left(x,t\right)=\frac{\left(x-1\right)\left(1+\cosh z\right)}{\left(x+1\right)\left(1-\cosh z\right)}=\frac{1-x}{1+x}\left(1+\frac{2x}{x\left(\cosh z-1\right)}\right)\\ =\frac{1-x}{1+x}\left(1+\frac{2x}{1-x+{\displaystyle \underset{i=1}{\overset{\infty }{\sum }}}{\left(-1\right)}^i{y}_i\frac{t^i}{i!}}\right)\\ =\frac{1-x}{1+x}+\frac{2x}{1+x}{\displaystyle \underset{k=0}{\overset{\infty }{\sum }}}{\left(-1\right)}^k{\left(1+x\right)}^k{\left({\displaystyle \underset{i\ge 1}{\sum }}{\left(-1\right)}^i{x}_i\frac{t^i}{i!}\right)}^k,\end{array}$

where $x_i={\left(1-x^2\right)}^{\lfloor \left(i-1\right)/2\rfloor }$ , and the desired result follows immediately.

In the next section, we first prove Theorem 1 and then give an explicit formula of $R_n\left(x\right)$ .

2. The Proof of Theorem 1 and an Explicit Formula of $R_n(\; x\; )$

A proof Theorem 1:

Proof. Multiplying both sides of (2) by $\frac{t^n}{n\mathrm{<mo>\; !\; </mo>}}$ and summing over all $n\ge 0$ , we get

$\frac{\partial R\left(x\mathrm{,}t\right)}{\partial t}=t{x}^2\frac{\partial R\left(x\mathrm{,}t\right)}{\partial t}+2xR\left(x\mathrm{,}t\right)+\left(x-x^3\right)\frac{\partial R\left(x\mathrm{,}t\right)}{\partial x}\mathrm{.}$

Hence

$\left(x-x^3\right)\frac{\partial R\left(x,t\right)}{\partial x}+\left(t{x}^2-1\right)\frac{\partial R\left(x,t\right)}{\partial t}=-2xR\left(x,t\right).$

This is a non-homogeneous linear partial differential equation, and the corresponding characteristic equation is

$\frac{\text{d}x}{x-x^3}=\frac{\text{d}t}{t{x}^2-1}=\frac{\text{d}R\left(x\mathrm{,}t\right)}{-2xR\left(x\mathrm{,}t\right)}\mathrm{.}$

It is easy to find that its two independent initial integrals are

$\text{arccosh}\left(\frac{1}{x}\right)-t\sqrt{1-x^2}=c_1\mathrm{,}\frac{x+1}{x-1}R\left(x\mathrm{,}t\right)=c_2\mathrm{.}$

Since $R\left(x,0\right)=R_1\left(x\right)=1$ , we have

$c_2=\frac{1+\cosh c_1}{1-\cosh c_1}\mathrm{,}$

which yields the desired formula.

Theorem 2. Let $b>a>0$ be two constants. When $x_i={\left(\frac{a}{b}\right)}^{\lfloor \left(i-1\right)/2\rfloor }$ for each $i\ge 1$ , we have

$B_{n,k}\left(1,1,\frac{a}{b},\frac{a}{b},\cdots ,{\left(\frac{a}{b}\right)}^{\lfloor \frac{n-k}{2}\rfloor }\right)$

$=\frac{{\left(-1\right)}^k}{k!}{\left(\frac{a}{b}\right)}^{\frac{n}{2}-k}{\displaystyle \underset{l=0}{\overset{k}{\sum }}}\left(\begin{array}{c}k\\ l\end{array}\right){\left(-\frac{\sqrt{b-a}}{2\sqrt{b}}\right)}^l{\displaystyle \underset{q=0}{\overset{l}{\sum }}}\left(\begin{array}{c}l\\ q\end{array}\right){\left(2q-l\right)}^n{\left(\frac{\sqrt{b}+\sqrt{a}}{\sqrt{b-a}}\right)}^{2q-l}.$ (4)

Proof. By the definition of partial bell polynomial, let $x_i={\left(\frac{a}{b}\right)}^{\lfloor \left(i-1\right)/2\rfloor }$ have

${\displaystyle \underset{n\ge k}{\sum }}{B}_{n,k}\left(1,1,\frac{a}{b},\frac{a}{b},\cdots ,{\left(\frac{a}{b}\right)}^{\lfloor \frac{n-k}{2}\rfloor }\right)\frac{t^n}{n!}$

$\begin{array}{l}=\frac{1}{k!}{\left[{\displaystyle \underset{i\ge 1}{\sum }}{\left(\frac{a}{b}\right)}^{\lfloor \frac{i-1}{2}\rfloor }\frac{t^i}{i!}\right]}^k=\frac{1}{k!}{\left[\frac{\sqrt{b}\sinh \left(\frac{\sqrt{a}}{\sqrt{b}}t\right)}{\sqrt{a}}+\frac{b\cosh \left(\frac{\sqrt{a}}{\sqrt{b}}t\right)}{a}-\frac{b}{a}\right]}^k\\ =\frac{{\sqrt{b}}^k}{k!a^k}{\left[\sqrt{a}\sinh \left(\frac{\sqrt{a}}{\sqrt{b}}t\right)+\sqrt{b}\cosh \left(\frac{\sqrt{a}}{\sqrt{b}}t\right)-\sqrt{b}\right]}^k\\ =\frac{{\sqrt{b}}^k}{k!a^k}{\left[\sqrt{b-a}\cosh \left(\frac{\sqrt{a}}{\sqrt{b}}t+\ln \frac{\sqrt{a}+\sqrt{b}}{\sqrt{b-a}}\right)-\sqrt{b}\right]}^k\\ =\frac{{(-1)}^k}{k!}{\left(\frac{b}{a}\right)}^k{\displaystyle \underset{l=0}{\overset{k}{\sum }}}\left(\begin{array}{c}k\\ l\end{array}\right){\left(\frac{\sqrt{b-a}}{\sqrt{b}}\right)}^l{\left(-1\right)}^l{\cosh }^l\left(\frac{\sqrt{a}}{\sqrt{b}}t+\ln \frac{\sqrt{a}+\sqrt{b}}{\sqrt{b-a}}\right).\end{array}$

Note that

${\cosh }^l\left(\alpha t+\beta \right)=\frac{1}{2^l}{\left({\text{e}}^{\left(\alpha t+\beta \right)}+{\text{e}}^{\left(\alpha t+\beta \right)}\right)}^l=\frac{1}{2^l}{\displaystyle \underset{q=0}{\overset{l}{\sum }}}\left(\begin{array}{c}l\\ q\end{array}\right){\text{e}}^{q\left(\alpha t+\beta \right)}{\text{e}}^{-\left(l-q\right)\left(\alpha t+\beta \right)}.$

So we get

${\cosh }^l\left(\alpha t+\beta \right)=\frac{1}{2^l}{\displaystyle \underset{q=0}{\overset{l}{\sum }}}\left(\begin{array}{c}l\\ q\end{array}\right){\text{e}}^{\left(2q-l\right)\left(\alpha t+\beta \right)}\mathrm{.}$

It is clear that

$\frac{{\text{d}}^m{\cosh }^l\left(\alpha t+\beta \right)}{\text{d}{t}^m}=\frac{1}{2^l}{\displaystyle \underset{q=0}{\overset{l}{\sum }}}\left(\begin{array}{c}l\\ q\end{array}\right){\left(2q-l\right)}^m{\alpha }^m{\text{e}}^{\left(2q-l\right)\left(\alpha t+\beta \right)}\mathrm{.}$

Differentiating the both sides of the following expression with respect to t,

${\displaystyle \underset{n\ge k}{\sum }}{B}_{n,k}\left(1,1,\frac{a}{b},\frac{a}{b},\cdots ,{\left(\frac{a}{b}\right)}^{\lfloor \frac{n-k}{2}\rfloor }\right)\frac{t^n}{n!}$

$=\frac{{\left(-1\right)}^k}{k!}{\left(\frac{b}{a}\right)}^k{\displaystyle \underset{l=0}{\overset{k}{\sum }}}\left(\begin{array}{c}k\\ l\end{array}\right){\left(\frac{\sqrt{b-a}}{\sqrt{b}}\right)}^l{\left(-1\right)}^l{\cosh }^l\left(\frac{\sqrt{a}}{\sqrt{b}}t+\ln \frac{\sqrt{a}+\sqrt{b}}{\sqrt{b-a}}\right),$

we arrive at

${\displaystyle \underset{n\ge k}{\sum }}{B}_{n,k}\left(1,1,\frac{a}{b},\frac{a}{b},\cdots ,{\left(\frac{a}{b}\right)}^{\lfloor \frac{n-k}{2}\rfloor }\right)\frac{t^{n-m}}{\left(n-m\right)!}$

$\begin{array}{l}=\frac{{\left(-1\right)}^k}{k!}{\left(\frac{b}{a}\right)}^k{\displaystyle \underset{l=0}{\overset{k}{\sum }}}\left(\begin{array}{c}k\\ l\end{array}\right){\left(\frac{\sqrt{b-a}}{\sqrt{b}}\right)}^l{\left(-1\right)}^k{}^l\frac{d^m{\cosh }^l\left(\frac{\sqrt{a}}{\sqrt{b}}t+\ln \frac{\sqrt{a}+\sqrt{b}}{\sqrt{b-a}}\right)}{d{t}^m}\\ =\frac{{\left(-1\right)}^k}{k!}{\left(\frac{b}{a}\right)}^k{\displaystyle \underset{l=0}{\overset{k}{\sum }}}\left(\begin{array}{c}k\\ l\end{array}\right){\left(\frac{\sqrt{b-a}}{\sqrt{b}}\right)}^l{\left(-1\right)}^k{}^l\frac{1}{2^l}{\displaystyle \underset{q=0}{\overset{l}{\sum }}}\left(\begin{array}{c}l\\ q\end{array}\right){\left(2q-l\right)}^m{\left(\frac{\sqrt{a}}{\sqrt{b}}\right)}^m\\ \cdot \exp \left[\left(2q-l\right)\left(\frac{\sqrt{a}}{\sqrt{b}}t+\ln \frac{\sqrt{a}+\sqrt{b}}{\sqrt{b-a}}\right)\right].\end{array}$

Taking the limit $t\to 0$ , we get the desired result.

According to Corollary 1, we know that the coefficients of the corresponding Bell polynomials should be real numbers, so if formula (4) satisfies the conditions and is meaningful, we need to make $a>0$ , $b>0$ and $\sqrt{b-a}>0$ . Therefore, we can obtain $b>a>0$ .

Set $\frac{a}{b}=1-x^2$ . Then

$-\frac{\sqrt{b-a}}{2\sqrt{b}}=-\frac{1}{2}\sqrt{1-\frac{a}{b}}=-\frac{x}{2},$

$\frac{\sqrt{b}+\sqrt{a}}{\sqrt{b-a}}=\frac{1-\sqrt{\frac{a}{b}}}{1-\sqrt{\frac{a}{b}}}=\frac{1+\sqrt{1-x^2}}{x}.$

Combining Corollary 1 and Theorem 2, we get the following result.

Corollary 2. We have

$\begin{array}{c}{R}_{n+1}\left(x\right)=2x{\displaystyle \underset{k=1}{\overset{n}{\sum }}}{\left(-1\right)}^n{\left(x+1\right)}^{k-1}{\left(\frac{1}{1-x^2}\right)}^{k-\frac{n}{2}}{\displaystyle \underset{l=0}{\overset{k}{\sum }}}\left(\begin{array}{c}k\\ l\end{array}\right)\left(-\frac{x}{2}\right)\\ \times {\displaystyle \underset{q=0}{\overset{l}{\sum }}}\left(\begin{array}{c}l\\ q\end{array}\right){\left(2q-l\right)}^n{\left(\frac{1+\sqrt{1-x^2}}{x}\right)}^{2q-l}.\end{array}$ (5)

We note that the explicit formula of $R_{n+1}\left(x\right)$ given by Corollary 2 is very useful. With the use of formula (5), we can directly calculate the value of $R\left(n\mathrm{,}k\right)$ for any given n and k, rather than relying on the recurrence relation. Here we provide an example to illustrate the application of Corollary 2, where all calculations are obtained using Mathematica 12.1.

Example 3. Let

$W_{n,k}={\displaystyle \underset{l=0}{\overset{k}{\sum }}}\left(\begin{array}{c}k\\ l\end{array}\right){\left(-\frac{x}{2}\right)}^l{\displaystyle \underset{q=0}{\overset{l}{\sum }}}\left(\begin{array}{c}l\\ q\end{array}\right){\left(2q-l\right)}^n{\left(\frac{1+\sqrt{1-x^2}}{x}\right)}^{2q-l}.$

Consider the case $1\le n\le 4$ , we have

$\begin{array}{l}{W}_{1,1}=-\sqrt{1-x^2};\\ W_{2,1}=-1,W_{2,2}=2-2x^2;\\ W_{3,1}=-\sqrt{1-x^2},W_{3,2}=6\sqrt{1-x^2},W_{3,3}=-6{\left(1-x^2\right)}^{3/2};\\ W_{4,1}=-1,W_{4,2}=14-8x^2,W_{4,3}=36\left(-1+x^2\right),W_{4,4}=24{\left(-1+x^2\right)}^2.\end{array}$

Thus

$\begin{array}{l}{R}_2\left(x\right)=-2x{\displaystyle \underset{k=1}{\overset{1}{\sum }}}{\left(x+1\right)}^{k-1}{\left(\frac{1}{1-x^2}\right)}^{k-\frac{1}{2}}{W}_{1,k}=2x;\\ R_3\left(x\right)=2x{\displaystyle \underset{k=1}{\overset{2}{\sum }}}{\left(x+1\right)}^{k-1}{\left(\frac{1}{1-x^2}\right)}^{k-1}{W}_{2,k}=2x+4x^2;\\ R_4\left(x\right)=-2x{\displaystyle \underset{k=1}{\overset{3}{\sum }}}{\left(x+1\right)}^{k-1}{\left(\frac{1}{1-x^2}\right)}^{k-\frac{3}{2}}{W}_{3,k}=2x+12x^2+10x^3;\\ R_5\left(x\right)=2x{\displaystyle \underset{k=1}{\overset{4}{\sum }}}{\left(x+1\right)}^{k-1}{\left(\frac{1}{1-x^2}\right)}^{k-2}{W}_{4,k}=2x+28x^2+58x^3+32x^4.\end{array}$

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	André, D. (1884) étude sur les maxima, minima et séquences des permutations. Annales Scientifiques de L’école Normale Supérieure, 3, 121-134. https://doi.org/10.24033/asens.235
[2]	Bóna, M. and Ehrenborg, R. (2000) A Combinatorial Proof of the Log-Concavity of the Numbers of Permutations with k Runs. Journal of Combinatorial Theory, Series A, 90, 293-303. https://doi.org/10.1006/jcta.1999.3040
[3]	Bóna, M. (2012) Combinatorics of Permutations. CRC Press, Boca Raton.
[4]	Ma, S.-M., Ma, J. and Yeh, Y.-N. (2010) David-Barton Type Identities and the Alternating Run Polynomials. Advances in Applied Mathematics, 114, 101978. https://doi.org/10.1016/j.aam.2019.101978
[5]	Carlitz, L. (1978) Enumeration of Permutations by Sequences. Fibonacci Quart, 16, 259-268.
[6]	Carlitz, L. (1980) The Number of Permutations with a Given Number of Sequences. Fibonacci Quart, 18, 347-352.
[7]	Carlitz, L. (1981) Enumeration of Permutations by Sequences II. Fibonacci Quart, 19, 398-406.
[8]	Qi, F. and Zheng, M.M. (2015) Explicit Expressions for a Family of the Bell Polynomials and Applications. Applied Mathematics and Computation, 258, 597-607. https://doi.org/10.1016/j.amc.2015.02.027
[9]	Qi, F., Shi, X.T., Liu, F.F. and Guo, B.-N. (2017) Several Formulas for Special Values of the Bell Polynomials of the Second Kind and Applications. Journal of Applied Analysis and Computation, 7, 857-871.
[10]	Qi, F., Niu, D.-W., Lim, D. and Guo, B.-N. (2020) Closed Formulas and Identities for the Bell Polynomials and Falling Factorials. Contributions to Discrete Mathematics, 15, 163-174.