Integer Composition, Connection Appell Constants and Bell polynomials

Nataliia Luno$^\ast $

October 10, 2021; accepted: November 26, 2021; published online: February 17, 2022.

We introduce an explicit form of the connection coefficients for Appell polynomial sequences via Toeplitz-Hessenberg matrix determinants. Generalising, we give an explicit form of the connection coefficients for arbitrary polynomial sequences and explain the combinatorial meaning of both constants in terms of integer composition.

MSC. 54AXX.

Keywords. Appell polynomials, generating functions, connection coefficients, integer composition, connection problems, Bell polynomials.

$^\ast $Faculty of Mathematics and Computer Sciences, Vasyl’ Stus Donetsk University, 21, 600-richchia Street, 21021, Vinnytsia, Ukraine, e-mail: nlunio@ukr.net.

1 Introduction

In [ 3 ] , P. Appell introduced polynomials $A_n(x)$ defined by the exponential generating function

\begin{equation} \label{gen_Ap} \exp (xt)A(t)= \sum _{n=0}^{\infty } A_n(x)\tfrac {t^n}{n!}, \end{equation}

where $A(t)$ is a formal power series

\begin{equation} A(t)= \sum _{n=0}^{\infty } a_n \tfrac {t^n}{n!}, \: \: a_0\neq 0, \end{equation}

which are known as the Appell polynomials today.

Besides, it was shown there exists a one-to-one correspondence in the form

\begin{equation} \label{n_poly} A_n(x)= \textstyle {n \choose 0}a_{n} x^0 + {n \choose 1}a_{n-1}x^1 + {n \choose 2}a_{n-2}x^2 +\dots + {n \choose n}a_0 x^n. \end{equation}

We call the formal power series $A(t)$ the transfer sequence of the Appell sequence $\{ A_n(x)\} _{n\geq 0}.$

Throughout the text, we will use the equivalent for transfer sequence in the form

\begin{equation} \label{tvirna} A(t)= \sum _{n=0}^{\infty } a_n {t^n}, \: \: a_0\neq 0, \end{equation}

whence

\begin{equation} \label{n_poly} A_n(x)= \sum _{i=0}^{n} \textstyle {n \choose i}(n-i)!a_{n-i} x^i. \end{equation}

The classical Appell polynomials include the monomials, the Bernoulli polynomials, the Euler polynomials, the Hermite polynomials. All of them, in turn, participate in a big number of modern generalisations such as the Bernoulli-Apostol polynomials, the Euler-Apostol polynomials, the Gould-Hopper polynomials, the generalised hypergeometric Appell polynomials, etc.

The Appell polynomials is a special case of the Sheffer polynomials, basic properties of the latter were widely studied in [ 22 ] from the point of view of the umbral calculus. Nowdays, the Appell polynomials are of great interest again, new modifiers of the existing definitions and properties are proposed, for instance, the Dattoli’s school [ 12 ] is focused on the realisation of the Wheyle algebras with special functions, matrix [ 1 ] and determinantal approaches [ 2 ] came out as well. As a consequence, new polynomial and combinatorial identities are obtained [ 10 , 19 , 20 , 5 ] .

For two given arbitrary polynomial sequences $\{ p_n(x)\} $ and $\{ q_n(x)\} $ of degree $n,$ each member of every sequence can be expressed as a linear combination of the second one:

\begin{equation} \label{Con_prob} p_n(x)=\sum _{k=0}^n c_k(n)q_k(x). \end{equation}

We call expression ?? the connection problem for polynomial sequences ${\{ }{{{p}}}_{n}({}{{{x}}}){\} }$ and $\{ q_n(x)\} .$ The unknown numbers $c_k(n)$ that need to be found are called the connection coefficients or the connection constants.

When $p_n(x)=x^n,$ the connection problem ?? is called the inverse problem:

\begin{equation} \label{Inv_prob} x^n=\sum _{k=0}^n c_k(n)q_k(x). \end{equation}

In literature, large variety of methods are proposed to solve the connection problem, and choosing the proper method depends on what special classes both sequences belong to. Great amount of solutions were constructed considering the classical orthogonal polynomials, we only mention the ones based on NaViMa and other algorithms [ 16 , 14 , 25 ] or on the generalised hypergeometric function [ 15 ] . Sometimes the results obtained by the recurrence methods are recurrent themselves [ 24 , 13 ] .

The explicit form of several connection problem solutions (the Laguerre polynomials, the Abel polynomials, the Gould polynomials, the falling and the rising factorials, etc.) was presented in the fundamental article by Roman and Rota [ 22 ] .

Here, we will use the results on Appell polynomials presented in [ 11 ] .

Theorem 1 Cheikh and Chaggara

Given two Appell sequences $p_n(x),$ $deg\left( p_n\right)=n,$ and $q_n(x),$ $deg\left( q_n\right)=n,$ with transfer sequences $A(t)$ and $B(t),$ respectively, the solution of the connection problem ?? has the form

\begin{equation} p_n(x)=\sum _{i=0}^n \tfrac {n!}{(n-i)!}c_{i}q_{n-i}(x), \textit{ where } \: {\tfrac {A(t)}{B(t)}=\sum _{i=0}^{\infty } c_it^i}. \end{equation}

Recently, independently from the Cheikh and Chaggara, in [ 9 ] , the authors presented the Sheffer and Appell families linear functionals based on the inverse problem closed form solution.

The aim of this paper is to give an explicit form of the connection coefficients for the Appell sequences, together with generalizing it to an arbitrary polynomial sequences. We also give the combinatorial interpretation of the results based on integer compositions and discuss arising related questions, i.e., relations between the Toeplitz-Hessenberg matrices determinants and the classical Bell polynomials.

2 Appell connection coefficients

2.1 Formal power series

It is known, that that formal power series 4 has a unique multiplicative inverse ${\frac{1}{A(t)}=A^{-1}(t)}$ if and only if $a \neq 0.$ The explicit formula was firstly discovered by Brioshi [ 8 ] in 1858 and is re-discovered by different researchers from time to time.

Transforming 4,

\begin{multline} \label{Ob_Rec} {\tfrac {1}{A(t)}}= {\left(1+\sum _{n=0}^{\infty } a_n {t^n}\right)}^{-1}= \sum _{m=0}^{\infty } {(-1)}^{m}{\left(1+\sum _{n=0}^{\infty } a_n {t^n}\right)}^{m}= \\ {=\sum _{i=0}^{\infty } \sum _{\substack {m_1, \ldots , m_n {\gt} 0, \\ \begin{bgroup} m_1+2m_2+\ldots +im_i=i \end{bgroup}}} {(-1)}^{m_1+\ldots + m_n}\binom {m_1+ \ldots + m_i}{m_1, \ldots , m_n}a_1^{m_1}\ldots a_i^{m_i} t^i } \end{multline}

The inner sum is precisely the expanded expression of an arbitrary $n$-th order determinant

\begin{gather} \label{detA} \sum _{\sigma \in S_n} \epsilon (\sigma )a_1^{\sigma (1)}\ldots a_n^{\sigma (n)} {\displaystyle =\sum _{\sigma _{1}, \sigma _{2},\ldots ,\sigma _{n}}(-1)^{N(\sigma _{1}\sigma _{2}\ldots \sigma _{n})}\cdot a_{1}^{\sigma _{1}}}\dots a_{n}^{\sigma _{n}}, \end{gather}

where permutations ${\displaystyle \sigma _{1},\sigma _{2},\ldots ,\sigma _{n}}$ belong to ${\displaystyle S_1,S_2,\dots , S_n,}$ respectively, and ${\displaystyle N(\sigma _{1}\sigma _{2}\ldots \sigma _{n})}$ denotes the number of inversions in ${\displaystyle \sigma _{1}\sigma _{2}\ldots \sigma _{n}}.$

The explicit form of the determinant 12 is given (see, e.g., [ 18 ] ) by one of the following expressions

\begin{gather} \label{ast} {\delta }_{n+1}= \left| \begin{array}{ccccccccc} 0 & a_1 & a_2 & \ldots & a_{i-2} & a_{i-1} & a_i\\ 0 & a_0 & a_1 & \ldots & a_{i-3} & a_{i-2} & a_{i-1}\\ 0 & 0 & a_0 & \ldots & a_{i-4} & a_{i-3} & a_{i-2}\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & 0 & \ldots & a_0 & a_1 & a_2 \\ 0 & 0 & 0 & \ldots & a_0 & a_1 \\ 1 & 0 & 0 & \ldots & 0 & a_0 \end{array} \right|, \end{gather}

or, equivalently, as the $n$-th order determinant of a Toeplitz-Hessenberg matrix

\begin{gather*} {\delta }_n= \tfrac {{(-1)}^n}{a_0^{n+1}} \left| \begin{array}{ccccccccc} a_1 & a_2 & \ldots & a_{i-2} & a_{i-1} & a_i\\ a_0 & a_1 & \ldots & a_{i-3} & a_{i-2} & a_{i-1}\\ 0 & a_0 & \ldots & a_{i-4} & a_{i-3} & a_{i-2}\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ 0 & 0 & \ldots & a_0 & a_1 & a_2 \\ 0 & 0 & \ldots & 0 & a_0 & a_1 \\ \end{array} \right|. \end{gather*}

We gather all previous statements into

Lemma 2

The formal power series 4 inverse has the following explicit form

\begin{equation} \tfrac {1}{A(t)}=\sum _{n=0}^{\infty }a_n^{\ast } t^n, \textit{where \: } a_0^{\ast }=1 \: \textit{and \: } a_i^{\ast }={\delta }_{i+1} \textit{are defined by \eqref{detA}}. \end{equation}

Some first inverse coefficients are listed below.

\begin{gather*} \begin{array}{ccccccccc} a_0^{\ast }=1,\\ a_1^{\ast }=-a_1,\\ a_2^{\ast }=a_1^2-a_2,\\ a_3^{\ast }=-a_1^3+2a_2a_1-a_3,\\ a_4^{\ast }=a_1^4-3a_2a_1^2+2a_3a_1+a_2^2-a_4,\\ a_5^{\ast }=-a_1^5+4a_1^3a_2-3a_1^2a_3-3a_1a_2^2+2a_1a_4+2a_2a_3-a_5.\\ \end{array}\end{gather*}

Recall, division of two formal power series $\frac{B(t)}{A(t)}$ is defined as a product $B(t)A^{-1}(t)$ if $A^{-1}(t)$ exists.

For $A(t)=\sum _{n=0}^{\infty } a_n t^n, a_0=1$ and $B(t)=\sum _{n=0}^{\infty }b_nt^n,$ we denote $C(t)=\frac{B(t)}{A(t)}=\sum _{=0}^{\infty }c_it^i,$ then ${{\frac{1}{A(t)}}}=\sum _{n=0}^{\infty } a_n^{\ast } t^n$ and, with the Cauchy formula,

\begin{gather*} C(t)=B(t)\tfrac {1}{A(t)}= \sum _{n=0}^{\infty }b_nt^n \cdot \sum _{n=0}^{\infty } a_n^{\ast } t^n= \sum _{n=0}^{\infty } \left( \sum _{p=0}^{n} b_{n-p}a^{\ast }_p \right)\: t^n. \end{gather*}

Considering the expressions 13 for $a^{\ast }_p$ and the properties of the determinants, we obtain

