Context-free grammars, generating functions and combinatorial arrays
| Autor: | Bao-Xuan Zhu, Qinglin Lu, Yeong-Nan Yeh |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Combinatorics
Recurrence relation 010201 computation theory & mathematics Group (mathematics) Flag (linear algebra) 010102 general mathematics Discrete Mathematics and Combinatorics 0102 computer and information sciences 0101 mathematics Context-free grammar Type (model theory) 01 natural sciences Mathematics |
| Zdroj: | European Journal of Combinatorics. 78:236-255 |
| ISSN: | 0195-6698 |
| Popis: | Let [ R n , k ] n , k ≥ 0 be an array of nonnegative numbers satisfying the recurrence relation R n , k = ( a 1 n + a 2 k + a 3 ) R n − 1 , k + ( b 1 n + b 2 k + b 3 ) R n − 1 , k − 1 + ( c 1 n + c 2 k + c 3 ) R n − 1 , k − 2 with R 0 , 0 = 1 and R n , k = 0 unless 0 ≤ k ≤ n . In this paper, we first prove that the array [ R n , k ] n , k ≥ 0 can be generated by some context-free Grammars, which gives a unified proof of many known results. Furthermore, we present criteria for real rootedness of row-generating functions and asymptotical normality of rows of [ R n , k ] n , k ≥ 0 . Applying the criteria to some arrays related to tree-like tableaux, interior and left peaks, alternating runs, flag descent numbers of group of type B , and so on, we get many results in a unified manner. Additionally, we also obtain the continued fraction expansions for generating functions related to above examples. As results, we prove the strong q -log-convexity of some generating functions. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect