18 citations · 53 across the 13 of their papers we have counts for
21 papers
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…
Counting Phylogenetic Networks with Few Reticulation Vertices: Exact Enumeration and Corrections
Michael Fuchs, Bernhard Gittenberger, Marefatollah Mansouri
In previous work, we gave asymptotic counting results for the number of tree-child and normal networks with reticulation vertices and explicit exponential generating functions…
Compaction for two models of logarithmic-depth trees: Analysis and Experiments
Olivier Bodini, Antoine Genitrini, Bernhard Gittenberger +2
We are interested in the quantitative analysis of the compaction ratio for two classical families of trees: recursive trees and plane binary increasing trees. These families are ty…
Protection numbers in simply generated trees and Pólya trees
Bernhard Gittenberger, Zbigniew Gołębiewski, Isabella Larcher +1
We determine the limit of the expected value and the variance of the protection number of the root in simply generated trees, in Pólya trees, and in unlabelled non-plane binary tre…
Distribution of variables in lambda-terms with restrictions on De Bruijn indices and De Bruijn levels
Bernhard Gittenberger, Isabella Larcher
We investigate the number of variables in two special subclasses of lambda-terms that are restricted by a bound of the number of abstractions between a variable and its binding lam…
On the Number of Increasing Trees with Label Repetitions
Olivier Bodini, Antoine Genitrini, Bernhard Gittenberger +1
We study the asymptotic number of certain monotonically labeled increasing trees arising from a generalized evolution process. The main difference between the presented model and t…
Threshold functions for small subgraphs in simple graphs and multigraphs
Gwendal Collet, Élie de Panafieu, Danièle Gardy +2
We revisit the problem of counting the number of copies of a fixed graph in a random graph or multigraph, for various models of random (multi)graphs. For our proofs we introduce th…
Counting Phylogenetic Networks with Few Reticulation Vertices: Tree-Child and Normal Networks
Michael Fuchs, Bernhard Gittenberger, Marefatollah Mansouri
In recent decades, phylogenetic networks have become a standard tool in modeling evolutionary processes. Nevertheless, basic combinatorial questions about them are still largely op…
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 shape of random Pólya structures
Bernhard Gittenberger, Emma Yu Jin, Michael Wallner
Panagiotou and Stufler recently proved an important fact on their way to establish the scaling limits of random Pólya trees: a uniform random Pólya tree of size consists of a c…
Threshold functions for small subgraphs: an analytic approach
Gwendal Collet, Élie de Panafieu, Danièle Gardy +2
We revisit the problem of counting the number of copies of a fixed graph in a random graph or multigraph, including the case of constrained degrees. Our approach relies heavily on…
Asymptotic Enumeration of Compacted Binary Trees of Bounded Right Height
Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers +1
A compacted binary tree is a graph created from a binary tree such that repeatedly occurring subtrees in the original tree are represented by pointers to existing ones, and hence e…
A note on the scaling limits of random Pólya trees
Bernhard Gittenberger, Emma Yu Jin, Michael Wallner
Panagiotou and Stufler (arXiv:1502.07180v2) recently proved one important fact on their way to establish the scaling limits of random Pólya trees: a uniform random Pólya tree of si…
2-Xor revisited: satisfiability and probabilities of functions
Élie de Panafieu, Danièle Gardy, Bernhard Gittenberger +1
The problem 2-Xor-Sat asks for the probability that a random expression, built as a conjunction of clauses , is satisfiable. We revisit this classical problem by giving…
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…
The relation between tree size complexity and probability for Boolean functions generated by uniform random trees
Antoine Genitrini, Bernhard Gittenberger, Veronika Kraus +1
We consider a probability distribution on the set of Boolean functions in n variables which is induced by random Boolean expressions. Such an expression is a random rooted plane tr…
Associative and commutative tree representations for Boolean functions
Antoine Genitrini, Bernhard Gittenberger, Veronika Kraus +1
Since the 90's, several authors have studied a probability distribution on the set of Boolean functions on variables induced by some probability distributions on formulas built…
Enumeration of generalized lambda-terms
Olivier Bodini, Danièle Gardy, Bernhard Gittenberger +1
We investigate the asymptotic number of elements of size in a particular class of closed lambda-terms (so-called -terms) which are related to axiom systems of combinato…
The degree profile of Pólya trees
Bernhard Gittenberger, Veronika Kraus
We investigate the profile of random Pólya trees of size when only nodes of degree are counted in each level. It is shown that, as in the case where all nodes contribute to…
The Shape of Unlabeled Rooted Random Trees
Michael Drmota, Bernhard Gittenberger
We consider the number of nodes in the levels of unlabelled rooted random trees and show that the stochastic process given by the properly scaled level sizes weakly converges to th…