* (281) S. Scheidegger, R. Käppeli, S. C. Whitehouse, T. Fischer, and M. Liebendorfer, Astronomy & Astrophysics 514, A51 (2010).
  * (282) P. Cerdá-Durán, N. DeBrye, M. A. Aloy, J. A. Font, and M. Obergaulinger, Astrophys. J. Lett. 779, L18 (2013).
  * (283) C. D. Ott et al., Astrophys. J. 768, 115 (2013).
  * (284) K. N. Yakunin et al., 92,084040,2015
  * (285) T. Kuroda, T. Takiwaki, and K. Kotake, 89,044011,2014
  * (286) K.-C. Pan, M. Liebendoerfer, S. M. Couch, and F.K. Thielemann, Astrophys. J. 857, 13 (2018).
  * (287) V. Morozova, D. Radice, A. Burrows, and D. Vartanyan, Astrophys. J. 861, 10 (2018).
  * (288) K. Kotake, Comptes Rendus Physique 14 318 (2013).
  * (289) A. Heger, S. E. Woosley, and H. C. Spruit, Astrophys. J. 626, 350 (2005).
  * (290) T. Takiwaki, K. Kotake, and Y. Suwa, Mon. Not. R. Astron. Soc. 461, L112 (2016).
  * (291) A. Summa, H.-T. Janka, T. Melson, and A Marek, Astrophys. J. 852, 28 (2018).
  * (292) T. Foglizzo et al., PASA 32 e009 (2015).
  * (293) E. Müller, and H.-T. Janka, Astronomy & Astrophysics 317, 140 (1997).
  * (294) E. Müller, M. Rampp, R. Buras, H.-T. Janka, and D. H. Shoemaker, Astrophys. J. 603, 221 (2004).
  * (295) J. W. Murphy, C. D. Ott, and A. Burrows, Astrophys. J. 707, 1173 (2009).
  * (296) K. Kotake, W. Iwakami, N. Ohnishi, and S. Yamada, Astrophys. J. Lett. 697, L133 (2009).
  * (297) B. Müller, H.-T. Janka, and A. Marek, Astrophys. J. 766, 43 (2013).
  * (298) A. Torres-Forné, P. Cerdá-Durán, M. Obergaulinger, B. Müller, and J. A. Font, 123, 051102,2019
  * (299) H. Andresen, B. Müller, E. Müller, and H.-T. Janka, Mon. Not. R. Astron. Soc. 468, 2032 (2017).
  * (300) T. Kuroda, K. Kotake, and T. Takiwaki, Astrophys. J. Lett. 829, L14 (2016).
  * (301) D. Radice, V. Morozova, A. Burrows, D. Vartanyan, and H. Nagakura, Astrophys. J. Lett. 876, L9 (2019).
  * (302) H. Andresen, E. Müller, H.-T. Janka, A. Summa, K. Gill, and M. Zanolin, Mon. Not. R. Astron. Soc. 486, 2238 (2019).
  * (303) S. E. Woosley, and T. A. Weaver, Astrophys. J. Suppl. 101, 181 (1995).
  * (304) H. Kawahara, T. Kuroda, T. Takiwaki, K. Hayama, and K. Kotake, Astrophys. J. 867, 126 (2018).
  * (305) L. Cohen, Time-frequency analysis: theory and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
  * (306) L. Stankovic, M. Dakovi?, and T. Thayaparan, 2013 Time-Frequency Signal Analysis with Applications (Boston: Artech House Publishers)
  * (307) B. Boashash, 2015 Time-Frequency Signal Analysis and Processing, II Edition A Comprehensive Reference (Amsterdam: Elsevier)
  * (308) A. Torres-Forné, P. Cerdá-Durán, A. Passamonti, M. Obergaulinger, and J. A. Font, Mon. Not. R. Astron. Soc. 482, 3967 (2019).
  * (309) K. Hayama, T. Kuroda, K. Nakamura, and S. Yamada, 116,151102,2016
  * (310) K. Hayama, T. Kuroda, K. Kotake, and T. Takiwaki, Mon. Not. R. Astron. Soc. Lett. 477, L96 (2018).
  * (311) A. W. Steiner, M. Hempel, and T. Fischer, Astrophys. J. 774, 17 (2013).
  * (312) K. Hayama, T. Kuroda, K. Kotake, and T. Takiwaki, 92,122001,2015
  * (313) C. D. Ott, Class. Quant. Grav. 26, 6/0630010630012009
  * (314) S. E. Woosley, and A. Heger, Astrophys. J. 637, 914 (2006).
  * (315) S. Suvorova, J. Powell, and A. Melatos, 99,123012,2019
  * (316) S. E. Gossan et al., 93,042002,2016
  * (317) T. Takiwaki, and K. Kotake, Mon. Not. R. Astron. Soc. 475, L91 (2018).
  * (318) S. Hild, A. Freise, M. Mantovani, S. Chelkowski, J. Degallaix, and R. Schilling, Class. Quant. Grav. 26, 025005 (2009).
  * (319) Y. Aso, Y. Michimura, K. Somiya, M. Ando, O. Miyakawa, T. Sekiguchi, D. Tatsumi, and H. Yamamoto, 88, 043007,2013
  * (320) L. Walk, I. Tamborra, H.-T. Janka, and A. Summa, 98, 123001,2018
  * (321) L. Walk, I. Tamborra, H.-T. Janka, and A. Summa, 100, 063018,2019
  * (322) K. Belczynski et al., Astrophys. J. Lett. 715, L138 (2010).
  * (323) N. Langer, Ann. Rev. Astron. Astrophys. 50, 107 (2012).
  * (324) T. Kinugawa, H. Nakano, and T. Nakamura, Progress of Theoretical and Experimental Physics 103E01, (2015)
  * (325) C. L. Fryer, S. E. Woosley, and D. H. Hartmann, Astrophys. J. 526, 152 (1999).
  * (326) K.-C. Pan, M. Liebendörfer, S. M. Couch, and F.-K. Thielemann, Astrophys. J. 857, 13 (2018).
  * (327) M. Liebendörfer, S. C. Whitehouse, and T. Fischer, Astrophys. J. 698, 1174 (2009).
  * (328) C. Chan, B. Müller, A. Heger, R. Pakmor, and V. Springel, Astrophys. J. Lett. 852, L19 (2018).
  * (329) K. Takahashi, H. Umeda, T. Yoshida 2014,ApJ, 794, 40
  * (330) M. Shibata, K. Kiuchi, Y. Sekiguchi, and Y. Suwa, Progress of Theoretical Physics 125, 1255, (2011)
  * (331) T. Kuroda, K. Kotake, T. Takiwaki, and F.-K. Thielemann, Mon. Not. R. Astron. Soc. 477, L80 (2018).
  * (332) M. Shibata, and T. Nakamura, 52,5428,1995
  * (333) T. W. Baumgarte, and S. L. Shapiro, 59,024007,1999
  * (334) J. Thornburg, Class. Quant. Grav. 21, 743 (2004).
  * (335) J. M. Lattimer, and F. Swesty, Nuc. Phys. A 535, 331 (1991).
  * (336) M. Liebendörfer, O. E. B. Messer, A. Mezzacappa, S. W. Bruenn, C. Y. Cardall, and F.-K. Thielemann, Astrophys. J. Suppl. 150, 263 (2004).
  * (337) T. Fischer, S. C. Whitehouse, A. Mezzacappa, F.K. Thielemann, and M. Liebendörfer, Astronomy & Astrophysics 499, 1 (2009).
  * (338) K. Sumiyoshi, S. Yamada, and H. Suzuki, Astrophys. J. 667, 382 (2007).
  * (339) C. Lunardini, 102, 231101,2009
  * (340) S. Horiuchi et al., Mon. Not. R. Astron. Soc. 475, 1363 (2018).
  * (341) B. Müller, H.-T. Janka, and A. Marek, Astrophys. J. 766, 43 (2013).
  * (342) A. Torres-Forné, P. Cerdá-Durán, A. Passamonti, M. Obergaulinger, and J. A. Font, Mon. Not. R. Astron. Soc. 482, 3967 (2019).
  * (343) V. Morozova, D. Radice, A. Burrows, and D. Vartanyan, Astrophys. J. 861, 10 (2018).
  * (344) H. Sotani, T. Kuroda, T. Takiwaki, and K. Kotake, 96,063005,2017
  * (345) E. Abdikamalov, P Pagliaroli. and D. Radice, arXiv:2010.04356.
  * (346) K. Sumiyoshi, and S. Yamada, Astrophys. J. Suppl. 199, 17 (2012).
  * (347) A. Harada et al., Astrophys. J. 872, 181 (2019).
  * (348) H. Nagakura, K. Sumiyoshi, and S. Yamada, Astrophys. J. 878, 160 (2019).
  * (349) H. T. Janka, in Handbook of Supernovae, ed. A. W. Alsabti and P. Murdin (Springer, Cham), 1575 (2017)
  * (350) B. Müller, Annual Review of Nuclear and Particle Science 69 253 (2019).
  * (351) A. Marek, H. T. Janka, and E. Müller, Astrophys. J. 496, 475 (2009).
  * (352) T. Yokozawa, M. Asano, T. Kayano, Y. Suwa, N. Kanda, Y. Koshio, and M. R. Vagins, Astrophys. J. 811, 86 (2015).
  * (353) Hyper-Kamiokande Proto-Collaboration, K. Abe, et al. arXiv:1805.04163.
  * (354) Hyper-Kamiokande Collaboration, K. Abe, et al. arXiv:2101.05269.
  * (355) S. Al Kharusi, et al. arXiv:2011.00035.
  * (356) J. F. Beacom, and M. R. Vagins, 93,171101,2004
  * (357) M. Ikeda et al., arXiv:1908.11532. [physics.ins-det], accepted for publication in Nucl.Inst.Meth. (2020).
  * (358) K. Sumiyoshi, and S. Yamada, Astrophys. J. Suppl. 199, 17 (2012).
  * (359) H. Nagakura, K. Sumiyoshi, and S. Yamada, Astrophys. J. Suppl. 214, 16 (2014).
  * (360) H. Nagakura, W. Iwakami, S. Furusawa, K. Sumiyoshi, S. Yamada, H. Matsufuru, and A. Imakura, Astrophys. J. Suppl. 229, 42 (2017).
  * (361) H. Nagakura, W. Iwakami, S. Furusawa, H. Okawa, A. Harada, K. Sumiyoshi, S. Yamada, H. Matsufuru, and A. Imakura, Astrophys. J. 854, 136 (2018).
  * (362) J. M. Lattimer, and F. D. Swesty, Nuc. Phys. A 535, 331 (1991).
  * (363) S. Furusawa, K. Sumiyoshi, S. Yamada, and H. Suzuki, Astrophys. J. 772, 95 (2013).
  * (364) S. E. Woosley, A. Heger, and T. A. Weaver, 74,1015,2002
  * (365) A. Harada, H. Nagakura, W. Iwakami, H. Okawa, S. Furusawa, H. Matsufuru, K. Sumiyoshi, and S. Yamada, Astrophys. J. 872, 181 (2019).
  * (366) A. Heger, N. Langer, and S. E. Woosley, Astrophys. J. 528, 368 (2000).
  * (367) H. Nagakura, K. Sumiyoshi, and S. Yamada, Astrophys. J. Lett. 880, L28 (2019).
  * (368) H. Togashi, K. Nakazato, Y. Takehara, S. Yamamuro, H. Suzuki, and M. Takano, Nuc. Phys. A 961, 78 (2017).
  * (369) L. Scheck, K. Kifonidis, H. T. Janka, and E. Mueller, A&A4579632006
  * (370) K. Nakazato, K. Sumiyoshi, H. Suzuki, T. Totani, H. Umeda, and S. Yamada, Astrophys. J. Suppl. 205, 2 (2013).
  * (371) T. Totani, K. Sato, H. E. Dalhed, and J. Wilson, Astrophys. J. 496, 216 (1998).
  * (372) K. Sumiyoshi, S. Yamada, S. Suzuki, H. Shen, S. Chiba, and H. Toki, Astrophys. J. 629, 922 (2005).
  * (373) S. Yamada, Astrophys. J. 475, 720 (1997).
  * (374) H. Suzuki, in Physics and Astrophysics of Neutrinos, ed. M. Fukugita and A. Suzuki (Tokyo: Springer-Verlag), 763 (1994)
  * (375) K. Nakazato, H. Suzuki, and H. Togashi, 97,035804,2018
  * (376) Y. Suwa, K. Sumiyoshi, K. Nakazato, Y. Takahira, Y. Koshio, M. Mori, and R. A. Wendell, Astrophys. J. 881, 139 (2019).
  * (377) K. Sumiyoshi, S. Yamada, and H. Suzuki, Astrophys. J. 667, 382 (2007).
  * (378) K. Sumiyoshi, S. Yamada, H. Suzuki, and S. Chiba, 97,091101,2006
  * (379) K. Nakazato, K. Sumiyoshi, H. Suzuki, and S. Yamada, 81,083009,2010
  * (380) H. Sotani, and K. Sumiyoshi, 100,083008,2019
  * (381) S. Horiuchi, K. Sumiyoshi, K. Nakamura, T. Fischer, A. Summa, T. Takiwaki, H. T. Janka, and K. Kotake, Mon. Not. R. Astron. Soc. 475, 1363 (2018).
  * (382) H. Shen, H. Toki, K. Oyamatsu, and K. Sumiyoshi, Nuc. Phys. A 637, 435 (1998).
  * (383) H. Shen, H. Toki, K. Oyamatsu, and K. Sumiyoshi, Prog. Theo. Phys. 100, 1013 (1998)
  * (384) H. Shen, H. Toki, K. Oyamatsu, and K. Sumiyoshi, Astrophys. J. Suppl. 197, 20 (2011).
  * (385) M. Oertel, M. Hempel, T. Klähn, and S. Typel, 89,015007,2017
  * (386) H. Shen, F. Ji, J. Hu, and K. Sumiyoshi, submitted to Astrophys. J., (2020); arXiv:2001.10143.
  * (387) S. Furusawa, K. Sumiyoshi, S. Yamada, and H. Suzuki, Nuc. Phys. A 957, 188 (2017).
  * (388) S. Furusawa, H. Togashi, H. Nagakura, K. Sumiyoshi, S. Yamada, H. Suzuki, and M. Takano, J Phys. G Nucl. Phys. 44, 094001 (2017)
  * (389) S. Furusawa, H. Togashi, K. Sumiyoshi, H. Saito, H. Suzuki, and S. Yamada, Prog. Theor. Exp. Phys. i, n (i).ress (2020)
  * (390) H. Togashi, K. Nakazato, Y. Takehara, S. Yamamuro, H. Suzuki, and M. Takano, Nuc. Phys. A 961, 78 (2017).
  * (391) T. Dannert, A. Marek, and M. Rampp, Advances in Parallel Computing 25, 305 (2014)
  * (392) H. Matsufuru, and K. Sumiyoshi, In: O. Gervasi et al., (eds) Computational Science and Its Applications– ICCSA 2018, Lecture Notes in Computer Science, vol 10962 (Springer, 2018)
  * (393) H. Matsufuru, and K. Sumiyoshi, Proceedings of the Sixth International Symposium on Computing and Networking Workshops (CANDAR 2018)
  * (394) A. Imakura, T. Sakurai, K. Sumiyoshi, and H. Matsufuru, JSIAM Letters 4, 41 (2012)
  * (395) E. S. Quintana, G. Quintana, X. Sun, and R. Geijn, SIAM J. Sci. Comput. 22(5), 1762,
  * (396) K. Yagi, and T. Tanaka, Phys. Rev. D 81, 064008 (2010) Erratum: [Phys. Rev. D 81, 109902 (2010)] [arXiv:0906.4269 [gr-qc]].
  * (397) S. Khan, K. Chatziioannou, M. Hannam, and F. Ohme, Phys. Rev. D 100, 024059 (2019) [arXiv:1809.10113 [gr-qc]].
  * (398) P. C. Peters, Phys. Rev. 136, B1224 (1964).
  * (399) C. F. B. Macedo, P. Pani, V. Cardoso, and L. C. B. Crispino, Astrophys. J. 774, 48 (2013).
  * (400) H. S. Zhao, and J. Silk, 95,011301,2005
  * (401) G. Bertone, A. R. Zentner, and J. Silk, 72,103517,2005
  * (402) K. Eda, Y. Itoh, S. Kuroyanagi, and J. Silk, 110,221101,2013
  * (403) K. Eda, Y. Itoh, S. Kuroyanagi, and J. Silk, 91,044045,2015
  * (404) X. J. Yue, and W. B. Han, 97,064003,2018
  * (405) O. A Hannuksela, K. C. Y. Ng, and T. G. F. Li, arXiv:1906.11845.
  * (406) B. J. Kavanagh, D. A. Nichols, G. Bertone, and D. Gaggero, arXiv:2002.12811.
  * (407) K. D. Kokkotas, and B. G. Schmidt, Liv. Rev. Rel. 2, 2 (1999).
  * (408) E. Berti, V. Cardoso, and C. M. Will, Phys. Rev. D 73, 064030 (2006).
  * (409) https://pages.jh.edu/~eberti2/ringdown/
  * (410) H. Nakano, H. Takahashi, H. Tagoshi, and M. Sasaki, Phys. Rev. D 68, 102003 (2003).
  * (411) H. Nakano, H. Takahashi, H. Tagoshi, and M. Sasaki, Prog. Theor. Phys. 111, 781 (2004).
  * (412) S. D. Mohanty, Phys. Rev. D 57, 630 (1998).
  * (413) K. Sakai, K. I. Oohara, H. Nakano, M. Kaneyama, and H. Takahashi, Phys. Rev. D 96, 044047 (2017).
  * (414) J. Meidam et al., Phys. Rev. D 97, 044033 (2018).
  * (415) F. Pretorius, Phys. Rev. Lett. 95, 121101 (2005).
  * (416) M. Campanelli, C. O. Lousto, P. Marronetti, and Y. Zlochower, Phys. Rev. Lett. 96, 111101 (2006).
  * (417) J. G. Baker, J. Centrella, D. I. Choi, M. Koppitz, and J. van Meter, Phys. Rev. Lett. 96, 111102 (2006).
  * (418) O. Dreyer, B. J. Kelly, B. Krishnan, L. S. Finn, D. Garrison, and R. Lopez-Aleman, Class. Quant. Grav. 21, 787 (2004).
  * (419) E. Berti, J. Cardoso, E. Cardoso, and M. Cavaglia, Phys. Rev. D 76, 104044 (2007).
  * (420) S. Gossan, J. Veitch, and B. S. Sathyaprakash Phys. Rev. D 85, 124056 (2012).
  * (421) H. Nakano, T. Tanaka, and T. Nakamura, Phys. Rev. D 92, 064003 (2015).
  * (422) H. Nakano, T. Narikawa, K. I. Oohara, K. Sakai, H. a. Shinkai, H. Takahashi, T. Tanaka, N. Uchikata, S. Yamamoto, and T. S. Yamamoto, Phys. Rev. D 99, 124032 (2019).
  * (423) N. Yunes, and F. Pretorius, Phys. Rev. D 80, 122003 (2009) [arXiv:0909.3328 [gr-qc]].
  * (424) C. K. Mishra, K. G. Arun, B. R. Iyer and B. S. Sathyaprakash, 82,064010,2010
  * (425) M. Agathos, W. Del Pozzo, T. G. F. Li, C. Van Den Broeck, J. Veitch and S. Vitale, 89,082001,2014
  * (426) B. P. Abbott et al. [LIGO Scientific and Virgo Collaborations], 123,011102,2019
  * (427) H. Takeda,, S. Morisaki, and A. Nishizawa, arXiv:2010.14538.
  * (428) A. Nishizawa A. Taruya K. Hayama S. Kawamura, and M. A. Sakagami, 79,082002,2009
  * (429) E. Poisson, and C. M. Will, Gravity, (Cambridge Univ. Press, UK. 2014).
  * (430) B. F. Schutz, and M. Tinto, Mon. Not. R. Astron. Soc. 224, 131 (1987).
  * (431) A. Nishizawa, and K. Hayama, 87,062003,2013
  * (432) H. Takeda et al., 98,022008,2018
  * (433) S. Hild et al., Class. Quant. Grav. 28, 094013 (2011).
  * (434) B. P. Abbott et al., Class. Quant. Grav. 34, 044001 (2017).
  * (435) H. Takeda et al., 100,042001,2019
  * (436) Y. Hagihara N. Era D. Iikawa, and H. Asada, 98,064035,2018
  * (437) Y. Hagihara N. Era D. Iikawa A. Nishizawa, and H. Asada, 100,064010,2019
  * (438) Y. Hagihara N. Era D. Iikawa N. Takeda, and H. Asada, 101,041501,2020
  * (439) C. Brans, and R. H. Dicke, Phys. Rev. 124, 925 (1961).
  * (440) C. M. Will, and H. W. Zaglauer, Astrophys. J. 346, 366 (1989).
  * (441) T. Damour, and G. Esposito-Farese, Class. Quant. Grav. 9, 2093 (1992).
  * (442) G. W. Horndeski, Int. J. Theor. Phys. 10, 363 (1974).
  * (443) D. Langlois, and K. Noui, J. Cosmol. Astropart. Phys. 1602, 034 (2016).
  * (444) M. Crisostomi, K. Koyama, and G. Tasinato, J. Cosmol. Astropart. Phys. 1604, 044 (2016).
  * (445) J. Ben Achour, M. Crisostomi, K. Koyama, D. Langlois, K. Noui, and G. Tasinato, JHEP 1612, 100 (2016).
  * (446) T. Kobayashi, Rept. Prog. Phys. 82, no. 8, 086901 (2019).
  * (447) T. Kobayashi, Y. Watanabe, and D. Yamauchi, 91,064013,2015
  * (448) T. Kobayashi, and T. Hiramatsu 97,104012,2018
  * (449) P. Creminelli, M. Lewandowski, G. Tambalo, and F. Vernizzi, J. Cosmol. Astropart. Phys. 1812, 025 (2018).
  * (450) P. Creminelli, G. Tambalo, F. Vernizzi, and V. Yingcharoenrat, J. Cosmol. Astropart. Phys. 1910, 072 (2019).
  * (451) S. Hirano, T. Kobayashi, and D. Yamauchi, 99,104073,2019
  * (452) M. Crisostomi, M. Lewandowski, and F. Vernizzi, 100,024025,2019
  * (453) K. i. Maeda, Phys. Rev. D 39, 3159 (1989).
  * (454) S. Weinberg, Phys. Rev. D 77, 123541 (2008) [arXiv:0804.4291 [hep-th]].
  * (455) C. de Rham, G. Gabadadze, and A. J. Tolley, Phys. Rev. Lett. 106, 231101 (2011) [arXiv:1011.1232 [hep-th]].
  * (456) H. van Dam, and M. J. G. Veltman, Nucl. Phys. B 22, 397 (1970).
  * (457) V. I. Zakharov, JETP Lett. 12, 312 (1970) [Pisma Zh. Eksp. Teor. Fiz. 12, 447 (1970)].
  * (458) A. I. Vainshtein, Phys. Lett. 39B, 393 (1972). doi:10.1016/0370-2693(72)90147-5
  * (459) S. F. Hassan, and R. A. Rosen, JHEP 1202, 126 (2012) [arXiv:1109.3515 [hep-th]].
  * (460) A. De Felice, T. Nakamura, and T Tanaka, PTEP 2014, 043E01 (2014) [arXiv:1304.3920 [gr-qc]].
  * (461) T. Jacobson, and D. Mattingly, 64, 024028, 2001
  * (462) T. Jacobson, PoS QG -PH, 020 (2007)
  * (463) S.M. Carroll, and E.A. Lim, 70, 123525, 2004
  * (464) J. W. Elliott, and G. D. Moore, JHEP 08, 066 (2005)
  * (465) C.M. Will, Living Rev. Rel. 17, 4 (2014)
  * (466) R.E. Rutledge, D.B. Fox, S.R. Kulkarni, B.A. Jacoby, D.C. Cognard, D.C. Backer, and S.S. Murry, Astrophys. J. 613, 522 (2004).
  * (467) M. Bailes, S. Johnston, J.F. Bell, B.W. Lorimer, B.W. Stappers, R.N. Manchester, A.G. Lyne, L. Nicastro, N. DAmico, and B.M. Gaensler, Astrophys. J. 481, 386 (1997).
  * (468) L. Shao, and N. Wex, Class. Quant. Grav. 29, 215018 (2012).
  * (469) L. Shao, R.N. Caballero, M. Kramer, N. Wex, D.J. Champion, and A. Jessner, Class. Quant. Grav. 30, 165019 (2013).
  * (470) T. Damour, and G. Esposito-Farese, 46, 4128, 1992
  * (471) K. Yagi, D. Blas, E. Barausse, and N. Yunes, 89, 084067, 2014, Erratum: [Phys. Rev. D 90, 069902 (2014)] Erratum: [Phys. Rev. D 90, 069901 (2014)]
  * (472) A.E. Gumrukcuoglu, M. Saravani, and T.P. Sotiriou, 97, 024032, 2018
  * (473) J. Oost, S. Mukohyama, and A. Wang, 97, 124023, 2018
  * (474) L. Sampson, N. Cornish, and N. Yunes, Phys. Rev. D 89, 064037 (2014) [arXiv:1311.4898 [gr-qc]].
  * (475) L. Sampson, N. Yunes, N. Cornish, M. Ponce, E. Barausse, A. Klein, C. Palenzuela, and L. Lehner, Phys. Rev. D 90, 124091 (2014) [arXiv:1407.7038 [gr-qc]].
  * (476) F. M. Ramazano?lu, and F. Pretorius, Phys. Rev. D 93, 064005 (2016) [arXiv:1601.07475 [gr-qc]].
  * (477) J. Antoniadis et al., Science 340, 6131 (2013) [arXiv:1304.6875 [astro-ph.HE]].
  * (478) A Arvanitaki, M. Baryakhtar, and X. Huang, Phys. Rev. D 91, 084011 (2015) [arXiv:1411.2263 [hep-ph]].
  * (479) R. Brito, S. Ghosh, E. Barausse, E. Berti, V. Cardoso, I. Dvorkin, A. Klein, and P. Pani, Phys. Rev. D 96, 064050 (2017) [arXiv:1706.06311 [gr-qc]].
  * (480) R. Narayan, and J. E. McClintock, arXiv:1312.6698 [astro-ph.HE].
  * (481) K. Yamada, T. Narikawa, and T. Tanaka, Prog. Theor. Exp. Phys. 2019, , (2019).03E01 (2019) [arXiv:1905.11859 [gr-qc]].
  * (482) K. Yagi, Phys. Rev. D 86, 081504 (2012) [arXiv:1204.4524 [gr-qc]].
  * (483) https://www.gw-openscience.org/about/
  * (484) N. Yunes, K. Yagi, and F. Pretorius, Phys. Rev. D 94, 084002 (2016) [arXiv:1603.08955 [gr-qc]].
  * (485) L. C. Stein, and K. Yagi, Phys. Rev. D 89, 044026 (2014) [arXiv:1310.6743 [gr-qc]].
  * (486) K. Prabhu, and L. C. Stein, Phys. Rev. D 98, 021503 (2018) [arXiv:1805.02668 [gr-qc]].
  * (487) K. Yagi, L. C. Stein, N. Yunes, and T. Tanaka, Phys. Rev. D 85, 064022 (2012) Erratum: [Phys. Rev. D 93, 029902 (2016)] [arXiv:1110.5950 [gr-qc]].
  * (488) E. Berti, K. Yagi, and N. Yunes, Gen. Rel. Grav. 50, 46 (2018) [arXiv:1801.03208 [gr-qc]].
  * (489) R. Nair, S. Perkins, H. O. Silva, and N. Yunes, Phys. Rev. Lett. 123, 191101 (2019) [arXiv:1905.00870 [gr-qc]].
  * (490) S. Tahura, K. Yagi, and Z. Carson, Phys. Rev. D 100, 104001 (2019) [arXiv:1907.10059 [gr-qc]].
  * (491) Z. Carson, B. C. Seymour, and K. Yagi, Class. Quant. Grav. 37, 065008 (2020) [arXiv:1907.03897 [gr-qc]].
  * (492) G. Gnocchi, A. Maselli, T. Abdelsalhin, N. Giacobbo, and M. Mapelli, Phys. Rev. D 100, 064024 (2019) [arXiv:1905.13460 [gr-qc]].
  * (493) A. Nishizawa, and T. Kobayashi, 98,124018,2018
  * (494) M. Crisostomi, K. Noui, C. Charmousis, and D. Langlois, 97,044034,2018
  * (495) A. De Felice, D. Langlois, S. Mukohyama, K. Noui, and A. Wang, 98,084024,2018
  * (496) P. Creminelli, J. Gleyzes, J. Noreña, and F. Vernizzi, 113,231301,2014
  * (497) K. Yamada, and T. Tanaka, arXiv:2006.11086 [gr-qc]..
  * (498) K. Yagi, and H. Yang, Phys. Rev. D 97, 104018 (2018) [arXiv:1712.00682 [gr-qc]].
  * (499) V. Cardoso, E. Franzin, and P. Pani, 116,171101,2016 [Erratum:117,089902,2016]
  * (500) V. Cardoso, S. Hopper, C. F. B. Macedo, C. Palenzuela, and P. Pani, 94,084031,2016.
  * (501) L. Hui, D. Kabat, and S. S. C. Wong, J. Cosmol. Astropart. Phys. 1912, 2019 (020).
  * (502) J. Abedi, H. Dykaar, and N. Afshordi, 96,082004,2017
  * (503) J. Westerweck et al., 97,125037,2018
  * (504) A. B. Nielsen, C. D. Capano, O. Birnholtz, and J. Westerweck, 99,104012,2019
  * (505) R. K. L. Lo, T. G. F. Li, and A. J. Weinstein, 99,084052,2019
  * (506) H. Nakano, H. Sago, H. Tagoshi, and T. Tanaka, Prog. Theor. Exp. Phys. 2017, 071E01 (2017).
  * (507) N. Uchikata, H. Nakano, T. Narikawa, N. Sago, H. Tagoshi, and T. Tanaka, 100,062006,2019
  * (508) K. W. Tsang et al., 98,024023,2018
  * (509) K. W. Tsang et al., 101,064012,2020
  * (510) A. Testa, and P. Pani, 98,044018,2018
  * (511) E. Maggio, A. Testa, S. Bhagwat, and P. Pani, 100,064056,2019
  * (512) V, Cardoso, and P. Pani, Liv. Rev. Rel. 22, 4 (2019).
  * (513) D.J.E. Marsh, Physics Reports 643, 1 (2016).
  * (514) D. Yoshida, and J. Soda, Prog. Theor. Exp. Phys. 2018, 041E01 (2018).
  * (515) D. Yoshida, and J. Soda, Int. J. Mod. Phys. D 27, 1850096 (2018).
  * (516) J. Soda, and D. Yoshida, Galaxies 5, 96 (2017).
  * (517) Y. Ali-Haimoud, and Y. Chen, Phys. Rev. D 84, 124033 (2011)
  * (518) B. Carr, K. Kohri, Y. Sendouda, and J. Yokoyama, arXiv:2002.12778 [astro-ph.CO]..
  * (519) T. Nakamura, M. Sasaki, T. Tanaka, and K. S. Thorne, Astrophys. J. Lett. 487, 139 (1997).
  * (520) B. P. Abbott et al. [LIGO Scientific and Virgo Collaborations], Phys. Rev. Lett. 123, 161102 (2019) [arXiv:1904.08976 [astro-ph.CO]].
  * (521) T. Nakamura et al., Prog. Theor. Exp. Phys. 2016, 093E01 (2016).
  * (522) B. Kocsis, T. Suyama, T. Tanaka, and S. Yokoyama, Astrophys. J. 854, 41 (2018).
  * (523) J. Garriga, and N. Triantafyllou, J. Cosmol. Astropart. Phys. 09, 043 (2019).
  * (524) S. Bird, I. Cholis, J. B. Munoz, Y. Ali-Haimoud, M. Kamionkowski, E. D. Kovetz, A. Raccanelli, and A. G. Riess, Phys. Rev. Lett. 116, 201301 (2016)
  * (525) R. M. O’Leary, Y. Meiron, and B. Kocsis, Astrophys. J. Lett. 824, 12 (2016).
  * (526) L. Gondán, B. Kocsis, P. Raffai, and Z. Frei, Astrophys. J. 860, 5 (2018)
  * (527) A. D. Gow, C. T. Byrnes, A. Hall, and J. A. Peacock, J. Cosmol. Astropart. Phys. 01, 031 (2020).
  * (528) T. Chiba, and S. Yokoyama, Prog. Theor. Exp. Phys. 2017, 083E01 (2017).
  * (529) M. Mirbabayi, A. Gruzinov, and J. Norena, J. Cosmol. Astropart. Phys. 03, 017 (2020).
  * (530) V. De Luca, V. Desjacques, G. Franciolini, A. Malhotra, and A. Riotto, J. Cosmol. Astropart. Phys. 05, 018 (2019).
  * (531) M. He, and T. Suyama, 100,063520,2019
  * (532) T. Harada, C. M. Yoo, K. Kohri, and K. I. Nakao, 96,083517,2017 Erratum: 99,069904,2019
  * (533) S. Wang, T. Terada, and K. Kohri, 99,103531,2019
  * (534) M. Sasaki, T. Suyama, T. Tanaka, and S. Yokoyama, 117,061101,2016 Erratum: [Phys. Rev. Lett. 121, 059901 (2018)]
  * (535) S. Wang, Y. F. Wang, Q. G. Huang, and T. G. F. Li, 120,191102,2018
  * (536) P. Ajith et al., 106,241101,2011
  * (537) P. Ajith et al., 77,104017,2008 Erratum: [Phys. Rev. D 79, 129901 (2009)].
  * (538) B. J. Carr, K. Kohri, Y. Sendouda, and J. Yokoyama, 81,104019,2010


