On the r -Shifted Central Coefficients of Riordan Matrices

Abstract

By presenting Riordan matrix as a triangle, the central coefficients are entries in the central column. Starting at the central column, the r -shifted central coefficients are entries in column r of the right part of the triangle. This paper aims to characterize the r -shifted central coefficients of Riordan matrices. Here we will concentrate on four elements of the subgroups of the Riordan group, that is, the Bell subgroup, the associated subgroup, the derivative subgroup, and the hitting time subgroup. Some examples are presented to show how we deduce the generating functions for interesting sequences by using different means of calculating these r -shifted central coefficients. Besides, we make some extensions in the Bell subgroup.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Academic Editor:Jin Liang

Department of Applied Mathematics, Lanzhou University of Technology, Lanzhou, Gansu 730050, China

Received 23 August 2013; Revised 22 December 2013; Accepted 8 March 2014; 3 April 2014

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

Every infinite lower triangular array, in particular Riordan array, can be presented as a triangle. For instance, the Pascal triangle can be represented in the following form: [figure omitted; refer to PDF] However, its most usual representation is [figure omitted; refer to PDF] We will refer to the former representation as the ISO (isosceles) triangle and to the latter as the REC (rectangular) triangle. The central coefficients are given by the central column of the ISO triangle, which play an important role in combinatorics. Barry [1] makes use of the central coefficients of Bell matrices to deduce the generating functions of interesting sequences. A natural question to ask is, "What happens when other columns of the ISO triangle are examined?" We investigate this question for the right part of the Riordan triangle. To consider this case we define the r -shifted central coefficients and give their computing methods in four subgroups of the Riordan group in Section 2. With the r -shifted central coefficients, we can deduce the generating functions of more sequences. Also, some examples are presented to show how we deduce the generating functions of interesting sequences by using different means of calculating these r -shifted central coefficients. Some sequences referred to by their Annnnnn OEIS number can be found in On-Line Encyclopedia of Integer Sequence (OEIS) [2].

Furthermore, we introduce the AER (aerated) triangle as the ISO form with interposed zeros: [figure omitted; refer to PDF] Considering a Riordan array in its AER form, we prove that the right part of the AER triangle is an aerated Riordan array. That is to say, the r -shifted central coefficients with interposed zeros can generate an aerated Riordan array and the relation of this Riordan array with the initial one will be shown in Section 3. Finally, we defined the ( m , r ) -shifted central coefficients for expanding our research subject.

Before defining the r -shifted central coefficients we recall the Riordan group [3], sate the Fundamental Theorem of Riordan arrays, and give four of the subgroups of the Riordan group. Consider infinite matrices D = ( _{d n , k ) n , k ...5; 0} with entries in ... , the complex numbers. Let _{S i} ( t ) = ^{∑ n ...5; 0 ∞} _{d n , i} ^{t n} be the generating function of the i th column of D . We now make the crucial special assumption that [figure omitted; refer to PDF] where [figure omitted; refer to PDF] In this case, we write D = ( d ( t ) , h ( t ) ) and say that D is a Riordan array. That is to say, the pair ( d ( t ) , h ( t ) ) defines the D = ( _{d n , k ) n , k ...5; 0} having [figure omitted; refer to PDF]

Suppose we multiply D = ( d ( t ) , h ( t ) ) by a column vector ( _{l 0} , _{l 1} , ... ^{) T} and the result is the column vector ( _{b 0} , _{b 1} , ... ^{) T} . If the generating function for the sequence ( _{l 0} , _{l 1} , ... ^{) T} is L ( t ) and similarly, ( _{b 0} , _{b 1} , ... ^{) T} has B ( t ) as its generating function, then we obtain [figure omitted; refer to PDF] This is called the Fundamental Theorem of Riordan arrays. The typical column of M = ( g ( t ) , f ( t ) ) is g ( t ) [ f ( t ) ^{] i} and using this as L ( t ) quickly yields the matrix multiplication rule for the Riordan group which is [figure omitted; refer to PDF] This shows us that the identity I = ( 1 , t ) , the usual matrix identity, and group inverse [figure omitted; refer to PDF] where h ¯ ( t ) is the compositional inverse of h ( t ) , such that h ( h ¯ ( t ) ) = h ¯ ( h ( t ) ) = t . In addition, subgroups of the Riordan group are important and have been considered in the literature.

(i) The associated subgroup [4]: elements of this subgroup are of the form ( 1 , h ( t ) ) .

(ii) The Bell subgroup [4]: elements of this subgroup are of the form ( h ( t ) / t , h ( t ) ) or ( f ( t ) , t f ( t ) ) .

(iii): The derivative subgroup [5]: elements of this subgroup are of the form ( ^{h [variant prime]} ( t ) , h ( t ) ) , where ^{h [variant prime]} ( t ) denotes the first derivative of h ( t ) .

(iv) The hitting time subgroup [6]: elements of this subgroup are of the form ( t ^{h [variant prime]} ( t ) / h ( t ) , h ( t ) ) , where ^{h [variant prime]} ( t ) denotes the first derivative of h ( t ) .

In order to compute the r -shifted central coefficients of matrices in the previous defined subgroups, we need the Lagrange Inversion Formula, whose proof can be found in [7].

Lemma 1 (LIF).

Let h ( t ) be a formal power series with h ( 0 ) = 0 and ^{h [variant prime]} ( 0 ) ...0; 0 and let h ¯ ( t ) be its compositional inverse; then one has [figure omitted; refer to PDF]

2. r -Shifted Central Coefficients

Definition 2.

Let D = ( d ( t ) , h ( t ) ) = ( _{d i , j ) i , j ...5; 0} be a Riordan array, and _{D 2 n , n} = { _{d 0,0} , _{d 2,1} , _{d 4,2} , _{d 6,3} , ... } denote the central coefficients. Then the r -shifted central coefficients are defined as the sequence _{D 2 n + r , n + r} , where n , r ∈ ... .

According to this definition, we find that the central coefficients are equal to 0-shifted central coefficients. Sometimes, we ignore the central coefficients; that is to say, the first column considered is 1-shifted central coefficients. Therefore, ( r + 1 ) -shifted central coefficients should be given for r ∈ ... .

Example 3.

The ISO representation of the Bell-type Riordan array D = ( ( 1 - 1 - 4 t ) / 2 t , ( 1 - 1 - 4 t ) / 2 ) is [figure omitted; refer to PDF]

Then its central coefficients begin 1,2 , 9,48 , ... , 1-shifted central coefficients begin 1,3 , 14 , ... , and 2-shifted central coefficients begin 1,4 , 20 , ... .

If we consider lattice paths in the first quadrant, then the r -shifted central coefficients _{D 2 n + r , n + r} of Riordan array D = ( ( 1 - 1 - 4 t ) / 2 t , ( 1 - 1 - 4 t ) / 2 ) are the number of paths from ( 0,0 ) to ( 2 n + r , n + r ) that consist of steps ( 1,1 ) and steps ( 1 , - l ) , l ...5; 0 . Besides, _{D 2 n + r , n + r} also denotes the number of paths from ( 0,0 ) to ( 3 n + r , n + r ) that consist of up steps ( 1,1 ) and down steps ( 1 , - 1 ) . If we just allow east steps ( 1,0 ) and north steps ( 0,1 ) , then _{D 2 n + r , n + r} is the number of paths from ( 0,0 ) to ( 2 n + r , n ) , never going above the main diagonal y = x .

In this section, we characterize the r -shifted central coefficients of the matrices in four subgroups, of which the Bell subgroup is the most important. Also, some examples are presented to show how we deduce the generating functions of interesting sequences by using different methods to calculate these r -shifted central coefficients.

2.1. The Bell Subgroup

Theorem 4.

