4 papers · 1 filter
Counting embeddings of rooted trees into families of rooted trees
Bernhard Gittenberger, Zbigniew Gołębiewski, Isabella Larcher +1
The number of embeddings of a partially ordered set in a partially ordered set is the number of subposets of isomorphic to . If both, and , have only one uniq…
Enumerating Lambda Terms by Weighted Length of Their De Bruijn Representation
Olivier Bodini, Bernhard Gittenberger, Zbigniew Gołębiewski
John Tromp introduced the so-called 'binary lambda calculus' as a way to encode lambda terms in terms of 0-1-strings using the de Bruijn representation along with a weighting schem…
On the number of unary-binary tree-like structures with restrictions on the unary height
Olivier Bodini, Danièle Gardy, Bernhard Gittenberger +1
We consider various classes of Motzkin trees as well as lambda-terms for which we derive asymptotic enumeration results. These classes are defined through various restrictions conc…
On the number of lambda terms with prescribed size of their De Bruijn representation
Bernhard Gittenberger, Zbigniew Gołębiewski
John Tromp introduced the so-called 'binary lambda calculus' as a way to encode lambda terms in terms of binary words. Later, Grygiel and Lescanne conjectured that the number of bi…