6 papers
Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs
Wojciech Gabryelski, Zbigniew Gołȩbiewski, Martin Pépin
We propose two efficient algorithms for generating uniform random directed acyclic graphs, including an asymptotically optimal exact-size sampler that performs $\frac{n^2}{2} + o(n…
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 spreading rumor in heterogeneous systems
Jacek Cichoń, Zbigniew Goł\eobbiewski, Marcin Kardas +2
In this paper we consider a model of spreading information in heterogeneous systems wherein we have two kinds of objects. Some of them are active and others are passive. Active obj…
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…