Let B = ( h ( t ) / t , h ( t ) ) be an element of the Bell subgroup of the Riordan group. If _{B 2 n + r , n + r} denote the r -shifted central coefficients of B , then one has [figure omitted; refer to PDF] where g ( t ) = ^{t 2} / h ( t ) , n , r ∈ ... .

Proof.

According to formula (6), we can calculate _{B 2 n + r , n + r} directly, [figure omitted; refer to PDF]

We now apply the LIF. This says that if we have [figure omitted; refer to PDF] then [figure omitted; refer to PDF] Thus we obtain that [figure omitted; refer to PDF] where g ( t ) = ^{t 2} / h ( t ) ; then formula (12) is obtained.

From formula (12) and [figure omitted; refer to PDF] formula (13) can be obtained immediately.

Example 5.

Let us consider the Riordan array [figure omitted; refer to PDF] We wish to show the following two formulas: [figure omitted; refer to PDF] where q = 1 - 6 t + ^{t 2} , r = 0,1 , 2,3 , ... . Using this formula, we can give some interesting sequence generating functions. Here we just list the first two cases: in the case r = 0 , the sequence we give is little Schröder numbers A001003, and in the case r = 1 , the sequence we give begins 1,3 , 14,70,363 , ... [figure omitted; refer to PDF] where q = 1 - 6 t + ^{t 2} , r ∈ ... . Here we show several cases: 0-shifted central coefficients _{B 2 n , n} begin 1,2 , 9,44,25 , ... , 1-shifted central coefficients _{B 2 n + 1 , n + 1} begin 1,3 , 14,70,363 , ... , 2-shifted central coefficients _{B 2 n + 2 , n + 2} are A089382, and 3-shifted central coefficients _{B 2 n + 3 , n + 3} begin 1,5 , 27,147,806 , ... .

In order to do this, we need to calculate the r -shifted central coefficients of this matrix in two ways. Then we have [figure omitted; refer to PDF]

On the other hand, by solving the inverse of g ( t ) , here g ( t ) = ^{t 2} / h ( t ) = t ( 1 - 2 t ) / ( 1 - t ) , we have [figure omitted; refer to PDF] Thus, from the previous theorem, the two formulas can be obtained by comparing the two expressions for _{B 2 n + r , n + r} .

Rogers [8] states that for every proper Riordan matrix D = ( d ( t ) , h ( t ) ) there exists a sequence A = ( _{a i ) i ∈ ...} such that for every n , k ∈ ... we have [figure omitted; refer to PDF] where the sum is actually finite, because when k > n , _{d n , k} = 0 . The sequence A = ( _{a i ) i ∈ ...} is called the A -sequence of the Riordan D = ( d ( t ) , h ( t ) ) . If A ( t ) is the generating function of the sequence A , we have [9] [figure omitted; refer to PDF] where h ¯ ( t ) is the compositional inverse of h ( t ) .

Making use of A -sequence and Theorem 4, we obtain a new characterization to the generating functions for central coefficients of a Bell-type array. Now we show this result as a corollary.

Corollary 6.

Let ( d ( t ) , h ( t ) ) be a proper Riordan array with the A-sequence whose generating function is A ( t ) . If _{B 2 n , n} denote the central coefficients of the Bell matrix B = ( A ( t ) , t A ( t ) ) produced by A ( t ) , then one has [figure omitted; refer to PDF]

Proof.

We can easily find that [figure omitted; refer to PDF] is equivalent to [figure omitted; refer to PDF] Then the result follows by using Theorem 4.

Example 7.

Consider the Riordan array D = ( 1 , h ( t ) ) = ( 1 , ( 1 - t - 1 - 2 t - 3 ^{t 2} ) / 2 t ) . From A ( t ) = t / h ¯ ( t ) , we have [figure omitted; refer to PDF]

Then the Bell matrix produced by A ( t ) is B = ( 1 + t + ^{t 2} , t ( 1 + t + ^{t 2} ) ) , its central coefficients [figure omitted; refer to PDF]

