On the Number of Unary-Binary Tree-Like Structures with Restrictions on the Unary Height

Bodini, Olivier; Gardy, Daniele; Gittenberger, Bernhard; Golebiewski, Zbigniew

doi:10.1007/s00026-018-0371-7

Record link:

https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:3-5026
http://hdl.handle.net/20.500.12708/98

Title:

On the Number of Unary-Binary Tree-Like Structures with Restrictions on the Unary Height

Citation:

Bodini, O., Gardy, D., Gittenberger, B., & Golebiewski, Z. (2018). On the Number of Unary-Binary Tree-Like Structures with Restrictions on the Unary Height. Annals of Combinatorics, 22, 45–91. https://doi.org/10.1007/s00026-018-0371-7

Publisher DOI:

10.1007/s00026-018-0371-7

CatalogPlus:

AC15321018

Publication Type:

Article - Original Research Article

Language:

English

Authors:

Bodini, Olivier
Gardy, Daniele
Gittenberger, Bernhard
Golebiewski, Zbigniew

Organisational Unit:

E104 - Institut für Diskrete Mathematik und Geometrie

Journal:

Annals of Combinatorics

ISSN:

0218-0006

Date (published):

2018

Number of Pages:

Publisher:

Birkhäuser

Peer reviewed:

Yes

Keywords:

asymptotic enumeration; generating functions; lambda-terms; trees; directed acyclic graphs; nested square-roots; singularity analysis

Abstract:

We investigate various classes of Motzkin trees as well as lambda-terms for which we derive asymptotic enumeration results. These classes are defined through various restrictions concerning the unary nodes or abstractions, respectively: we either bound their number or the allowed levels of nesting. The enumeration is done by means of a generating function approach and singularity analysis. The generating functions are composed of nested square roots and exhibit unexpected phenomena in some of the cases. Furthermore, we present some observations obtained from generating such terms randomly and explain why usually powerful tools for random generation, such as Boltzmann samplers, face serious difficulties in generating lambda-terms.

License:

CC BY 4.0