Last Symbol Distribution in Pattern Avoiding Catalan Words
Tóm tắt
We study the distribution of the last symbol statistics on the sets of Catalan words avoiding a pattern of length at most three. For each pattern p, we provide a bivariate rational generating function where the coefficient
$$\varvec{c}_p(n,k)$$
of
$$x^ny^k$$
in its series expansion is the number of length n Catalan words avoiding p and ending with the symbol k. We deduce recurrence relations or closed forms for
$$\varvec{c}_p(n,k)$$
and we provide asymptotic approximations for the expectation of the last symbol on all Catalan words avoiding p. We end this paper by describing a computational approach using computer algebra.
Tài liệu tham khảo
Baril, J.-L., Kirgizov, S., Vajnovszki, V.: Descent distribution on Catalan words avoiding a pattern of length at most three. Discr. Math. 341, 2608–2615 (2018)
Baril, J.L., Khalil, C., Vajnovszki, V.: Catalan words avoiding pairs of length three patterns. Discr. Math. Theor. Comput. Sci. 22(2), 5 (2021)
Baril, J.-L., Ramírez, J.L.: Descent distribution on Catalan words avoiding ordered pairs of relations. Adv. Appl. Math. 149, 102551 (2023)
Bernini, A., Bouvel, M., Ferrari, L.: Some statistics on permutations avoiding generalized patterns. Pure Math Appl. (PU.M.A.) 18, 223–237 (2007)
Bousquet-Mélou, M., Claesson, A., Dukes, M., Kitaev, S.: (2+2)-free posets, ascent sequences and pattern avoiding permutations. J. Comb. Theory Ser. A 117(7), 884–909 (2010)
Callan, D., Mansour, T., Ramírez, J.L.: Statistics on bargraphs of Catalan words. J. Autom. Lang. Comb. 26, 177–196 (2021)
Elizalde, S., Flólrez, R., Ramírez, J.L.: Enumerating symmetric peaks in non-decreasing Dyck paths. Ars Math. Contemp. 21 (2021) #P2.04
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
Mansour, T., Shattuck, M.: Some enumerative results related to ascent sequences. Discr. Math. 315, 29–41 (2014)
Mansour, T., Ramírez, J.L., Toquica, D.A.: Counting lattice points on bargraphs of Catalan words. Math. Comput. Sci. 15, 701–713 (2021)
Mansour, T., Vajnovszki, V.: Efficient generation of restricted growth words. Inform. Process. Lett. 113, 613–616 (2013)
Orlov, A.G.: On asymptotic behavior of the Taylor coefficients of algebraic functions. Sib. Math. J. 25(5), 1002–1013 (1994)
Ramírez, J.L., Rojas-Osorio, A.: Consecutive patterns in Catalan words and the descent distribution. Bol. Soc. Mat. Mex. 29 (2023)
Ruskey, F., Savage, C.: Gray codes for set partitions and restricted growth tails. Australas. J. Combin. 10, 85–96 (1994)
Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. Available at https://oeis.org/
Stanley, R.: Enumerative Combinatorics. Vol. 1 Second Ed. Cambridge, (2012)
Stanley, R.: Catalan Numbers. Cambridge University Press, Cambridge (2015)
Woan, W.-J., Shapiro, L., Rogers, D.G.: The Catalan numbers, the Lebesgue integral, and \(4^{n-2}\). Am. Math. Month. 104, 926–931 (1997)