\begin{gather} \label{determin} c_0=1, c_n= \displaystyle \tfrac {1}{a_0^{p+1}} \left| \begin{array}{cccccccc} b_p & a_1 & a_2 & \ldots & a_{p-2} & a_{p-1} & a_p\\ b_{p-1} & a_0 & a_1 & \ldots & a_{p-3} & a_{p-2} & b_{p-1}\\ b_{p-2} & 0 & a_0 & \ldots & a_{p-4} & a_{p-3} & b_{p-2}\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ b_2 & 0 & 0 & \ldots & a_0 & a_1 & a_2 \\ b_1 & 0 & 0 & \ldots & 0 & a_0 & a_1 \\ b_0 & 0 & 0 & \ldots & 0 & 0 & a_0 \end{array} \right|. \end{gather}

Some first ratio coefficients are listed below.

\begin{gather*} \begin{array}{ccccccccc} c_0=1,\\ c_1=-a_1+_1,\\ c_2=a_1^2-a_1b_1-a_2+b_2,\\ c_3=-a_1^3+a_1^2b_1+2a_2a_1-a_1b_2-a_2b_1-a_3+b_3,\\ c_4^{\ast }=a_1^4-a_1^3b_1-3a_1^2a_2+a_1^2b_2+2a_1a_2b_1+2a_3a_1-a_1b_3+a_2^2-a_2b_2-\\ -a_3b_1-a_4+b_4. \end{array}\end{gather*}

2.2 Connection constants

Thus, we derive the explicit form of two arbitrary formal power series ratio.

Lemma 3

The ratio coefficients $c_i$ of two given formal power series $A(t)=\sum _{n=0}^{\infty } a_n t^n, a_0 \neq 0$ and $B(t)=\sum _{n=0}^{\infty }b_nt^n$ are defined by formulas 15.

Now, connection Appell coefficients are specified as follows.

Theorem 4

Given two Appell families $p_n(x)$ and $q_n(x)$ such that $\operatorname {deg}{\left( p_n\right)}{=}$ $=\operatorname { deg}\left( q_n\right)=n,$ with transfer sequences $A(t)$ and $B(t),$ respectively,

$(i)$ solution of inverse problem for $A_n(x)$ has the form

\begin{equation} x^i=\sum _{i=0}^n \tfrac {n!}{(n-i)!}a^{\ast }_{i}A_{n-i}(x), \end{equation}
16

where connection constants $a_i^{\ast }$ are defined by lemma 2;
$(ii)$ solution of their connection problem has the form

\begin{equation} \label{conap} B_n(x)=\sum _{i=0}^n \tfrac {n!}{(n-i)!}c_{i}A_{n-i}(x), \end{equation}
17

where connection constants $c_i$ are defined by lemma 3.

The proof comes from theorem 1, lemma 2 and lemma 3.

Example 5

Considering two equal formal power series with $a_i=b_i$ for all $i \geq 0$, according to theorem 4 we have

\begin{gather*} c_0=1,c_i= \tfrac {1}{a_0^{i+1}} \left| \begin{array}{cccccccc} b_i & b_1 & _2 & \ldots & b_{i-2} & b_{i-1} & _i\\ b_{i-1} & b_0 & b_1 & \ldots & b_{i-3} & b_{i-2} & b_{i-1}\\ b_{i-2} & 0 & b_0 & \ldots & b_{i-4} & b_{i-3} & b_{i-2}\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ b_2 & 0 & 0 & \ldots & b_0 & b_1 & b_2 \\ b_1 & 0 & 0 & \ldots & 0 & b_0 & b_1 \\ b_0 & 0 & 0 & \ldots & 0 & 0 & b_0 \end{array} \right|=0, \end{gather*}

which turns the connection formula 17 into the needed identity:

\[ A_n(x)=\sum _{i=0}^n \tfrac {n!}{(n-i)!}c_{i}B_{n-i}(x)=c_0B_{n-0}(x)=B_n(x). \]

Example 6

Let us find the standard basis representation of an arbitrary Appell polynomial $A_n(x)$ with transfer sequence $A(t)=\sum _{n=0}^{\infty }a_nt^n,$ where $a_n={ \tfrac {A_n(0)}{n!}}.$ For standard basis, we have $B_n(x)=x^n$ with transfer sequence $B(t)=\sum _{n=0}^{\infty }t^n,$ then

\begin{gather*} c_0=1,c_i= \tfrac {1}{a_0^{i+1}} \left| \begin{array}{cccccccc} a_i & 0 & 0 & \ldots & 0 & 0\\ a_{i-1} & 1 & 0 & \ldots & 0 & 0\\ a_{i-2} & 0 & 1 & \ldots & 0 & 0\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ a_1 & 0 & 0 & \ldots & 0 & 1 & 0 \\ a_0 & 0 & 0 & \ldots & 0 & 0 & 1 \end{array} \right|=a_i \end{gather*}

and the connection formula 17 takes the form

\[ A_n(x)=\sum _{i=0}^n \tfrac {n!}{(n-i)!}a_{i}x^{n-i}= \sum _{i=0}^n \tfrac {n!}{(n-i)!}\tfrac {A_i(0)}{i!}x^{n-i}=\sum _{n=0}^{n}\textstyle {n \choose i}A_i(0)x^{n-i}, \]

which reconstitute S. Roman’s umbral calculus result presented in [ 22 ] .

Remark 7

It is easy to see that the first $k$ members of the ratio $\frac{B(t)}{A(t)}=C(t)=\sum _{=0}^{\infty }c_it^i$ with $A(t)=\sum _{i=0}^{\infty }a_it^i$ and $B(t)=\sum _{i=0}^{\infty }b_it^i$ produce the simultaneous linear recurrent equations

\[ b_k=\sum _{j=0}^k a_j c_{k-j},\: \text{where}\: a_0\neq 0, \]

solutions of which in the form of determinants 15 were given formulas ???(2.22) in the significant collection of combinatorial identities of H. W Gould [ 21 ] . â–¡

Remark 8

Another interesting method of obtaining determinants 13 appeared in [ 26 ] . For two given formal power series

\[ g(x)=a_1x^1+a_2x^2+a_3x^3+\ldots +a_nx^n+\ldots , \]

