Matrix characterizations of Riordan arrays. (English) Zbl 1303.05007
Summary: Here we discuss two matrix characterizations of Riordan arrays, \(P\)-matrix characterization and \(A\)-matrix characterization. \(P\)-matrix is an extension of the Stieltjes matrix defined in [L. W. Shapiro, Theor. Comput. Sci. 307, No. 2, 403–413 (2003; Zbl 1048.05008)] and the production matrix defined in [E. Deutsch et al., Ann. Comb. 13, No. 1, 65–85 (2009; Zbl 1229.05015)]. By modifying the marked succession rule introduced in [D. Merlini et al., in: Mathematics and computer science. Algorithms, trees, combinatorics and probabilities. Proceedings of the colloquium, September 18–20, 2000. Basel: Birkhäuser. 127–139 (2000; Zbl 0965.68071)], a combinatorial interpretation of the \(P\)-matrix is given. The \(P\)-matrix characterizations of some subgroups of Riordan group are presented, which are used to find some algebraic structures of the subgroups. We also give the \(P\)-matrix characterizations of the inverse of a Riordan array and the product of two Riordan arrays. \(A\)-matrix characterization is defined in [D. Merlini et al., Can. J. Math. 49, No. 2, 301–320 (1997; Zbl 0886.05013)], and it is proved to be a useful tool for a Riordan array, while, on the other side, the \(A\)-sequence characterization is very complex sometimes. By using the fundamental theorem of Riordan arrays, a method of construction of \(A\)-matrix characterizations from Riordan arrays is given. The converse process is also discussed. Several examples and applications of two matrix characterizations are presented.
MSC:
| 05A15 | Exact enumeration problems, generating functions |
| 05A05 | Permutations, words, matrices |
| 11B39 | Fibonacci and Lucas numbers and polynomials and generalizations |
| 11B73 | Bell and Stirling numbers |
| 15B36 | Matrices of integers |
| 15A06 | Linear equations (linear algebraic aspects) |
| 05A19 | Combinatorial identities, bijective combinatorics |
| 11B83 | Special sequences and polynomials |
Keywords:
Riordan group; generating function; Stieltjes matrix; succession rule; production matrix; \(A\)-matrix; fundamental theorem of Riordan arrays; Stirling numbers of the second kindReferences:
| [1] | Barcucci, E.; Del Lungo, A.; Pergola, E.; Pinzani, R., ECO: a methodology for the enumeration of combinatorial objects, J. Difference Equ. Appl., 5, 435-490 (1999) · Zbl 0944.05005 |
| [2] | Bilotta, S.; Pergola, E.; Pinzani, R.; Rinaldi, S., Recurrence relations versus succession rules · Zbl 1425.05020 |
| [3] | Cheon, G.-S.; Jin, S.-T., Structural properties of Riordan matrices and extending the matrices, Linear Algebra Appl., 435, 2019-2032 (2011) · Zbl 1226.05021 |
| [4] | Cheon, G.-S.; Kim, H.; Shapiro, L. W., An algebraic structure for Faber polynomials, Linear Algebra Appl., 433, 1170-1179 (2010) · Zbl 1205.30007 |
| [5] | Cheon, G.-S.; Kim, H.; Shapiro, L. W., Combinatorics of Riordan arrays with identical A and Z sequences, Discrete Math., 312, 2040-2049 (2012) · Zbl 1243.05007 |
| [6] | Chung, F. R.K.; Graham, R. L.; Hoggatt, V. E.; Kleiman, M., The number of Baxter permutations, J. Combin. Theory Ser. A, 24, 382-394 (1978) · Zbl 0398.05003 |
| [7] | Deutsch, E.; Ferrari, L.; Rinaldi, S., Production matrices, Adv. in Appl. Math., 34, 1, 101-122 (2005) · Zbl 1064.05012 |
| [8] | Deutsch, E.; Ferrari, L.; Rinaldi, S., Production matrices and Riordan arrays, Ann. Comb., 13, 65-85 (2009) · Zbl 1229.05015 |
| [9] | Ferrari, L.; Pergola, E.; Pinzani, R.; Rinaldi, S., An algebraic characterization of the set of succession rules, Selected Papers in Honour of Maurice Nivat. Selected Papers in Honour of Maurice Nivat, Theoret. Comput. Sci., 281, 1-2, 351-367 (2002) · Zbl 1021.68068 |
| [10] | Gould, H. W.; He, T. X., Characterization of (c)-Riordan arrays, Gegenbauer-Humbert-type polynomial sequences, and (c)-Bell polynomials, J. Math. Res. Appl., 33, 5, 505-527 (2013) · Zbl 1299.05005 |
| [11] | He, T. X., A symbolic operator approach to power series transformation-expansion formulas, J. Integer Seq., 11, 2, 1-19 (2008), article 08.2.7 · Zbl 1151.41312 |
| [12] | He, T. X., Riordan arrays associated with Laurent series and generalized Sheffer-type groups, Linear Algebra Appl., 435, 1241-1256 (2011) · Zbl 1223.05012 |
| [13] | He, T. X., Parametric Catalan numbers and Catalan triangles, Linear Algebra Appl., 438, 3, 1467-1484 (2013) · Zbl 1257.05003 |
| [14] | He, T. X.; Hsu, L. C.; Shiue, P. J.-S., The Sheffer group and the Riordan group, Discrete Appl. Math., 155, 1895-1909 (2007) · Zbl 1123.05007 |
| [15] | He, T. X.; Sprugnoli, R., Sequence characterization of Riordan arrays, Discrete Math., 309, 3962-3974 (2009) · Zbl 1228.05014 |
| [16] | Hsu, L. C.; Shiue, P. J.-S., A unified approach to generalized Stirling numbers, Adv. in Appl. Math., 20, 366-384 (1998) · Zbl 0913.05006 |
| [17] | Jean-Louis, C.; Nkwanta, A., Some algebraic structure of the Riordan group, Linear Algebra Appl., 438, 5, 2018-2035 (2013) · Zbl 1282.05015 |
| [18] | Luzón, A.; Merlini, D.; Morón, M. A.; Sprugnoli, R., Identities induced by Riordan arrays, Linear Algebra Appl., 436, 3, 631-647 (2012) · Zbl 1232.05011 |
| [19] | Luzón, A.; Merlini, D.; Morón, M. A.; Sprugnoli, R., Complementary Riordan arrays, Discrete Appl. Math., 172, 75-87 (2014) · Zbl 1288.05015 |
| [20] | Merlini, D.; Rogers, D. G.; Sprugnoli, R.; Verri, M. C., On some alternative characterizations of Riordan arrays, Canad. J. Math., 49, 301-320 (1997) · Zbl 0886.05013 |
| [21] | Merlini, D.; Sprugnoli, R.; Verri, M. C., An algebra for proper generating trees, (Mathematics and Computer Science. Mathematics and Computer Science, Versailles (2000)), 127-139 · Zbl 0965.68071 |
| [22] | Nkwanta, A., A Riordan matrix approach to unifying a selected class of combinatorial arrays, Congr. Numer., 160, 33-45 (2003) · Zbl 1042.05005 |
| [23] | Peart, P.; Woan, W.-J., A divisibility property for a subgroup of Riordan matrices, Discrete Appl. Math., 98, 255-263 (2000) · Zbl 0944.05016 |
| [24] | Peart, P.; Woan, W.-J., Generating functions via Hankel and Stieltjes matrices, J. Integer Seq., 3, 2 (2000), article 00.2.1, 1 HTML document (electronic) · Zbl 0961.15018 |
| [25] | Rogers, D. G., Pascal triangles, Catalan numbers and renewal arrays, Discrete Math., 22, 301-310 (1978) · Zbl 0398.05007 |
| [26] | Shapiro, L. W., A survey of the Riordan group, (Talk at a Meeting of the American Mathematical Society. Talk at a Meeting of the American Mathematical Society, Richmond, VA (1994)) |
| [27] | Shapiro, L. W., Some open questions about random walks, involutions, limiting distributions and generating functions, Adv. in Appl. Math., 27, 585-596 (2001) · Zbl 0994.05008 |
| [28] | Shapiro, L. W., Bijections and the Riordan group, Theoret. Comput. Sci., 307, 403-413 (2003) · Zbl 1048.05008 |
| [29] | Shapiro, L. V.; Getu, S.; Woan, W. J.; Woodson, L., The Riordan group, Discrete Appl. Math., 34, 229-239 (1991) · Zbl 0754.05010 |
| [30] | Sprugnoli, R., Riordan arrays and combinatorial sums, Discrete Math., 132, 267-290 (1994) · Zbl 0814.05003 |
| [31] | Sprugnoli, R., Riordan arrays and the Abel-Gould identity, Discrete Math., 142, 213-233 (1995) · Zbl 0832.05007 |
| [32] | Yang, S.-L., Recurrence relations for the Sheffer sequences, Linear Algebra Appl., 437, 12, 2986-2996 (2012) · Zbl 1251.05015 |
| [33] | Yang, S.-L.; Zheng, S.-N.; Yuan, S.-P.; He, T.-X., Schröder matrix as inverse of Delannoy matrix, Linear Algebra Appl., 439, 11, 3605-3614 (2013) · Zbl 1283.15098 |
| [34] | Wang, W.; Wang, T., Generalized Riordan arrays, Discrete Math., 308, 24, 6466-6500 (2008) · Zbl 1158.05008 |
| [35] | West, J., Generating trees and forbidden subsequences, Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics. Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics, New Brunswick, NJ, 1994. Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics. Proceedings of the 6th Conference on Formal Power Series and Algebraic Combinatorics, New Brunswick, NJ, 1994, Discrete Math., 157, 1-3, 363-374 (1996) · Zbl 0877.05002 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
