On the enumeration and generation of generalized Dyck words

AbstractWe provide a new algebraic grammar for generalized Dyck languages as introduced by Labelle and Yeh (Discrete Math. 82 (1990) 1–6). The study of these languages leads to the particular sublanguages of words without proper factors belonging to the studied language. A random generation scheme is shown for generalized Dyck languages, which leads to some asymptotic results. In the two-letter case, for which the words correspond to ‘rational slope Dyck paths’, more exact and asymptotic enumerative results are obtained, including the asymptotic average area to integer or 32 slope Dyck paths