\[ f(x)=\tfrac {1}{1-x}=1+x^1+x^2+x^3+\ldots +x^n+\ldots , \]

their compositional function $F(x)=f\left(g(x)\right)$ has the expansion

\begin{gather*} F(x)=1+a_1x^1+(a_1^2+a_2)x^2+(a_1^3+2a_1a_2+a_3)x^3+\\ +(a_1^4+3a_1^2a_2+a_2^2+2a_1a_3+a_4)x^4+\\ +(a_1^5+4a_1^3a_2+3a_1a_2^2+3a_1^2a_3+2a_2a_3+2a_1a_4+a_5)x^5+ \ldots \end{gather*}

and the coefficients of the powers of $n$ almost coincide with the connection determinants defined by 13 (for total identity, choose $f(x)=\frac{1}{1+x}.$)

The reasons of choosing $f(x)$ and $g(x),$ due to N. Wheeler, is cored into the eigenvalue representation of unnamed Newton matrices identity:

\[ \operatorname {det} \left(\mathbb {I}-x\mathbb {A}\right){=}\exp \left( \operatorname {tr} \: \operatorname {log} \left(\mathbb {I}-x\mathbb {A}\right)\right){=}{\exp }\left({-}T_1x-\tfrac {1}{2}T_2x^2-\tfrac {1}{3}T_3x^3+{\ldots } \right), \]

where $T_k = tr ( {\mathbb {A}}^k).$

Besides the relations between the connection determinants and the Toeplitz-Hessenberg matrix determinants, in [ 26 ] , the similarity of the Toeplitz-Hessenberg matrix determinants and the classical Bell polynomials are clarified. In the assumptions

\[ f(x)=\exp (x)=1+\tfrac {1}{1!}x^1+\tfrac {1}{2!}x^2+\tfrac {1}{3!}x^3+\ldots , \]

\[ g(x)=b_1x^1+\tfrac {1}{2!}b_2x^2+\tfrac {1}{3!}b_3x^3+\ldots , \]

one can obtain

\begin{gather*} F(x)=1+\tfrac {1}{1!}b_1x^1+\tfrac {1}{2!}(b_1^2+b_2)x^2+\tfrac {1}{3!}(b_1^3+3b_1b_2+b_3)x^3+\\ +\tfrac {1}{4!}(b_1^4+6b_1^2b_2+3b_2^2+4_1b_3+b_4)x^4+\\ +\tfrac {1}{5!}(b_1^5+10b_1^3b_2+15b_1b_2^2+10b_1^2b_3+10b_2b_3+5b_1b_4+b_5)x^5+ \ldots = \end{gather*}

\begin{gather*} =1+\tfrac {1}{1!}B_1\left(b_1\right)x^1+\tfrac {1}{2!}B_2\left(b_1,b_2\right)x^2+\tfrac {1}{3!}B_3\left(b_1,b_2,b_3\right)x^3+\\ +\tfrac {1}{4!}B_4\left(b_1, b_2, b_3, b_4\right)x^4 +\tfrac {1}{5!}B_5\left(b_1, b_2, b_3, b_4, b_5\right)x^5+ \ldots , \end{gather*}

where the $B_n(\bullet )$ are the classical complete exponential Bell polynomials. â–¡

3 Combinatorial meanings of Appell connection constants

3.1 Integer composition

As far as classical Bell polynomials encode the information related to the ways a set (an integer number) can be partitioned, let us have a look on the inverse determinants 13 from the combinatorial point of view.

The partition of the integer number $n$ is a tuple of positive integers [ 4 ] : $\lambda =\left({\lambda }_1,{\lambda }_2, \ldots , {\lambda }_n\right) $ such that ${\lambda }_1+{\lambda }_2+ \ldots + {\lambda }_k=n$ and ${\lambda }_1\leq {\lambda }_2\leq \ldots \leq {\lambda }_k.$ The notation $\lambda \vdash n$ means that $\lambda $ is a partition of $n.$ As usual, integer partitions are visualized with Young diagrams.

Two sums that differ only in the order of their summands are considered the same partition. For example, $5$ can be partitioned in seven distinct ways:

\[ 5=5, 5=4 + 1, 5=3 + 2, 5=3 + 1 + 1, 5=2 + 2 + 1, \]

\[ 5=2 + 1 + 1 + 1, 5=1 + 1 + 1 + 1+1. \]

If the order of summands does matter, integer partition is called integer composition.

In the case of integer composition of $n,$ we move from the origin $(0, 0)$ to the east-north along the $n \times n$ square diagonal. The step is a pair $(x, y),$ where $x$ is an east value, $y$ is a north value. In integer compositions, only $(x, x)$ diagonal steps occur, with the length of the step equal to $x.$ Thus, we associate every step $\left({\lambda }_j, {\lambda }_j \right)$ with a member ${\lambda }_j$ of the certain partition ${\sum }_{j=1}^k {\lambda }_j=n.$ The pass is a sequence of the diagonal steps with integer coordinate from the origin $(0, 0)$ to the point $(n, n).$ So, a path is a product of the steps of lengths ${\lambda }_i:$ $ \left({\lambda }_1, {\lambda }_1 \right) \left({\lambda }_2, {\lambda }_2 \right) \ldots \left({\lambda }_k, {\lambda }_k \right).$ Thus, there exists a one-to-one correspondence between the set of all compositions of $n$ and the set of all different paths from $(0, 0)$ to the point $(n, n).$

According to the composition definition, for $n=5,$ the binary paths

\[ \left(1, 1 \right) \left(2,2 \right) \ldots \left(2, 2 \right) \text{and} \: \left(2, 2 \right) \left(2,2 \right) \ldots \left(1, 1 \right) \]

are considered to be different, but, taking into account step product’s commutativity, we have three different paths of length $1+2+2:$

\begin{gather*} (1,1)(2,2)(2,2)+(2,2)(1,1)(2,2)+(2,2)(2,2)(1,1)=\\ =3(1,1)(2,2)(2,2)=3(1,1){(2,2)}^2. \end{gather*}