Since [figure omitted; refer to PDF] where M ( t ) = ( 1 - t - 1 - 2 t - 3 ^{t 2} ) / 2 ^{t 2} is the generating function for the Motzkin numbers, and Corollary 6, we have [figure omitted; refer to PDF]

2.2. The Associated Subgroup

Theorem 8.

Let S = ( 1 , h ( t ) ) be an element of the associated subgroup of the Riordan group. If _{S 2 n + r + 1 , n + r + 1} denote the ( r + 1 ) -shifted central coefficients of S , then one has [figure omitted; refer to PDF] where g ( t ) = ^{t 2} / h ( t ) , n , r ∈ ... .

Proof.

First of all, we have [figure omitted; refer to PDF] According to the Lagrange Inversion Formula, we have [figure omitted; refer to PDF] since we set [figure omitted; refer to PDF]

Therefore, we get [figure omitted; refer to PDF] where g ( t ) = ^{t 2} / h ( t ) .

Example 9.

Let us consider the Riordan array [figure omitted; refer to PDF] We wish to show that [figure omitted; refer to PDF] where q = 1 - 6 t + ^{t 2} , r ∈ ... . We can call this ( r + 1 ) -fold convolution of the large Schroeder numbers.

We list the first few cases: when r = 0 , the sequence is large Schröder numbers A006318, when r = 1 , the sequence is A006319, and when r = 2 , the sequence is A006320.

Firstly, we can calculate _{S 2 n + 1 , n + 1} directly, and then we have [figure omitted; refer to PDF] as expected. Secondly, to carry out the reversion of g ( t ) , we set g ¯ ( t ) = u , where g ( t ) = ( t - ^{t 2} ) / ( 1 + t ) ; then we obtain the result (with u ( 0 ) = 0 ) [figure omitted; refer to PDF] Lastly, from Theorem 8, the result follows.

2.3. The Derivative Subgroup

Theorem 10.

Let D = ( ^{h [variant prime]} ( t ) , h ( t ) ) be an element of the derivative subgroup of the Riordan group. If _{D 2 n + r , n + r} denote the r -shifted central coefficients of D , then one has [figure omitted; refer to PDF] where g ( t ) = ^{t 2} / h ( t ) , n , r ∈ ... .

Proof.

Calculating _{D 2 n + r , n + r} directly, we have [figure omitted; refer to PDF] Since ( n + r + 1 ) ^{h [variant prime]} ( t ) h ( t ^{) n + r} = ( d / d t ) h ( t ^{) n + r + 1} , we obtain [figure omitted; refer to PDF] As we know, [figure omitted; refer to PDF] then we have [figure omitted; refer to PDF]

We now set [figure omitted; refer to PDF] then an application of the Lagrange Inversion Formula gives us [figure omitted; refer to PDF]

Thus we obtain [figure omitted; refer to PDF] where g ( t ) = ^{t 2} / h ( t ) .

Example 11.

Let us apply the previous theorem to the Riordan array [figure omitted; refer to PDF] Actually, ( 1 / ( 1 - t ^{) 2} , t / ( 1 - t ) ) = ( 1 / ( 1 - t ) , t ) ( 1 / ( 1 - t ) , t / ( 1 - t ) ) .

Our purpose is to obtain that [figure omitted; refer to PDF] which is equivalent to [10] [figure omitted; refer to PDF] where C ( t ) = ( 1 - 1 - 4 t ) / 2 t is the generating function for the Catalan numbers.

Since g ( t ) = ^{t 2} / h ( t ) = ^{t 2} / ( t / ( 1 - t ) ) = t ( 1 - t ) , we have [figure omitted; refer to PDF] By the previous theorem, we have [figure omitted; refer to PDF]

We now calculate _{D 2 n + r , n + r} as follows: [figure omitted; refer to PDF]

A comparison of both expressions for _{D 2 n + r , n + r} now yields the result.

2.4. The Hitting Time Subgroup

Theorem 12.

