A Relationship between the Partial Bell Polynomials and Alternating Run Polynomials ()
1. Introduction
Let
be the symmetric group of all permutations of
, where
= {1, 2, … ,
}. An alternating run of a permutation
is a continuous maximal monotone increasing or decreasing sequence. For example, the permutation 3175246 has four alternating runs 31, 17, 752 and 246. Let
denote the number of permutations in
with k alternating runs. The study of alternating runs of permutations was initiated by André [1] , who found that the numbers
satisfy the recurrence relation
(1)
for
, where
and
for
. The reader is referred to [2] [3] [4] for the recent studies on this topic. For
, we define
. Then by using (1), one can deduce the following recurrence relation
(2)
with initial value
. The first few terms of
’s are given as follows:
In a series of papers [5] [6] [7] , Carlitz studied the generating functions for the numbers
. In particular, Carlitz [5] proved that
(3)
As a dual of (3), the first result of this note is the following.
Theorem 1. Let
, we have
where
.
Let
be a sequence of variables. The partial Bell polynomials
are defined by the generating function
or equivalently defined by the series expansion
with
and
for
. We refer the reader to [8] [9] [10] for some applications of the partial Bell polynomials.
Corollary 1. Let
be the partial Bell polynomials. When
for each
, we have
Proof. Let
. By Theorem 1, we get
where
Therefore,
where
, and the desired result follows immediately.
In the next section, we first prove Theorem 1 and then give an explicit formula of
.
2. The Proof of Theorem 1 and an Explicit Formula of
A proof Theorem 1:
Proof. Multiplying both sides of (2) by
and summing over all
, we get
Hence
This is a non-homogeneous linear partial differential equation, and the corresponding characteristic equation is
It is easy to find that its two independent initial integrals are
Since
, we have
which yields the desired formula.
Theorem 2. Let
be two constants. When
for each
, we have
(4)
Proof. By the definition of partial bell polynomial, let
have
Note that
So we get
It is clear that
Differentiating the both sides of the following expression with respect to t,
we arrive at
Taking the limit
, 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
,
and
. Therefore, we can obtain
.
Set
. Then
Combining Corollary 1 and Theorem 2, we get the following result.
Corollary 2. We have
(5)
We note that the explicit formula of
given by Corollary 2 is very useful. With the use of formula (5), we can directly calculate the value of
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
Consider the case
, we have
Thus