Discrete Mathematics Letters
www.dmlett.com Discrete Math. Lett. X (202X) XX–XX

Lattice paths with a first return decomposition constrained by the maximal
height of a pattern

Jean-Luc Baril1,***Corresponding author (barjl@u-bourgogne.fr), Sergey
Kirgizov1

1LIB, Université de Bourgogne Franche-Comté, B.P. 47 870, 21078 Dijon Cedex
France

(Received: Day Month 202X. Received in revised form: Day Month 202X. Accepted:
Day Month 202X. Published online: Day Month 202X.)

###### Abstract

We consider the system of equations
$A_{k}(x)=p(x)A_{k-1}(x)(q(x)+\sum_{i=0}^{k}A_{i}(x))$ for $k\geqslant r+1$
where $A_{i}(x)$, $0\leqslant i\leqslant r$, are some given functions and show
how to obtain a close form for $A(x)=\sum_{k\geqslant 0}A_{k}(x)$. We apply
this general result to the enumeration of certain subsets of Dyck, Motzkin,
skew Dyck, and skew Motzkin paths, defined recursively according to the first
return decomposition with a monotonically non-increasing condition relative to
the maximal ordinate reached by an occurrence of a given pattern $\pi$.
Keywords: Enumeration, Dyck and Motzkin paths, first return decomposition,
statistics, height, pattern.
2020 Mathematics Subject Classification: 05A15, 05A19, 68R05.