Let H = ( t ^{h [variant prime]} ( t ) / h ( t ) , h ( t ) ) be an element of the hitting time subgroup of the Riordan group. If _{H 2 n + r + 1 , n + r + 1} denote the ( r + 1 ) -shifted central coefficients of H , then one has [figure omitted; refer to PDF] where g ( t ) = ^{t 2} / h ( t ) , n , r ∈ ... .

Proof.

Apparently, [figure omitted; refer to PDF] which can proceed along the same way as in the proof of Theorem 10.

Example 13.

Consider the Catalan triangle [figure omitted; refer to PDF] where C ( t ) is the generating function for the Catalan numbers and B ( t ) is the generating function for the central binomial coefficients. We wish to get that [figure omitted; refer to PDF] where p = sin ( arcsin ( 27 t / 4 ) / 3 ) , r ∈ ... .

In the case r = 0 , the sequence we discuss is A001764, and in the case r = 1 , the sequence we discuss is A006013.

To this end, we should make the g ¯ ( t ) clear. Here [figure omitted; refer to PDF] Then the compositional inverse of g ( t ) is [1] [figure omitted; refer to PDF] From Theorem 12, we have [figure omitted; refer to PDF] where p = sin ( arcsin ( 27 t / 4 ) / 3 ) .

_{H 2 n + 1 , n + 1} also can be presented as [figure omitted; refer to PDF] Then by Formula B ( t ) C ( t ^{) a} = ^{∑ k = 0 ∞} ... ( 2 k + a k ) ^{t k} [11], used backwards, we obtain [figure omitted; refer to PDF]

Comparison of the expressions for _{H 2 n + r + 1 , n + r + 1} now gives the result.

3. Some Extensions

In the previous section, using the r -shifted central coefficients, we can give some interesting sequences generating functions. In this section, we make some extensions.

(i) Generate the proper aerated Riordan array by the r -shifted central coefficients with interposed zeros.

(ii) ( m , r ) -shifted central coefficients are defined by stretching the right part of the triangle m times.

Here we do these just in the Bell subgroup.

3.1. r -Shifted Central Coefficients with Interposed Zeros

From Theorem 4, we have obtained that the r -shifted central coefficients _{B 2 n + r , n + r} of a Bell-type Riordan array B = ( h ( t ) / t , h ( t ) ) have g.f. given by [figure omitted; refer to PDF] where g ( t ) = ^{t 2} / h ( t ) , r ∈ ... . Therefore, an aerated Riordan array can be generated by the r -shifted central coefficients with interposed zeros, and it has the following form: [figure omitted; refer to PDF] where F ( t ) = ^{g ¯ [variant prime]} ( t ) , G ( t ) = g ¯ ( t ) . That is to say, the right part of the AER triangle (starting at any column r ...5; 0 ) is an aerated Riordan array which is uniquely determined by the function h ( t ) . For instance, the Pascal triangle can generate the aerated Riordan array ( B ( ^{t 2} ) , t C ( ^{t 2} ) ) , where B ( t ) = 1 / 1 - 4 t , C ( t ) = ( 1 - 1 - 4 t ) / 2 t .

3.2. ( m , r ) -Shifted Central Coefficients

For expanding our research subject in Bell subgroup, we now repeat the following steps.

(i) Stretch the infinite lower triangular array so that it becomes isosceles.

(ii) Consider the columns of the right part of the ISO triangle.

(iii): Regard the right part of the ISO triangle as an infinite lower triangular array.

We can repeat this process infinite times, because the right part of every triangle can be regarded as an infinite lower triangular array. Considering a Bell-type array D as the initial one, we now repeat this process m = 1,2 , 3 , ... times for the initial array; then we should consider the ( m , r ) -shifted central coefficients defined as the sequence _{D ( m + 1 ) n + r , m n + r} , where n , r ∈ ... , m = 1,2 , 3 , ... , just like the following cases.