For $n=5,$ we have sixteen distinct partitions, two of which are shown in Fig. 1 (a, b).

\includegraphics[width=0.4\textwidth ]{part_1(2).jpg} — $5=1+1+3$.

\includegraphics[width=0.4\textwidth ]{part_2(2).jpg} — $5=1+1+3$.

3.2 Toeplitz-Hessenberg matrix determinants via integer composition

As far, as Toeplitz-Hessenberg matrix determinants 13 and, consequently, the formulas ??, describe integer partition of natural number $i,$ it implies the combinatorial meaning of the connection coefficients $a_i^{\ast }$ defined by lemma 2.‘ We match every step $\left( {\lambda }_j, {\lambda }_j \right)$ the member $a_{{\lambda }_j}$ of the transfer function $A(t)={\sum }_{n=0}^n a_it^i.$ Then, the expressions for $a_i^{\ast }$ 13 of the inverse problem are literally the “connection” coefficients, each of $a_i^{\ast }$ is formed as a sum of all different paths connecting the origin $(0, 0)$ with the point $(n, n).$ The latter coincides with all integer compositions of $n.$

For instance, if $n=5,$ from 13,

\begin{equation*} c_5=-a_1^5+4a_1^3a_2-3a_1^2a_3-3a_1a_2^2+2a_1a_4+2a_2a_3-a_5. \end{equation*}

Here the summands multiplied by a number $k$ contain $k$ different paths, i.e.,

\[ 3a_1a_2^2=a_1a_2a_2+a_2a_1a_2+a_2a_2a_1 \]

binary path corresponding to the second summand in the latter sum are shown in Fig. 1(a)??,

\[ 3a_1^2a_3=a_1a_1a_3+a_1a_3a_1+a_3a_1a_1 \]

binary path corresponding to the first summand in the latter sum are shown in Fig. 1(b)???, and we have sixteen different binary paths in total.

Moreover, those coefficients $a_i^{\ast }$ 13 form the corresponding line in the analogue of Pascal triangle, similiar constructions occure for special polynomial structures ( [ 7 ] ). In the case of the inverse problem, we have the analogue of Pascal’s triangle for compositions (as far as the order of the summands matters, some coefficients are multiplied by a number $k$):

\[ {{{ {{{ \begin{array}{ccccccccccccccccccccccccc}& & & & & \! {{{1 }}}\\ & & & & & \! {{{-}}}a_{(1)} \\ & & & & \! {{{a}}}_{(1^2)} & & \! {{{-}}}{{{a}}}_{(2)} \\ & & & \! {{{-}}}{{{a}}}_{(1^3)} & & \! {{2}}{{{a}}}_{(2,1)} & & \! {{{-a}}}_{(3)} \\ & & \! {{{a}}}_{(1^4)} & & \! {{{-}}}{{3}}{{{a}}}_{(2,1^2)} & \! a_{(2^2)} & \! 2a_{(3,1)} & & \! {{{-a}}}_{(4)} \\ & \! {{{-a}}}_{{{(1^5)}}} & & \! {4{a_{{{(2,1^3)}}}}} & \! {{{-}}}{3}a_{{{(2^2,1)}}} & \! {{{-}}}{3}a_{{{(3,1^2)}}} & \! {2}a_{{{(3,2)}}} & \! {2}a_{{{(4,1)}}} & & \! {{{-}}}a_{(5)} \end{array}}}} }}} \]

where $a_{\left(\lambda _i \vdash n\right)}=\prod _{i} a_i^{m_i},$ i.e., $ a_{(2,1^3)}=a_2a_1^3.$

Here, some summands have negative signs. Combinatorially, it means when making the odd number of paths we change the direction into the opposite one.

Let us denote the number of all different paths corresponding to integer $n$ by $W(n),$ the properties of the Pascal triangle implies $W(n)=2^{n-1}.$ Thus, we have

Proposition 9

The number of all different paths corresponding to each $a_i^{\ast }$ in determinants 13 is equal to $2^{i-1}.$

Combinatorially, the expressions for $c_i$ from the connection problem solution given by theorem 4 are formed in the following manner. Starting from the origin $(0, 0),$ the first step correspondent to $b_i$ always ought to be made over the main diagonal of the big square to the east-north (marked by blue), and it can be absent. The rest of the steps corresponding to ${\prod }_{k=1}^{n-i} a_k$ are made under the main diagonal of the big square to the point $(n, n)$ (marked by red).

In other words, connection coefficient $c_n$ is represented by the set of all paths, each of the latter consists of no more than one upper binary step and the rest $(n-i)$ lower steps, both all upper and lower steps are the members of the same integer partition. If we match every upper step $\left( {\beta }_i, {\beta }_i\right)$ with the coefficient ${b}_{{\beta }_i}$ of the transfer function $B(t)$ and we match the rest $(n-i)$ of the lower steps with the product of the coefficients ${a}_{{\alpha }_1}, \ldots , {a}_{{\alpha }_{n-i}} $ of the transfer function $A(t),$ then the path $\left({\beta }_i, {\beta }_i \right) \left({\alpha }_1, {\alpha }_1 \right) \ldots , \left({\alpha }_{n-i}, {\alpha }_{n-i} \right)$ is matched with a product ${b}_{{\beta }_i},{a}_{{\alpha }_1}, \ldots , {a}_{{\alpha }_{n-i}},$ where ${\beta }_{i}+{\alpha }_1+ \ldots + {\alpha }_{n-i}=n.$

For instance, if $n=4,$ due to 15,

\[ c_4=a_1^4-a_1^3b_1-3a_1^2a_2+a_1^2b_2+2a_1a_2b_1+2a_1a_3-a_1b_3+a_2^2-a_2b_2-a_3b_1-a_4+b_4. \]

Here the summands multiplied by a number $k$ contain $k$ different paths, starting with $b_i$ $(0\leq i \leq n),$ i.e.,

\[ 2a_1a_2b_1=b_1a_1a_2+b_1a_2a_1 \]

the paths corresponding to both summands are shown in Fig. 2(a,b).

\includegraphics[width=0.4\textwidth ]{part_3(2).jpg} — $b_1a_1a_2$.

\includegraphics[width=0.4\textwidth ]{part_4(2).jpg} — $b_1a_1a_2$.

Proposition 10

The number of all different paths corresponding to each connection coefficient $c_i$ in determinants 13 is equal to $2^{i}.$

Proof â–¼

Let us count the number of all paths correspondent to the connection coefficient13.

If multiplier $b_i$ is absent, the corresponding summands look like ${\prod }_ka_k$ and the number of all correspondent paths describes integer composition of $n,$ and it is equal to $W(n)$;
for $b_1,$ the correspondent multipliers ${\prod }_ka_k$ describe integer composition of $n-1,$ d the number of correspondent paths is equal to $W(n-1)$, and we have $1 \cdot W(n-1)$ paths in total;
for $b_2,$ the correspondent multipliers ${\prod }_ka_k$ describe integer composition of $n-2,$ d the number of correspondent paths is equal to $W(n-2)$, and we have $1 \cdot W(n-1)$ paths in total; and so on;
for $b_{n-1},$ we have $1 \cdot W(1)$ paths;
finally, for $b_{n},$ we have only one possible path.

Summing up, we obtain from proposition 9:

\begin{gather*} W(n)+1 \cdot W(n-1)+1 \cdot W(n-2)+ \cdots + 1 \cdot W(2)+ 1 \cdot W(1) +1=\\ 2^{n-1}+2^{n-2}+\cdots + 2^{1}+ 2^{0}+1. \end{gather*}

The latter sum is known to be equal to $2^n,$ which completes the proof.

4 Connection coefficients for arbitrary polynomials

4.1 Expressions for arbitrary connection constants

Connection between two orthogonal polynomial families

\begin{align*} \label{P_Q} P_n(x)=\sum _{k=0}^n {a}_{n,k}x^k, \quad \quad Q_n(x)=\sum _{k=0}^m {\overline{a}}_{m,k}x^m, \: {a}_{n,k}, {\overline{a}}_{m,k} \in \mathbb {R} \end{align*}

can be established as a connection between corresponding vectors $\vec{P}_n^t$ and $\vec{Q}_n^t$ by the lower-triangle matrix of unknown coefficients $C_m(n)$ (see [ 24 ] ):

\[ \vec{P}_n = \left[C_{m,n}\right] \vec{Q}_n \: \textit{where} \: C_{m,n}=C_m(n), \]

or, equivalently:

\begin{equation*} \begin{pmatrix} P_0(x) \\ P_1(x) \\ \cdots \\ P_n(x) \end{pmatrix}= \begin{pmatrix} C_0(0) & 0 & \cdots & 0 \\ C_1(0) & C_1(1) & \cdots & C_1(0) \\ \cdots & \cdots & \cdots & \cdots \\ C_n(0) & C_n(1) & \cdots & C_n(n) \end{pmatrix}\begin{pmatrix} Q_0(x) \\ Q_1(x) \\ \cdots \\ Q_n(x) \end{pmatrix}\end{equation*}

We will search for the solution of the connection problem ?? in the form

\begin{equation} \label{con_con} P_n(x) = \begin{pmatrix} d_0(n) & d_1(n) & d_2(n) & \cdots & d_n(n) \end{pmatrix} \begin{pmatrix} Q_n(x) \\ Q_{n-1}(x) \\ Q_{n-2}(x) \\ \cdots \\ Q_0(x) \end{pmatrix}. \end{equation}

Solving the Appell connection problem in the previous section was based on the simultaneously linear recurrence equations

\[ b_k=\sum _{j=0}^k a_j c_{k-j},\: \text{where}\: a_0\neq 0, \: 0 \leq k \leq n, \]

Unlike the Appell polynomials, the generating function of an arbitrary polynomial family depends on two variable $x$ and $t,$ which can not be "divided" into two independent series, for instance, the Chebyshev polynomials $T_n(x)$ of the first kind have the following generating function

\[ \sum _{n=0}^{\infty }T_n(x)t^n=\frac{1-tx}{1-2tx+t^2}. \]

Let

\begin{equation} \label{explicit} P_n(x)=\sum _{i=0}^{n} c_i(n) {x^{n-i}} \text{\: and} \: \: Q_i(x)=\sum _{j=0}^{i} b_j(i) {x^{i-j}}, 0\leq i \leq n \end{equation}

be two families of arbitrary polynomials given in the standard basis. For the fixed $n,$ coefficients $d_i(n) $ and $c_i(n) $ can be treated as one-indexed, so we denote $d_i(n):=d_i,$ $c_i(n):=c_i.$ After substituting 19 into ??, we obtain simultaneously two-indexed recurrence equations

\begin{equation} \label{simult} b_i=\sum _{j=0}^i a_j c_{i-j}(n-j),\: \text{where}\: b_0(i) \neq 0, \: 0 \leq i \leq n. \end{equation}

Since $\operatorname {deg}(Q_i(x))=i,$ then $b_0(i)\neq 0,$ and, by the Cramer’s rule, 20 has unique solution.

Lemma 11

Solutions $c_i(n)$ of the simultaneously two-indexed recurrence equations 20 are defined by the $(n+1)$-order determinants

\begin{gather} \label{prosto} \displaystyle { c_i(n)=\frac{1}{a_0(n)a_0(n-1)\ldots a_0(1)a_0(0)}}\times \\ \times \left| \begin{array}{ccccccc} b_i & a_1(n-i+1) & a_2(n-i+2) & \ldots & a_{i-1}(n-i) & a_i(n)\\ b_{i-1} & a_0(n-i+1) & a_1(n-i+2) & \ldots & a_{i-2}(n-i) & a_{i-1}(n)\\ b_{i-2} & 0 & a_0(n-i+2) & \ldots & a_{i-3}(n-i) & a_{i-2}(n)\\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ b_0 & 0 & 0 & \ldots & 0 & a_0(n) \end{array} \right|.\notag \end{gather}

Now, we are ready to establish the explicit formula of the connection problem ?? in general case.

Theorem 12

For two polynomial families given in the standard basis

\begin{equation*} P_n(x)=\sum _{i=0}^{n} b_i(n) {x^{n-i}}, \: Q_i(x)=\sum _{j=0}^{i} a_j(i) {x^{i-j} }, \: b_0(i) \neq 0, \: 0\leq i \leq n, \end{equation*}

the unknown connection coefficients $c_i(n)$ of the connection problem ??

\begin{equation*} P_n(x)=\sum _{i=0}^n c_i(n)Q_i(x) \end{equation*}

are defined via determinants 21.

4.2 Combinatorial meanings of arbitrary connection constants

In fact, the connection problem ?? includes one polynomial $P_n(x)$ and the set of the polynomials $\{ Q_i(x)\} _{i=0}^n,$ every of which, in turn, is defined by the set of two-indexed coefficients $b_0(n), b_1(n),$ $ \ldots , b_n(n)$ and $a_0(n), a_1(n), \ldots , a_n(n),$ $a_0(n-1), a_1(n-1), \ldots , a_n(n-1),$ $\ldots ,$ $a_0(0), a_1(0), \ldots , a_n(0),$ respectively.

In the case when all zero-subscribed coefficients are equal to $1,$ the connection coefficients 21 have combinatorial meanings. It looks like we need to arrange all implicit points $(i, n)$ associated with value $a_i(n),$ and points $(i, i)$ associated with values $b_i(n)$ along the $(n, n)$ square diagonal in a proper way.

More precisely, we associate each two-indexed coefficient $b_i(n)$ ($0 \leq i \leq n$) with upper step (over the diagonal, marked blue) and each two-indexed coefficient $a_i(i)$ ($0 \leq i \leq n$) with lower binary step (under the diagonal, marked red) into the west-south direction. The number in the parentheses denotes the starting point at the diagonal of the $(n, n)$ square, the number of subscript denotes the step size.

Then every connection coefficient $c_i(n)$ ($0 \leq i \leq n$) in 21 represents the set of all possible paths from point $(n,n)$ to point $(n-i,n-i).$ Each path consists of no more than one upper step $b_i(n)$ and the rest $(n-i)$ of lower steps $a_i(i)$ ($0 \leq i \leq n$), both all upper and lower steps are the members of the same integer composition.

\includegraphics[width=0.4\textwidth ]{part_5(2).jpg} — $b_3(4) a_1(1)$.

\includegraphics[width=0.4\textwidth ]{part_6(2).jpg} — $b_3(4) a_1(1)$.

If $n=4,i=4,$ from 21,

\begin{gather*} c_4(4)=b_4(4) - b_3(4) a_1(1) + a_1(1) a_1(2) b_2(4) - a_2(2) b_2(4) -\notag \\ - a_1(1) a_1(2) a_1(3) b_1(4) + a_1(1) a_2(3) b_1(4) + a_2(2) a_1(3) b_1(4) - a_3(3) b_1(4)+\notag \\ + a_1(1) a_1(2) a_1(3) a_1(4) - a_1(1) a_1(2) a_2(4) - a_1(1) a_2(3) a_1(4) + a_1(1) a_3(4) -\notag \\ - a_2(2) a_1(3) a_1(4)+ a_2(2) a_2(4) + a_3(3) a_1(4) - a_4(4), \end{gather*}

which implies sixteen different paths from $(4, 4)$ to $(0, 0)$, the ones representing the second and the seventh summands, respectively, are shown in Fig. 3(a, b).

If $n=4,i=3,$ from 21,

\begin{gather*} c_3(4)=-a_1(3)a_1(2)a_1(4)+a_1(3)a_1(2)b_1(4)+a_2(3)a_1(4)-\notag \\ -a_2(3)b_1(4)+a_1(2)a_2(4)-b_2(4)a_1(2)+b_3(4)-a_3(4), \end{gather*}

there are eight different binary paths from $(4, 4)$ to $(1, 1)$, the ones representing the second and the third summands, respectively, are shown in Fig. 4(a, b).

\includegraphics[width=0.4\textwidth ]{part_7(2).jpg} — $a_1(3)a_1(2)b_1(4)$.

\includegraphics[width=0.4\textwidth ]{part_8(2).jpg} — $a_1(3)a_1(2)b_1(4)$.

Proposition 13

The number of all different paths corresponding to each connection coefficient in the 21 is equal to $2^{i}.$

The proof is analogous to that of proposition 9.

Remark 14

Choosing a proper numeration of the polynomial coefficients different from the standard one 19 one can obtain the binary paths correspondent to the connection coefficients that will start at origin $(0, 0)$ and will end at point $(n,n).$ â–¡

Remark 15

In the case when zero-subscribed coefficients are not equal to $1,$ the number of the summands does not increase, but the number of steps inside one summand does increase. Moreover, the divisors appear as well. That is why the question about combinatorial meanings of the connection coefficients $c_i(n)$ when all $a_0(i)\neq 0$ is still open. â–¡

Bibliography

1

L. Aceto, H.R. Malonek, Gr. Tomaz, A unified matrix approach to the representation of Appell polynomials, Integral Transforms. Spec. Funct., 26 (2015) no. 6, pp. 426–441, http://doi.org/10.1080/10652469.2015.1013035. $\includegraphics[scale=0.1]{ext-link.png}$

2

J.A. Adell, A. Lekuona, Binomial convolution and transformations of Appell polynomials, J. Math. Anal. Appl., 456 (2017) no. 1, pp. 16–33, https://doi.org/10.1016/j.jmaa.2017.06.077. $\includegraphics[scale=0.1]{ext-link.png}$