## 1 Introduction and notations

Let $\mathcal{A}$ be a combinatorial class, that is a collection of similar
objects (lattices, trees, permutations, words) endowed with a size function
$\ell$ whose values are non-negative integers, so that the number
$|\ell^{-1}(n)|$ of objects of a given size $n$ is finite. With $\mathcal{A}$
we associate the generating function

$A(x)=\sum\limits_{a\in\mathcal{A}}x^{\ell(a)}=\sum\limits_{n\geqslant
0}|\ell^{-1}(n)|x^{n},$

which appears to be the main source of interest for researchers working in
enumerative combinatorics.

Given a function $s:\mathcal{A}\rightarrow\mathbb{N}$, called statistic, and
an integer $k\geqslant 0$, we define the combinatorial class $\mathcal{A}_{k}$
consisting of objects $a\in\mathcal{A}$ such that $s(a)=k$, and associate the
following generating function with this class:

$A_{k}(x)=\sum\limits_{a\in\mathcal{A}_{k}}x^{\ell(a)},\mbox{ which implies
}A(x)=\sum\limits_{k\geqslant 0}A_{k}(x).$

In three recent articles [1, 2, 6], the authors enumerate particular
subclasses of lattice paths (Dyck, Motzkin, $2$-Motzkin and Schröder paths)
defined recursively according to the first return decomposition with a
condition on the path height. More precisely, in the first paper, they focus
on the Dyck path set $\mathcal{D}^{h,\geqslant}$ consisting of the union of
the empty path with all Dyck paths $P$ having a first return decomposition
$P=U\alpha D\beta$ satisfying the conditions:

$\begin{cases}\alpha,\beta\in\mathcal{D}^{h,\geqslant},\\\ h(U\alpha
D)\geqslant h(\beta),\\\ \end{cases}$ (1)

where $h$ is the height statistic, i.e. the maximal ordinate reached by a
path. In these studies, the authors need to consider a system of equations
involving the generating functions $D_{k}(x)$, $k\geqslant 0$, for the subset
of paths $P\in\mathcal{D}^{h,\geqslant}$ satisfying $h(P)=k$:

$D_{k}(x)=x\cdot D_{k-1}(x)\cdot\sum\limits_{i=0}^{k}D_{i}(x)\mbox{ for
}k\geqslant 1$ (2)

anchored with initial condition $D_{0}(x)=1$.

They deduce algebraically a close form of the generating function
$D(x)=\sum_{k\geqslant 0}D_{k}(x)$ for $\mathcal{D}^{h,\geqslant}$ by solving
System (2), and prove that $\mathcal{D}^{h,\geqslant}$ is enumerated by the
Motzkin sequence, that is A001006 in the On-Line Encyclopedia of Integer
Sequences (OEIS) [13]. The second paper is a similar study in the context of
Motzkin and Schröder paths.

Inspired by these two works, the motivation of the paper is to extend such
studies by investigating the solutions of a more general system defined as
follows. For an integer $r\geqslant 0$ and two functions $p(x)$ and $q(x)$, we
consider the system of equations:

$A_{k}(x)=p(x)A_{k-1}(x)\left(q(x)+\sum\limits_{i=0}^{k}A_{i}(x)\right)\mbox{,
for }k\geqslant r+1,$ (3)

anchored with $A_{i}(x)=u_{i}(x)$ for $0\leqslant i\leqslant r$ where
$u_{i}(x)$, $0\leqslant i\leqslant r$, are some given functions. For the sake
of brevity, we set $u=u_{r}(x)$, $v=\sum_{i=0}^{r}u_{i}(x)-u$, $p=p(x)$ and
$q=q(x)$.

Before considering how Equation (3) is related to particular sets of lattice
paths defined in the same way as the set $\mathcal{D}^{h,\geqslant}$, let us
recall some definitions and notations. A skew Motzkin path (see [7]) of length
$n\geqslant 0$ is a lattice path in the quarter plane starting at point
$(0,0)$, ending on the $x$-axis (but never going below), consisting of $n$
steps of the four following types: up steps $U=(1,1)$, down steps $D=(1,-1)$,
flat steps $F=(1,0)$ and left steps $L=(-1,-1)$, such that left and up steps
never overlap. Let $\mathcal{SM}$ be the set of all skew Motzkin paths of any
length. A Motzkin path is a skew Motzkin path with no left steps. Let
$\mathcal{M}$ be the set of all Motzkin paths. A Dyck path is a Motzkin path
with no flat steps. Let $\mathcal{D}$ be the set of all Dyck paths. A skew
Dyck path is a skew Motzkin path with no flat steps. Let $\mathcal{SD}$ be the
set of all skew Dyck paths. Obviously, we have
$\mathcal{D}\subset\mathcal{SD}\subset\mathcal{SM}$ and
$\mathcal{D}\subset\mathcal{M}\subset\mathcal{SM}$.

A pattern of length $n\geqslant 1$ in a lattice path $P$ consists of $n$
consecutive steps. The height of an occurrence of a pattern in a given path is
the maximal ordinate reached by its points. For a pattern $\pi$, we define the
statistic $h_{\pi}$ on lattice paths so that $h_{\pi}(P)$ is the maximal
height reached by the occurrences of $\pi$ in $P$. The amplitude $r_{\pi}$ of
a pattern $\pi$ is the height of the path $\pi$ considered as a path touching
the $x$-axis in the quarter plane. For instance, the path $P=UUDUUDUDDD$
contains the pattern $UUD$ and $h_{UUD}(P)=3$, while the amplitude of $UUD$ is
$r_{UUD}=2$.

The paper is organized as follows. In Section 2, we show how we can obtain a
close form for $A(x)$ defined by the system (3). In Section 3, we provide
several concrete applications in the context of lattices paths (Dyck, Motzkin,
skew Dyck, and skew Motzkin paths) for the statistic $h_{\pi}$ giving the
maximal ordinate reached by the occurrence of $\pi$ in a path. Finally in
Section 4, we provide some possible future research directions.

## 2 General result

For $k\geqslant 0$, we set $B_{k}(x)=\sum_{i=0}^{k}A_{i}(x)$, and thus we have
$A(x)=\lim_{k\rightarrow\infty}B_{k}(x)$. The next theorem provides a close
form of $A(x)$ whenever Equation (3) admits a solution, that is when
$1-A_{k}(x)p(x)\neq 0$ for all $k\geqslant r$.

######  Theorem 2.1.

If Equation (3) has a solution then for $k\geqslant r+1$ we have

$B_{k}(x)=\frac{a+bB_{k-1}(x)}{c+dB_{k-1}(x)},$ (4)

where

$\begin{cases}a=p^{2}qv\left(q+u+v\right)-pqu-u-v\\\ b=-p\left({\it
pq}+1\right)\left(q+v+u\right)\\\ c=-p^{2}v\left(q+u+v\right)-qp-pv-1\\\
d={p}^{2}\left(q+v+u\right).\end{cases}$

Moreover
$A(x)=\lim\limits_{k\rightarrow\infty}B_{k}(x)=\sum_{k=0}^{\infty}A_{i}(x)$ is
a root of the polynomial

$d\cdot A(x)^{2}+(c-b)\cdot A(x)-a.$ (5)

###### Proof.

Using $B_{r}(x)=u+v$, we solve the following linear system for $a,b,c,d$

$\begin{cases}B_{r+1}(x)(c+dB_{r}(x))=a+bB_{r}(x)\\\
B_{r+2}(x)(c+dB_{r+1}(x))=a+bB_{r+1}(x)\\\
B_{r+3}(x)(c+dB_{r+2}(x))=a+bB_{r+2}(x),\\\ \end{cases}$

and obtain (modulo a multiplicative factor) the claimed values. However, it
remains to prove that

$B_{k}(x)=\frac{a+bB_{k-1}(x)}{c+dB_{k-1}(x)}$

for any $k\geqslant r+1$. We proceed by induction on $k$. Obviously, for
$k=r+1$ it is true. So, we assume that the formula is true for $k\leqslant n$
and we prove that this is also true for $k=n+1$. More precisely, we will prove
that $R=(c+dB_{n}(x))B_{n+1}(x)-(a+bB_{n}(x))$ equals zero.

Considering Equation (3), we have
$B_{n+1}(x)=\frac{pqA_{n}(x)+B_{n}(x)}{1-pA_{n}(x)}$. The recurrence
hypothesis provides $B_{n}(x)=\frac{a+bB_{n-1}(x)}{c+dB_{n-1}(x)}$, and we
have $A_{n}(x)=B_{n}(x)-B_{n-1}(x)$. Replacing respectively $B_{n+1}(x)$,
$B_{n}(x)$ and $A_{n}(x)$ in $R$, and multiplying it by $1-p\cdot A_{n}(x)\neq
0$, we obtain

$\left(qp\left({\frac{a+bS}{c+dS}}-S\right)+{\frac{a+bS}{c+dS}}\right)\left(c+{\frac{d\left(a+bS\right)}{c+dS}}\right)-\left(a+{\frac{b\left(a+bS\right)}{c+dS}}\right)\left(1-p\left({\frac{a+bS}{c+dS}}-S\right)\right),$

where $S=B_{n-1}(x)$. A simplification of this expression (whatever the value
of $S$) implies that $R=0$, which completes the induction. Finally, taking the
limit when $k\rightarrow\infty$ of both sides of
$B_{k}(x)=\frac{a+bB_{k-1}(x)}{c+dB_{k-1}(x)}$, and using the fact that
$A(x)=\lim\limits_{k\rightarrow\infty}B_{k}(x)$, one gets

$d\cdot A(x)^{2}+(c-b)\cdot A(x)-a=0.$

Notice that an alternative proof can be obtained by using Chebyshev
polynomials of the second kind (see Proposition D.5 p. 508 in [10]). ∎

## 3 Some applications

In this section, we apply Theorem 2.1 to study special kinds of classes of
lattices paths: Dyck, Motzkin, skew Dyck, and skew Motzkin paths. We extend
the definition (1) to these paths using the maximal height reached by the
occurrences of $\pi$, the statistic $h_{\pi}$ instead of statistic $h$. Notice
that the statistic $h$ equals the statistic $h_{U}$ on all considered paths,
which allows us to focus only on $h_{\pi}$. We will deal with patterns $\pi$
of length at most three.

Given a pattern $\pi$, we define the set $\mathcal{A}^{h_{\pi},\geqslant}$ as
the union of the empty path with paths $P$ satisfying a recurrence condition
($R$), which depends on the first return decomposition of a path. The four
cases are described in the following table with
$\alpha,\beta,\gamma\in\mathcal{A}^{h_{\pi},\geqslant}$.

Paths | First return decomposition with recurrence condition ($R$)
---|---
Dyck |  $P=U\alpha D\beta$ with $h_{\pi}(U\alpha D)\geqslant h_{\pi}(\beta)$
Motzkin |  $\begin{cases}P=U\alpha D\beta\\\ P=F\gamma\\\ \end{cases}$ with $h_{\pi}(U\alpha D)\geqslant h_{\pi}(\beta)$ and $h_{\pi}(F)\geqslant h_{\pi}(\gamma)$
Skew Dyck |  $\begin{cases}P=U\alpha D\beta\\\ P=U\alpha L\\\ \end{cases}$ $\mbox{with }\begin{cases}h_{\pi}(U\alpha D)\geqslant h_{\pi}(\beta)\\\ \mbox{ and }\alpha\neq\epsilon\mbox{ for the last case}\\\ \end{cases}$
Skew Motzkin |  $\begin{cases}P=U\alpha D\beta\\\ P=F\gamma\\\ P=U\alpha L\\\ P=U\alpha LF\gamma\\\ \end{cases}$ $\mbox{with }\begin{cases}h_{\pi}(U\alpha D)\geqslant h_{\pi}(\beta)\mbox{ and }h_{\pi}(F)\geqslant h_{\pi}(\gamma)\\\ \mbox{ and }\alpha\neq\epsilon\mbox{ for the last two cases}\\\ \end{cases}$

We keep the notations used in the previous sections. The generating functions
$A_{k}(x)$, $k\geqslant 0$, correspond to the sets $\mathcal{A}_{k}$ of Dyck
paths $P\in\mathcal{A}^{h_{\pi},\geqslant}$ so that $h_{\pi}(P)=k$. We set
$A(x)=\sum_{k\geqslant 0}A_{k}(x)$ and $B_{k}(x)=\sum_{i=0}^{k}A_{i}(x)$.

In any case, the set $\mathcal{A}_{0}$ of paths
$P\in\mathcal{A}^{h_{\pi},\geqslant}$ such that $h_{\pi}(P)=0$ is the set of
paths having no occurrence of $\pi$ at height at least one. In the case where
the amplitude of $\pi$ is at least one, $\mathcal{A}_{0}$ consists of the
paths avoiding $\pi$. So, we can easily obtain $A_{0}(x)$ using the first
return decomposition of such paths. For Dyck and Motzkin paths, these
generating functions (for short g.f.) are already known (see [3, 4, 8, 9, 11,
12]). For skew Dyck and Motzkin paths, we can obtain them by similar methods,
which are classic and present no difficulty. So, we do not give here all the
details to get $A_{0}(x)$.

Note that the maximal height of an occurrence of pattern $\pi$ in $P$ is
necessarily greater or equal than its amplitude $r_{\pi}$. This means that the
generating functions for the sets $\mathcal{A}_{k}$, $1\leqslant k<r_{\pi}$
satisfy $A_{k}(x)=0$. Finally, if $r_{\pi}\geqslant 1$ (which is equivalent to
$\pi\neq F^{k}$ for all $k\geqslant 1$) then $\mathcal{A}_{r_{\pi}}$, is the
set of paths $P\in\mathcal{A}^{h_{\pi},\geqslant}$ having at least one
occurrence of $\pi$ and such that $h_{\pi}(P)=r_{\pi}$, i.e. all occurrences
of $\pi$ touch the $x$-axis in $P$. Similar methods as for $A_{0}(x)$ can be
used in order to obtain $A_{r_{\pi}}(x)$. Theorems 3.1 and 3.2 focus on two
examples of these methods in the context of Dyck paths.

###  3.1 Dyck and Motzkin paths

First we consider Dyck paths. For a given pattern $\pi$, Condition ($R$)
implies that for $k\geqslant r_{\pi}+1$ we have

$A_{k}(x)=x\cdot A_{k-1}(x)\cdot\sum_{i=0}^{k}A_{i}(x)$

which is a particular case of Equation (3) for $r=r_{\pi}$, $p(x)=x$,
$q(x)=0$, $u=A_{r_{\pi}}(x)$, and $v=\sum_{i=0}^{r}A_{i}(x)-u=A_{0}(x)$. From
Theorem 2.1, we can easily deduce the following.

######  Corollary 3.1.

$A(x)={\frac{{x}^{2}uv+{x}^{2}{v}^{2}-ux+1-\sqrt{\Delta}}{2{x}^{2}\left(v+u\right)}}$
(6)

with
$\Delta={u}^{2}{v}^{2}{x}^{4}+2\,u{v}^{3}{x}^{4}+{v}^{4}{x}^{4}-2\,{u}^{2}v{x}^{3}-2\,u{v}^{2}{x}^{3}-3\,{u}^{2}{x}^{2}-6\,{x}^{2}uv-2\,{x}^{2}{v}^{2}-2\,ux+1$.

In order to convince the reader that all generating functions $A(x)$ can be
obtained easily by calculating algebraically $u$ and $v$, we give here the
methods for the two patterns $UUD$ and $DUU$.

######  Theorem 3.1.

If $\pi=UUD$ then we have $r_{\pi}=2$,
$u=A_{2}(x)={\frac{{x}^{2}}{\left(x-1\right)\left({x}^{2}+x-1\right)}}$,
$A_{1}(x)=0$, and $v=A_{0}(x)=\frac{1}{1-x}$.

###### Proof.

As already mentioned above, the set $\mathcal{A}_{0}$ is the set of Dyck paths
avoiding the pattern $\pi$. So, a nonempty path $P\in\mathcal{A}_{0}$ is of
the form $P=UD\alpha$ where $\alpha\in\mathcal{A}_{0}$, which implies that
$A_{0}(x)=\frac{1}{1-x}$. On the other hand, the set $\mathcal{A}_{1}$ is the
set of Dyck paths $P\in\mathcal{A}^{h_{\pi},\geqslant}$ such that
$h_{UUD}(P)=1$, which cannot be possible because the amplitude $r_{\pi}=2$;
so, $A_{1}(x)=0$. Finally, the set $\mathcal{A}_{2}$ is the set of Dyck paths
$P\in\mathcal{A}^{h_{\pi},\geqslant}$ such that $h_{UUD}(P)=2$, which means
that $P$ can be written $U\alpha D\beta$ with
$\alpha\in\mathcal{A}_{0}\backslash\epsilon$ and
$\beta\in\mathcal{A}_{2}\cup\mathcal{A}_{1}\cup\mathcal{A}_{0}$. So, we have
the functional equation $A_{2}(x)=x(A_{0}(x)-1)(A_{2}(x)+A_{1}(x)+A_{0}(x))$,
which gives the expected result. ∎

######  Theorem 3.2.

If $\pi=DUU$ then we have $r_{\pi}=2$,
$u=A_{2}(x)={\frac{{x}^{3}\left(1-x\right)}{\left(2\,x-1\right)^{2}}}$,
$A_{1}(x)=0$, and $v=A_{0}(x)=\frac{x-1}{2x-1}$.

###### Proof.

The set $\mathcal{A}_{0}$ is the set of Dyck paths avoiding the pattern $DUU$.
So, a nonempty path $P\in\mathcal{A}_{0}$ is of the form $P=U\alpha D\beta$
where $\alpha\in\mathcal{A}_{0}$ and $\beta=(UD)^{k}$ for some $k\geqslant 0$,
which implies that $A_{0}(x)=1+\frac{xA_{0}(x)}{1-x}$, and thus
$A_{0}(x)=\frac{x-1}{2x-1}$. On the other hand, the set $\mathcal{A}_{1}$ is
the set of Dyck paths $P\in\mathcal{A}^{h_{\pi},\geqslant}$ such that
$h_{DUU}(P)=1$, which cannot be possible because the amplitude $r_{\pi}=2$;
so, $A_{1}(x)=0$. Finally, the set $\mathcal{A}_{2}$ is the set of Dyck paths
$P\in\mathcal{A}^{h_{\pi},\geqslant}$ such that $h_{DUU}(P)=2$, which means
that $P$ can be written $U\alpha DU\beta D$ with $\alpha\in\mathcal{A}_{0}$
and $\beta\in\mathcal{A}_{0}\backslash\\{\epsilon\\}$.

So, we have the functional equation $A_{2}(x)=x^{2}A_{0}(x)(A_{0}(x)-1)$,
which gives the expected result. ∎

So, we present in the following table the first values of the sequences
corresponding to the cardinality of $\mathcal{A}^{h_{\pi},\geqslant}$ for
patterns $\pi$ of length at most three.

Statistic $h_{\pi}$ | $a_{n},~{}1\leqslant n\leqslant 9$ | OEIS
---|---|---
$h$, $U$, $D$, $UD$, $UU$, $DD$, $UDD$, $UUD$ | 1, 2, 4, 9, 21, 51, 127, 323 | A001006
$DU$ | 1, 2, 4, 8, 17, 39, 94, 233, 588 |
$UUU$, $DDD$ | 1, 2, 5, 13, 35, 97, 274, 786, 2282 |
$UDU$, $DUD$ | 1, 2, 4, 9, 22, 56, 146, 389, 1053 |
$DUU$, $DDU$ | 1, 2, 5, 13, 34, 89, 234, 621, 1669 |

Now, we examine the set of Motzkin paths. For a given pattern $\pi$, Condition
($R$) implies that for $k\geqslant r_{\pi}+1$ we have

$A_{k}(x)=x^{2}\cdot A_{k-1}(x)\cdot\sum\limits_{i=0}^{k}A_{i}(x)$

which is a particular case of Equation (3) for $r=r_{\pi}$, $p(x)=x^{2}$,
$q(x)=0$, $u=A_{r_{\pi}}(x)$, and $v=A_{0}(x)$. Then, the generating function
$A(x)$ is the generating function found above in the context of Dyck paths
(see ($6$)) applied on the variable $x^{2}$ ($x$ is not replaced with $x^{2}$
in $u$ and $v$). The following table gives the first values of generating
functions $A(x)$ obtained for all patterns of length at most two.

Statistic $h_{\pi}$ | $a_{n},~{}1\leqslant n\leqslant 9$ | OEIS
---|---|---
$h$, $U$, $D$ | 1, 2, 3, 6, 11, 22, 43, 87, 176 | A026418
$F$ | 1, 2, 4, 8, 17, 36, 78, 170, 374 |
$UU$, $DD$ | 1, 2, 4, 9, 20, 46, 107, 253, 604 |
$UD$ | 1, 2, 3, 7, 13, 29, 61, 138, 308 |
$DU$ | 1, 2, 4, 9, 20, 46, 107, 252, 599 |
$UF$, $FD$ | 1, 2, 4, 8, 17, 37, 82, 185, 422 |
$DF$, $FU$ | 1, 2, 4, 8, 17, 36, 79, 175, 395 |
$FF$ | 1, 2, 4, 9, 20, 47, 111, 268, 653 |

Looking at the two tables above, one observes that some patterns have same
sequences, for example $DUU$ and $DDU$, $UF$ and $FD$. We actually can
generalize this as follows. Let $\pi=\pi_{1}\pi_{2}\ldots\pi_{k}$ be a pattern
of length $k$ and $C(\pi)$ be the reversed complement of $\pi$, that is
$C(\pi)=\overline{\pi}_{k}\overline{\pi}_{k-1}\cdots\overline{\pi}_{1}$ where

$\overline{x}=\begin{cases}F\,\text{ if }x=F,\\\ D\,\text{ if }x=U,\\\
U\,\text{ if }x=D.\\\ \end{cases}$

For instance we have $C(UFDD)=UUFD$.

######  Theorem 3.3.

If ${}_{\pi}A(x)$ is the generating function for the set
$\mathcal{A}^{h_{\pi},\geqslant}$, then we have

${}_{\pi}A(x)={}_{C(\pi)}A(x).$

###### Proof.

For short we set $\sigma=C(\pi)$. Since the reversed complement operation
preserves the amplitude, we have $r_{\pi}=r_{\sigma}$. Now, we will exhibit a
bijection $\phi$ from $\mathcal{A}^{h_{\pi},\geqslant}$ to
$\mathcal{A}^{h_{\sigma},\geqslant}$. Suppose $\pi\neq F^{k},k\geqslant 1$, if
a path $P\in\mathcal{A}^{h_{\pi},\geqslant}$ does not contain $\pi$, we set
$\phi(P)=C(P)$. It avoids $\sigma$ and belongs to
$\mathcal{A}^{h_{\sigma},\geqslant}$. So, we have
${}_{\pi}A_{0}(x)={}_{\sigma}A_{0}(x)$. If $\pi=F^{k}$ for some $k\geqslant
1$, we have $r_{\pi}=0$ and we also set $\phi(P)=C(P)$. We easily deduce again
that ${}_{\pi}A_{0}(x)={}_{\sigma}A_{0}(x)$.

Now, let us consider the case where $r_{\pi}\geqslant 1$ and prove that g.f.
${}_{\pi}A_{r_{\pi}}$ for pattern $\pi$ is actually equals
${}_{\sigma}A_{r_{\sigma}}$ for pattern $\sigma$. To do this we consider a
path $P\in\mathcal{A}^{h_{\pi},\geqslant}$ having at least one occurrence of
$\pi$ and such that $h_{\pi}(P)=r_{\pi}$. We can write $P$ either as ($i$)
$P=F\alpha$ or ($ii$) $P=U\alpha D\beta$ where
$\alpha,\beta\in\mathcal{A}^{h_{\pi},\geqslant}$.

Case ($i$). We assume $P=F\alpha$ and $h_{\pi}(F)\geqslant h_{\pi}(\alpha)$.
Since the pattern $\pi$ is not $F^{k}$ (because $r_{\pi}\geqslant 1$), we
necessarily have $h_{\pi}(F)=0=h_{\pi}(\alpha)$ which means that $\alpha$
avoids $\pi$. Therefore, the pattern $\pi$ occurs once in $P$ and it straddles
$F$ and $\alpha$. We deduce that $C(P)$ belongs to
$\mathcal{A}^{h_{\sigma},\geqslant}$ and it has at least one occurrence of
$\sigma$ such that $h_{\sigma}(C(P))=r_{\sigma}$. So in this case, we define
the function $\phi$ with $\phi(P)=C(P)$.

Case ($ii$). We assume $P=U\alpha D\beta$ and $h_{\pi}(U\alpha D)\geqslant
h_{\pi}(\beta)$. If $h_{\pi}(U\alpha D)=0$ then we have $h_{\pi}(\beta)=0$ and
using the same argument as previous, $C(P)$ belongs to
$\mathcal{A}^{h_{\sigma},\geqslant}$ and it has exactly one occurrence of
$\sigma$ straddling $U\alpha D$ and $\beta$, and such that
$h_{\sigma}(C(P))=r_{\sigma}$. In this subcase, we set $\phi(P)=C(P)$. If
$h_{\pi}(U\alpha D)=r_{\pi}$ then the occurrence of $\pi$ in $U\alpha D$ is at
the beginning or at the end (or touches both extremities) of $U\alpha D$ since
it must touch the $x$-axis, but the occurrence does not straddle $U\alpha D$
and $\beta$. This means that $\alpha$ avoids $\pi$ and $\beta$ either avoids
$\pi$ (i.e. $h_{\pi}(\beta)=0$, as $\pi\neq F^{k}$) or contains $\pi$ with
$h_{\pi}(\beta)=r_{\pi}$. In this subcase, we recursively define $\phi$ as
$\phi(P)=UC(\alpha)D\phi(\beta)$. It belongs to
$\mathcal{A}^{h_{\sigma},\geqslant}$ and has at least one occurrence of
$\sigma$ such that $h_{\sigma}(\phi(P))=r_{\sigma}$. So, $\phi$ is a one-to-
one correspondence between paths in $\mathcal{A}^{h_{\pi},\geqslant}$ having
at least one occurrence of $\pi$ such that $h_{\pi}(\phi(P))=r_{\pi}$ and
paths $\mathcal{A}^{h_{\sigma},\geqslant}$ having at least one occurrence of
$\sigma$ such that $h_{\sigma}(\phi(P))=r_{\sigma}$. So, we have
${}_{\pi}A_{r_{\pi}}(x)={}_{\sigma}A_{r_{\sigma}}(x)$.

Since ${}_{\pi}A_{k}(x)={}_{\sigma}A_{k}(x)=0$ for $0<k<r_{\pi}$, finally we
have ${}_{\pi}A_{k}(x)={}_{\sigma}A_{k}(x)$ for $0\leqslant k\leqslant
r_{\pi}$, and Equation (3) implies ${}_{\pi}A_{k}(x)={}_{\sigma}A_{k}(x)$ for
$k\geqslant r_{\pi}+1$. ∎

###  3.2 Skew Dyck and Motzkin paths

Let us discuss the skew Dyck paths first. For a given pattern $\pi$, Condition
($R$) implies that for $k\geqslant r_{\pi}+1$ we have

$A_{k}(x)=x\cdot A_{k-1}(x)\cdot\left(\sum\limits_{i=0}^{k}A_{i}(x)+1\right)$

which is a particular case of Equation (3) for $r=r_{\pi}$, $p(x)=x$,
$q(x)=1$, $u=A_{r_{\pi}}(x)$, and $v=A_{0}(x)$. Then, we deduce the following.

######  Corollary 3.2.

$A(x)=\frac{uv{x}^{2}+{v}^{2}{x}^{2}-{x}^{2}u-xu-{x}^{2}+1-\sqrt{\Delta}}{2{x}^{2}\left(1+v+u\right)}$
(7)

with
$\Delta={u}^{2}{v}^{2}{x}^{4}+2\,u{v}^{3}{x}^{4}+{v}^{4}{x}^{4}+2\,{u}^{2}v{x}^{4}+6\,u{v}^{2}{x}^{4}+4\,{v}^{3}{x}^{4}-2\,{u}^{2}v{x}^{3}+{u}^{2}{x}^{4}-2\,u{v}^{2}{x}^{3}+6\,uv{x}^{4}+6\,{v}^{2}{x}^{4}-2\,{x}^{3}{u}^{2}-4\,uv{x}^{3}+2\,u{x}^{4}+4\,v{x}^{4}-3\,{u}^{2}{x}^{2}-6\,uv{x}^{2}-2\,u{x}^{3}-2\,{v}^{2}{x}^{2}+{x}^{4}-6\,{x}^{2}u-4\,v{x}^{2}-2\,xu-2\,{x}^{2}+1.$

The following table gives the first values of generating functions $A(x)$
obtained for all patterns of length at most two. Notice that none sequences
appear in [13].

Statistic $h_{\pi}$ | $a_{n},~{}1\leqslant n\leqslant 9$ | OEIS
---|---|---
$h$, $U$, $D$, $UU$ , $UD$ | 1, 3, 8, 23, 68, 211, 668, 2169, 7145 |
$L$, $DL$ | 1, 3, 9, 28, 91, 307, 1062, 3748, 13429 |
$DD$ | 1, 3, 9, 29, 96, 327, 1136, 4014, 14365 |
$DU$ | 1, 3, 9, 27, 82, 255, 813, 2655, 8847 |
$LD$ | 1, 3, 10, 35, 126, 463, 1728, 6529, 24916 |
$LL$ | 1, 3, 10, 35, 128, 485, 1890, 7531, 30545 |

In the context of skew Motzin paths we have

$A_{k}(x)=x^{2}\cdot A_{k-1}(x)\cdot\left(\sum\limits_{i=0}^{k}A_{i}(x)+x\cdot
A_{0}(x)+1\right)$

which is a particular case of Equation (3) for $r=r_{\pi}$, $p(x)=x^{2}$,
$q(x)=x\cdot A_{0}(x)+1$, $u=A_{r_{\pi}}(x)$, which means that $v=0$ when
$r_{\pi}=0$ and $v=A_{0}(x)$ otherwise. Then, the generating function $A(x)$
is the generating function for skew Dyck paths (see Equation (7)) applied on
the variable $x^{2}$ ($x$ is not replaced with $x^{2}$ in $u$ and $v$), and we
obtain the following results for patterns of length at most one. The sequences
do not appear in [13].

Statistic $h_{\pi}$ | $a_{n},~{}1\leqslant n\leqslant 9$ | OEIS
---|---|---
$h$, $U$ | 1, 2, 4, 9, 20, 45, 101, 229, 524, 1211, 2820 |
$D$ | 1, 2, 4, 10, 23, 55, 131, 318, 774, 1899, 4678 |
$F$ | 1, 2, 5, 11, 27, 64, 157, 383, 946, 2347, 5854 |
$L$ | 1, 2, 5, 12, 30, 76, 196, 513, 1359, 3639, 9831 |

## 4 Conclusion and research directions

Except Dyck and Motzkin cases, where we obtain two sequences appearing in [13]
for the pattern $U$, all the others have never been studied in the literature.
So, this work provides a new catalog of sequences which is a possibly fertile
ground in number theory, and more precisely in the analyse of their modular
congruences (see [5] for instance). Another research direction could be the
investigation of the distribution of a given pattern in the set
$\mathcal{A}^{h_{\pi},\geqslant}$. For instance, if $\pi=UU$ in the context of
Dyck paths, then the paths in $\mathcal{A}^{h_{\pi},\geqslant}$ avoiding the
pattern $UDU$ are enumerated by the generalized Catalan numbers (see A004148
in [13]), which also count peak-less Motzkin paths. It would be interesting to
find a one-to-one correspondence between these objects.

In this paper, we focus on the generating $A(x)$ of
$\mathcal{A}^{h_{\pi},\geqslant}$, but we do not deal with the generating
functions $A_{k}(x)$ for paths $P\in\mathcal{A}^{h_{\pi},\geqslant}$ such that
$h_{\pi}(P)=k$ since they can be easily obtained. Observing these g.f. for
small $k$, we have identified some of them that are already known in OEIS
[13]. For instance, the number of $n$-length Dyck paths
$P\in\mathcal{A}^{h_{UU},\geqslant}$ such that $h_{UU}(P)=2$ is the classical
number of Fibonacci minus one (see A000071 in [13]). Such a result suggests us
to look for new bijections with known classes counted by this sequence.

Finally, it would be interesting to extend this work to other classes of
objects counted by generating functions satisfying System (3).

## Acknowledgements

This work was partly supported by the project ANER ARTICO financed by
Bourgogne-Franche-Comté region.

## References

  * [1] J.-L. Baril, S. Kirgizov, and A. Petrossian, Dyck paths with a first return decomposition constrained by height, Discrete Math., 341 (2018), 1620–1628.
  * [2] J.-L. Baril, S. Kirgizov, and A. Petrossian, Motzkin paths with a restricted first return decomposition, Integers: Electronic Journal of Combinatorial Number Theory, 19 (2019), $\\#$A46.
  * [3] C. Brennan and S. Mavhungu, Peaks and valleys in Motzkin paths, Quaestiones Mathematicae, 33 (2010), 171–188.
  * [4] E. Deutsch, Dyck path enumeration, Discrete Math., 204 (1999), 167–202.
  * [5] E. Deutsch and B. Sagan, Congruences for Catalan and Motzkin numbers and related sequences, J. Number Theory, 117 (2006), 191–215.
  * [6] R. Flórez, L. Junes, and J. Ramírez, Enumerating several aspects of non- decreasing Dyck paths, Discrete Math., 342 (2019), 3079–3097.
  * [7] Q. L. Lu, Skew Motzkin paths, Acta Math. Sinica, 33 (2017), 657–667.
  * [8] T. Mansour, Counting peaks at height $k$ in a Dyck path, J. Integer of Sequences, 5 (2002), Article 02.1.1.
  * [9] T. Mansour, Statistics on Dyck paths, J. Integer Sequences, 9 (2006), Article 06.1.5.
  * [10] T. Mansour, Combinatorics of set partitions, CRC Press, 2012.
  * [11] T. Mansour, E. Deng, and R. Du, Dyck paths and restricted permutations, Discrete Applied Math., 154 (2006), 1593–1605.
  * [12] D. Merlini, R. Sprugnoli, and M. Verri, Some statistics on Dyck paths, J. Statis. Plann. Inference, 101 (2002), 211–227.
  * [13] N. Sloane, The on-line encyclopedia of integer sequences, Available electronically at http://oeis.org.