When m = 1 , we consider [figure omitted; refer to PDF] That is to say, we should consider r -shifted central coefficients _{D 2 n + r , n + r} .

When m = 2 , we consider [figure omitted; refer to PDF] That is to say, we should consider ( 2 , r ) -shifted central coefficients _{D 3 n + r , 2 n + r} .

Then we have the following result.

Theorem 14.

Let _{D ( m + 1 ) n + r , m n + r} denote the ( m , r ) -shifted central coefficients of Bell-type Riordan matrix D = ( h ( t ) / t , h ( t ) ) ; then one has [figure omitted; refer to PDF] where g ( t ) = ^{t 2} / h ( t ) , n , r ∈ ... , m = 1,2 , 3 , ... .

Proof.

Using LIF and proceeding along the same way as in the proof of Theorem 4, we can get the result easily.

Example 15.

We consider the Pascal triangle D = ( h ( t ) / t , h ( t ) ) = ( 1 / ( 1 - t ) , t / ( 1 - t ) ) . We wish to prove the following result about the generating function for ( ( ( m - 1 ) n + r + 1 ) / ( m n + r + 1 ) ) ( m n + n + r n ) : [figure omitted; refer to PDF] where C ( t ) = ( 1 - 1 - 4 t ) / 2 t is the generating function for the Catalan number A000108, n , r ∈ ... , m = 1,2 , 3 , ... .

Since g ( t ) = ^{t 2} / h ( t ) = t ( 1 - t ) , we have [figure omitted; refer to PDF] By Theorem 14, we obtain [figure omitted; refer to PDF]

On the other hand, as we all known, the Pascal triangle D = _{( d i , j ) i , j ...5; 0} = ( i j ) . Therefore, we have [figure omitted; refer to PDF] Then the result follows immediately by comparing the two expressions for _{D ( m + 1 ) n + r , m n + r} .

Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grant no. 11261032) and the Natural Science Foundation of Gansu Province (Grant no. 1010RJZA049).

Conflict of Interests

The authors declare that they have no conflict of interests regarding the publication of this paper.

References

[1] P. Barry, "On the central coefficients of Bell matrices," Journal of Integer Sequences , vol. 14, no. 4, pp. Article 11.4.3, 2011.

[2] N. J. A. Sloane, "The On-Line Encyclopedia of Integer Sequences," 2011, http://oeis.org

[3] L. W. Shapiro, S. Getu, W. J. Woan, L. C. Woodson, "The Riordan group," Discrete Applied Mathematics , vol. 34, no. 1-3, pp. 229-239, 1991.

[4] L. W. Shapiro, "Bijections and the Riordan group," Theoretical Computer Science , vol. 307, no. 2, pp. 403-413, 2003.

[5] L. W. Shapiro, "A survey of the Riordan group," Lecture Notes, Center for Combinatorics, Nankai University, Tianjin, China, 2005, http://www.combinatorics.cn/activities/Riordan%20Group.pdf

[6] P. Peart, W.-j. Woan, "A divisibility property for a subgroup of Riordan matrices," Discrete Applied Mathematics , vol. 98, no. 3, pp. 255-263, 2000.

[7] R. Sprugnoli, "An introduction to mathematical methods in combinatorics," pp. 32-34, 2006, http://www.dsi.unifi.it/

[8] D. G. Rogers, "Pascal triangles, Catalan numbers and renewal arrays," Discrete Mathematics , vol. 22, no. 3, pp. 301-310, 1978.

[9] T.-X. He, R. Sprugnoli, "Sequence characterization of Riordan arrays," Discrete Mathematics , vol. 309, no. 12, pp. 3962-3974, 2009.

[10] D. Merlini, R. Sprugnoli, M. C. Verri, "Lagrange inversion: when and how," Acta Applicandae Mathematicae , vol. 94, no. 3, pp. 233-249, 2006.

[11] R. L. Graham, D. E. Knuth, O. Patashnik Concrete Mathematics , Addison-Wesley, New York, NY, USA, 1989.