3

P. Appell, On one class of polynomials, Ann. Sci. Ec. Norm. Super., 9 (1880), 2e serie, pp. 119–144.

4

G.E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and Its Applications, vol. 2, Addison-Wesley, 1976.

5

H. Belbachir, S. Haj Brahim, M. Rachidi, On another approach for a family of Appell polynomials, Filomat, 9 (2018), pp. 4155–4164. $\includegraphics[scale=0.1]{ext-link.png}$

6

E.T. Bell, Partition Polynomials, Ann. Math., Second Series, 29 (1927-1928), no. 1/4, pp. 38–46.

7

N. Bonneux, Z. Hamaker, J. Stembridge, M. Stevensa, Wronskian Appell polynomials and symmetric functions, Adv. Appl. Math., 111 (2019), 101932, https://doi.org/10.1016/j.aam.2019.101932. $\includegraphics[scale=0.1]{ext-link.png}$

8

F. Brioschi, Sulle funzioni Bernoulliane ed Euleriane, Ann. Mat. Pura Appl., (1858), pp. 260–263, https://doi.org/10.1007/BF03197335. $\includegraphics[scale=0.1]{ext-link.png}$

9

S.A. Carillo, M. Hurtado, J. Stembridge, M. Stevensa, Appell and Sheffer sequences; on their characterizations through functionals and examples, Comptes Rendus Math., (2021) no. 2, pp. 205–217, https://doi.org/10.5802/crmath.172. $\includegraphics[scale=0.1]{ext-link.png}$

10

F.A. Costabile, E. Longo, A determinantal approach to Appell polynomials, J. Comput. Appl. Math., 234 (2010) no. 2, pp. 1528–1542, https://doi.org/10.1016/j.cam.2010.02.033. $\includegraphics[scale=0.1]{ext-link.png}$

11

Y.B. Cheikh, H. Chaggara, Connection problems via lowering operators, J. Comput. Appl. Math., 178 (2005) nos. 1-2, pp. 45–61, doi:10.1016/j.cam.2004.02.024. $\includegraphics[scale=0.1]{ext-link.png}$

12

G. Dattoli, Hermite-Bessel and Laguerre-Bessel functions: a by-product of the monomiality principle, in: Advanced Special Functions and Applications, Proceedings of the Melfi School on Advanced Topics in Mathematics and Physics, J. Comput. Appl. Math., Aracne Editrici, Rome, (2005), pp. 147–164, https://doi:10.1016/j.cam.2004.02.024. $\includegraphics[scale=0.1]{ext-link.png}$

13

E. Godoy, A. Ronveaux, A. Zarzo, I. Area, Minimal recurrence relations for connection coefficients between classical orthogonal polynomials: Continuous case, J. Comput. Appl. Math., (1997) no. 84, pp. 257–275, https://doi.org/10.1016/s0377-0427(97)00137-4. $\includegraphics[scale=0.1]{ext-link.png}$

14

W. Koepf, D. Schmersau, Recurrence equations and their classical orthogonal polynomials solutions, Appl. Math. Comput., (2002) no. 128, pp. 303–327, http://doi.org/10.1016/S0096-3003(01)00078-9. $\includegraphics[scale=0.1]{ext-link.png}$

15

S. Lewanowicz, The Hypergeometric functions approach to the connection problem for the classical orthogonal polynomials, Inst. of Computer Sci., Univ. of Wroclaw, 2003, http://doi.org/10.13140/RG.2.1.2993.3209. $\includegraphics[scale=0.1]{ext-link.png}$

16

J.C. Lopez, sc R. Carreno, R.M. Suarez, J.A. Mendoza, Connection formulae among special polynomials, Int. J. Math. Comput. Sci., 10 (2015) no. 1, pp. 39–49.

17

N. Luno, Connection problems for the generalized hypergeometric Appell polynomials, Proceedings of the International Geometry Center, 13 (2020) no. 2, pp. 1–18, https://doi.org/10.15673/tmgc.v13i2.1733. $\includegraphics[scale=0.1]{ext-link.png}$

18

M. Merca, A note on the determinant of a Toeplitz-Hessenberg matrix, Spec. Matrices, (2013), pp. 10–16, https://eudml.org/doc/267216. $\includegraphics[scale=0.1]{ext-link.png}$

19

H.D. Nguyen, L.G. Cheong, New convolution identities for hypergeometric Bernoulli polynomials, J. Number Theory, 137 (2014), pp. 201–221, https://doi.org/10.1016/j.jnt.2013.11.008. $\includegraphics[scale=0.1]{ext-link.png}$

20

H. Pan, Zh. W. Sun, New identities involving Bernoulli and Euler polynomials, J. Combinatorial Theory, Series A, 113 (2006) no. 1, pp. 156–175, https://doi.org/10.1016/j.jcta.2005.07.008. $\includegraphics[scale=0.1]{ext-link.png}$

21

J. Quaintance, Combinatorial Identities for Stirling Numbers: The Unpublished Notes of H. W. Gould., World Scientific Publishing, Singapore, 2015.

22

S. Roman, G.-C. Rota, The umbral calculus, Adv. Math., 27 (1978) no. 2, pp. 95–188.

23

S. Roman, The umbral calculus, Dover Publ. Inc., New York, 2005.

24

A. Ronveaux, Orthogonal polynomials: connection and linearisation coefficients, Proceedings of the International Workshop on Orthogonal Polynomials in Mathematical Physics, Leganes, 24-26 June, 1996.

25

J. Sánchez-Ruiz, J.S. Dehesa, Some connection and linearization problems for the polynomials in and beyond the Askey scheme, J. Comput. Appl. Math., (2001) no. 133, pp. 579–591, http://dx.doi.org/10.1016/S0377-0427(00)00679-8. $\includegraphics[scale=0.1]{ext-link.png}$

26

https://www.reed.edu/physics/faculty/wheeler/documents/