Michael Wallner – Academic Profile

Publications

2026

A Combinatorial Framework for the Pons-Batle Identity: Young Tableaux, Lattice Paths, and Limit Laws

Hexuan Liu, Guan-Ru Yu, Michael Wallner

Accepted AofA 2026, 2026

Bijections between Pons-Batle words and Young tableaux with walls and holes; Beta and Uniform limit laws.

Tree-child networks model reticulate evolutionary processes. This paper studies bicombining tree-child networks through combinatorial and analytic approaches, using Young tableaux with walls and holes and constructing bijections to Pons-Batle words. We derive algebraic generating functions with differential operators for enumeration formulas and reveal probabilistic structures with Beta and Uniform limit distributions.
Bivariate asymptotics via random walks: application to large genus maps

Andrew Elvey Price, Wenjie Fang, Baptiste Louf, Michael Wallner

Preprint

arXiv zbMATH

Bivariate asymptotics for unicellular maps as size and genus grow simultaneously, via linear recurrences and complex analysis.

We obtain bivariate asymptotics for the number of (unicellular) combinatorial maps (a model of discrete surfaces) as both the size and the genus grow. This work is related to two research topics that have been very active recently: multivariate asymptotics and large genus geometry. Our method consists of studying a linear recurrence for these numbers, and can be applied to many other linear recurrences. In particular, we include a general theorem that yields asymptotics for such recurrences, provided that some assumptions are satisfied.
- ↳
  
  Bivariate asymptotics via random walks: application to large genus maps (Extended abstract)
  
  37th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2025), 2025
  
  www arXiv
  
  Extended Abstract. Bivariate asymptotics for unicellular maps as size and genus grow simultaneously, via linear recurrences and complex analysis.
  
  We obtain bivariate asymptotics for the number of (unicellular) combinatorial maps (a model of discrete surfaces) as both the size and the genus grow. This work is related to two research topics that have been very active recently: multivariate asymptotics and large genus geometry. Our method consists in studying a linear recurrence for these numbers, and in fact it can be applied to many other linear recurrences. We discuss briefly the generality of our method and future research directions.
The decompressed tree size of k-ary chains

Michael Wallner

Accepted Annals of Combinatorics, 2026

www arXiv zbMATH

Expected decompressed tree size of a $k$-ary chain of size $n$ contains a stretched exponential $e^{c\,\sqrt{n}}$.

A chain is a directed acyclic graph (DAG) with one source and one sink, where the children are ordered and the spanning tree is a path. Such DAGs arise in the compression of trees and are therefore uniquely associated with a tree. The tree size of a DAG is therefore the size of the associated tree. For fixed finite out-degrees, we compute the expected decompressed tree size of a chain of size n chosen uniformly at random, and show that it contains a stretched exponential term of the form $e^{c \, \sqrt{n}}$. The key idea is to use a special generating function that generalizes exponential generating functions and allows the decompressed trees to be constructed symbolically.
- ↳
  
  The decompressed tree size of k-ary chains (Extended abstract)
  
  European Conference on Combinatorics, Graph Theory and Applications (Eurocomb'25), Budapest, 2025
  
  www
  
  Extended abstract. Stretched exponential $e^{c\sqrt{n}}$ in the expected decompressed tree size of a $k$-ary chain.
  
  A chain is a directed acyclic graph (DAG) with one source and one sink, where the children are ordered and the spanning tree is a path. Such DAGs arise in the compression of trees and are therefore uniquely associated with a tree. The tree size of a DAG is therefore the size of the associated tree. For fixed finite out-degrees, we compute the expected decompressed tree size of a chain of size n chosen uniformly at random, and show that it contains a stretched exponential term of the form $e^{c \, \sqrt{n}}$. The key idea is to use a special generating function that generalizes exponential generating functions and allows the decompressed trees to be constructed symbolically.

2024

Asymptotics of relaxed k-ary trees

Manosij Ghosh Dastidar, Michael Wallner

35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024), 2024

www arXiv Maple zbMATH

Stretched exponential $e^{c n^{1/3}}$ in the asymptotics of relaxed $k$-ary trees, for all finite arities; recurrences for compacted trees and minimal DFA.

A relaxed $k$-ary tree is an ordered directed acyclic graph with a unique source and sink in which every node has out-degree $k$. These objects arise in the compression of trees in which some repeated subtrees are factored and repeated appearances are replaced by pointers. We prove an asymptotic theta-result for the number of relaxed $k$-ary tree with $n$ nodes for $n \to \infty$. This generalizes the previously proved binary case to arbitrary finite arity, and shows that the seldom observed phenomenon of a stretched exponential term $e^{c n^{1/3}}$ appears in all these cases. We also derive the recurrences for compacted $k$-ary trees in which all subtrees are unique and minimal deterministic finite automata accepting a finite language over a finite alphabet.
Composition schemes: q-enumerations and phase transitions in Gibbs models

Cyril Banderier, Markus Kuba, Stephan Wagner, Michael Wallner

35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024), 2024

www arXiv zbMATH

Phase transitions in $q$-enumeration via composition schemes: Mittag-Leffler, Gaussian, and Boltzmann limit laws depending on the regime.

Composition schemes are ubiquitous in combinatorics, statistical mechanics and probability theory. We give a unifying explanation to various phenomena observed in the combinatorial and statistical physics literature in the context of $q$-enumeration (this is a model where objects with a parameter of value $k$ have a Gibbs measure/Boltzmann weight $q^k$). For structures enumerated by a composition scheme, we prove a phase transition for any parameter having such a Gibbs measure: for a critical value $q=q_c$, the limit law of the parameter is a two-parameter Mittag-Leffler distribution, while it is Gaussian in the supercritical regime ($q>q_c$), and it is a Boltzmann distribution in the subcritical regime ( $0 < q < q_c$). We apply our results to fundamental statistics of lattice paths and quarter-plane walks. We also explain previously observed limit laws for pattern-restricted permutations, and a phenomenon uncovered by Krattenthaler for the wall contacts in watermelons.
A bijection between stacked directed polyominoes and Motzkin paths with alternative catastrophes

Florian Schager, Michael Wallner

GASCom 2024, 2024

www arXiv zbMATH

Novel bijection between stacked directed polyominoes and Motzkin paths with alternative catastrophes.

We present a novel bijection between stacked directed polyominoes and Motzkin paths with alternative catastrophes. Further, we show how this new connection can be used in order to obtain a better understanding of certain parameters of stacked directed animals.
Bijections and congruences involving lattice paths and integer compositions

Manosij Ghosh Dastidar, Michael Wallner

Submitted

arXiv zbMATH

New bijections explain the counting formula $4^{n-1}$ for Dyck paths and integer compositions; connections to mock theta functions and Fibonacci numbers.

We prove new bijections between different variants of Dyck paths and integer compositions, which give combinatorial explanations of their simple counting formula $4^{n−1}$. These give relations between different statistics, such as the number of crossings of the x-axis in classes of Dyck bridges or the distribution of peaks in classes of Dyck paths, and furthermore relate them with k- and g-compositions. These allow us to find and prove congruence results for Dyck paths and parity results for compositions. Our investigation uncovers unexpected connections to mock theta functions, Hardinian arrays, little Schröder paths, Fibonacci numbers, and irreducible pairs of compositions, offering new insights into the structures of paths, partitions and compositions.
- ↳
  
  Bijections between variants of Dyck paths and integer compositions (Extended abstract)
  
  GASCom 2024, 2024
  
  www arXiv zbMATH
  
  Extended abstract. Bijective results between Dyck path variants and integer compositions enumerated by $4^{n-1}$; congruence relationships.
  
  We give bijective results between several variants of lattice paths and integer compositions all enumerated by the seemingly innocuous formula $4^{n-1}$. These associations lead us to make more connections between the two constructs such as congruence results.
Enumerative and Distributional Results for d-combining Tree-Child Networks

Yu-Sheng Chang, Michael Fuchs, Hexuan Liu, Guan-Ru Yu, Michael Wallner

Advances in Applied Mathematics, 157, 102704, 2024

www arXiv Maple zbMATH

Exact formulas and phase transitions (normal, Bessel, Poisson, degenerate) for shape parameters of $d$-combining tree-child networks.

Tree-child networks are one of the most prominent network classes for modeling evolutionary processes which contain reticulation events. Several recent studies have addressed counting questions for {\it bicombining tree-child networks} in which every reticulation node has exactly two parents. We extend these studies to {\it $d$-combining tree-child networks} where every reticulation node has now $d\geq 2$ parents, and we study one-component as well as general tree-child networks. Moreover, we also give results on the distributional behavior of shape parameters (e.g., number of reticulation nodes, Sackin index) of a network which is drawn uniformly at random from the set of all tree-child networks with the same number of leaves. We show phase transitions depending on $d$, leading to normal, Bessel, Poisson, and degenerate distributions. Some of our results are new even in the bicombining case.
- ↳
  
  Enumeration of d-combining Tree-Child Networks (Extended abstract)
  
  33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022), 2022
  
  www arXiv Maple zbMATH
  
  Extended abstract. Counting and distributional results for $d$-combining tree-child networks with $d\geq 2$ parents per reticulation node.
  
  Tree-child networks are one of the most prominent network classes for modeling evolutionary processes which contain reticulation events. Several recent studies have addressed counting questions for bicombining tree-child networks which are tree-child networks with every reticulation node having exactly two parents. In this paper, we extend these studies to $d$-combining tree-child networks where every reticulation node has now $d\geq 2$ parents. Moreover, we also give results and conjectures on the distributional behavior of the number of reticulation nodes of a network which is drawn uniformly at random from the set of all tree-child networks with the same number of leaves.
Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions

Cyril Banderier, Markus Kuba, Michael Wallner

Annals of Applied Probability, 34(5), pp. 4635–4693, 2024

www arXiv zbMATH

Three-parameter Mittag-Leffler distribution as a universal law; double phase transitions involving Boltzmann and mixed Poisson distributions.

Multitudinous combinatorial structures are counted by generating functions satisfying a composition scheme $$F(z)=G(H(z)).$$ The corresponding asymptotic analysis becomes challenging when this scheme is critical (i.e., $G$ and $H$ are simultaneously singular). The singular exponents appearing in the Puiseux expansions of G and H then dictate the asymptotics. In this work, we first complement results of Flajolet et al. for a full family of singular exponents of $G$ and $H$. We identify the arising limit laws (for the number of $H$-components in $F$) and prove moment convergence. Then, motivated by many examples (random mappings, planar maps, directed lattice paths), we consider a natural extension of this scheme, namely $$F(z)=G(H(z))M(z).$$ We discuss the number of $H$-components of a given size in $F$; this leads to a nice world of limit laws involving products of beta and Mittag-Leffler distributions. We also obtain continuous to discrete phase transitions involving mixed Poisson distributions, giving an unified explanation of the associated thresholds. We end with extensions of the critical composition scheme to a cycle scheme and to the multivariate case, leading again to product distributions. Applications are presented for random walks, trees (supertrees of trees, increasingly labelled trees, preferential attachment trees), triangular Pólya urns, and the Chinese restaurant process.

2023

Dyck paths and inversion tables

Michael Wallner

Permutation Patterns 2023, pp. 142–144, 2023

www

Inversion tables generalized to boxed Dyck paths; bijections with increasing Cayley trees, binary trees, and relaxed binary trees.

We generalize inversion tables, which are in bijection with permutations, to boxed Dyck paths, where the number of markers in each row depends on a path that may differ from the staircase path. We demonstrate that subclasses of this family correspond to various combinatorial objects, including increasing Cayley trees, increasing binary trees, and relaxed binary trees. Moreover, we discuss the relationship between the path and the markers and enumerate some of the aforementioned subclasses.
The binary digits of n+t

Lukas Spiegelhofer, Michael Wallner

Annali della Scuola Normale Superiore di Pisa, Classe di Scienze, 24(1), pp. 1–31, 2023

www arXiv zbMATH

Cusick's conjecture proved for $t$ with sufficiently many blocks of 1s; Gaussian behavior of $s(n+t)-s(n)$.

The binary sum-of-digits function $s$ counts the number of $\mathtt 1$s in the base-$2$ expansion of a nonnegative integer. T. W. Cusick defined the asymptotic density $$c_t=\lim_{N\rightarrow \infty} \frac 1N \#\{0\leq n \lt N:s(n+t)\geq s(n)\}$$ for integers $t\geq 0$ and conjectured that $c_t>1/2$ for all $t$. We prove that indeed $c_t>1/2$ if the binary expansion of $t$ contains at least $K$ blocks of contiguous $1$s, where $K$ is an absolute, effective constant.
Walks avoiding a quadrant and the reflection principle

Mireille Bousquet-Mélou, Michael Wallner

European Journal of Combinatorics, 103803, 2023

www arXiv Maple Slides zbMATH

Generating function for king walks avoiding the negative quadrant: D-finite series plus algebraic component; algebraicity for Weyl step sets.

We continue the enumeration of plane lattice walks with small steps avoiding the negative quadrant, initiated by the first author in 2016. We solve in detail a new case, namely the king model where all eight nearest neighbour steps are allowed. The associated generating function is proved to be the sum of a simple, explicit D-finite series (related to the number of walks confined to the first quadrant), and an algebraic one. This was already the case for the two models solved by the first author in 2016. The principle of the approach is also the same, but challenging theoretical and computational difficulties arise as we now handle algebraic series of larger degree. We expect a similar algebraicity phenomenon to hold for the seven Weyl step sets, which are those for which walks confined to the first quadrant can be counted using the reflection principle. With this paper, this is now proved for three of them. For the remaining four, we predict the D-finite part of the solution, and in three of the four cases, give evidence for the algebraicity of the remaining part.
- ↳
  
  More Models of Walks Avoiding a Quadrant (Extended abstract)
  
  31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), 2020
  
  www arXiv Video zbMATH
  
  Extended abstract. King walks avoiding the negative quadrant: D-finite plus algebraic generating function decomposition.
  
  We continue the enumeration of plane lattice paths avoiding the negative quadrant initiated by the first author in [Bousquet-Mélou 2016]. We solve in detail a new case, where all 8 nearest neighbour steps are allowed. As in the two cases solved in [Bousquet-Mélou 2016], the associated generating function is proved to differ from a simple, explicit D-finite series (related to the enumeration of walks confined to the first quadrant) by an algebraic one. The principle of the approach is the same as in [Bousquet-Mélou 2016], but challenging theoretical and computational difficulties arise as we now handle algebraic series of larger degree. We also explain why we expect the observed algebraicity phenomenon to persist for 4 more models, for which the quadrant problem is solvable using the reflection principle.
Combinatorics of nondeterministic walks

Élie de Panafieu, Michael Wallner

Submitted

arXiv Maple Git Slides

Nondeterministic bridges, excursions, and meanders with Dyck/Motzkin steps are algebraic; reachable endpoint sets; Python and Maple packages.

This paper introduces nondeterministic walks, a new variant of one-dimensional discrete walks. The main difference to classical walks is that its nondeterministic steps consist of sets of steps from a predefined set such that all possible extensions are explored in parallel. We discuss in detail the most natural nondeterministic step sets (Dyck and Motzkin step sets), and show that several nondeterministic classes of lattice paths, such as nondeterministic bridges, excursions, and meanders are algebraic. The key concept is the generalization of the ending point of a walk to its reachable points, i.e., a set of ending points. We extend our results to general step sets: We show that nondeterministic bridges and several subclasses of nondeterministic meanders are always algebraic. We conjecture the same is true for nondeterministic excursions, and we present python and Maple packages to support our conjecture. This research is motivated by the study of networks involving encapsulation and decapsulation of protocols. Our results are obtained using generating functions, analytic combinatorics, and additive combinatorics.
- ↳
  
  De la probabilité de creuser un tunnel (French abstract)
  
  AlgoTel 2019, Saint Laurent de la Cabrerisse, 2019
  
  HAL
  
  Feasibility probability of protocol paths with nested encapsulations/decapsulations computed via Dyck and Motzkin path generating functions (French-language abstract).
  
  Un tunnel est une portion d'un chemin où un protocole de communication est encapsulé dans un autre. Les tunnels sont de plus en plus présents dans les réseaux. Ils sont utilisés pour la sécurité, l'interopérabilité, les réseaux virtuels, etc. Un chemin contenant un tunnel doit ^etre faisable, c'est-à-dire qu'il doit respecter l'ordre des encapsulations et des désencapsulations, parfois imbriquées. Les algorithmes de calcul de chemins avec prise en compte de tunnels ne sont pas les m^emes que dans un réseau classique. Afin de tester ces algorithmes, il serait utile de disposer d'un générateur de topologies aléatoires avec tunnels. Ce générateur devra produire des topologies ayant certaines caractéristiques (par exemple, que la probabilité qu'un chemin soit faisable soit un paramètre p quelconque). Il se trouve que ce problème est lié aux chemins de Dyck et de Motzkin en combinatoire. En effet, une encapsulation peut ^etre vue comme un pas montant et une désencapsulation peut ^etre vue comme un pas descendant. La question qui se pose est donc de savoir quelle est la probabilité qu'un chemin de Dyck ou de Motzkin ait certaines propriétés. Dans ce travail, en utilisant des outils de combinatoire analytique, nous donnons la probabilité qu'un chemin soit faisable en fonction de la distribution des encapsulations et des désencapsulations sur les sommets.
- ↳
  
  Combinatorics of nondeterministic walks of the Dyck and Motzkin type (Extended abstract)
  
  Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2019), San Diego, 2019
  
  www arXiv
  
  Generating functions for nondeterministic Dyck/Motzkin walks (bridges, meanders, excursions); motivated by protocol encapsulation.
  
  This paper introduces nondeterministic walks, a new variant of one-dimensional discrete walks. At each step, a nondeterministic walk draws a random set of steps from a predefined set of sets and explores all possible extensions in parallel. We introduce our new model on Dyck steps with the nondeterministic step set $\{ \{-1\}, \{1\}, \{-1,1\}\}$ and Motzkin steps with the nondeterministic step set $\{\{-1\}, \{0\}, \{1\}, \{-1,0\}, \{-1,1\}, \{0,1\}, \{-1,0,1\}\}$. For general lists of step sets and a given length, we express the generating function of nondeterministic walks where at least one of the walks explored in parallel is a bridge (ends at the origin). In the particular cases of Dyck and Motzkin steps, we also compute the asymptotic probability that at least one of those parallel walks is a meander (stays nonnegative) or an excursion (stays nonnegative and ends at the origin). This research is motivated by the study of networks involving encapsulations and decapsulations of protocols. Our results are obtained using generating functions and analytic combinatorics.

2022

On the critical exponents of generalized ballot sequences in three dimensions and large tandem walks

Michael Wallner

Aequationes Mathematicae, 96, pp. 815–826, 2022

www arXiv zbMATH

Ballot walk models are not $D$-finite; tandem walks generalized bijectively to ballot walks in three dimensions.

We answer some questions on the asymptotics of ballot walks raised in [Personal Journal Shalosh B Ekhad and Doron Zeilberger, Apr 5, 2021; see also arXiv:2104.01731] and prove that these models are not D-finite. This short note demonstrates how the powerful tools developed in the last decades on lattice paths in convex cones help us to answer some challenging problems that were out of reach for a long time. On the way we generalize tandem walks to the family of large tandem walks whose steps are of arbitrary length and map them bijectively to a generalization of ballot walks in three dimensions.

2021

Young tableaux with periodic walls: counting with the density method

Cyril Banderier, Michael Wallner

33rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2021), 2021

www zbMATH

Generalized Young tableaux with periodic walls (Jenga tableaux): algebraic, hypergeometric, $D$-finite, and differentially-algebraic generating functions.

We consider a generalization of Young tableaux in which we allow some consecutive pairs of cells with decreasing labels, conveniently visualized by a "wall" between the corresponding cells. Some shapes can be enumerated by variants of hook-length type formulas. We focus on families of tableaux (like the so-called "Jenga tableaux") having some periodic shapes, for which the generating functions are harder to obtain. We get some interesting new classes of recurrences, and a surprisingly rich zoo of generating functions (algebraic, hypergeometric, D-finite, differentially-algebraic). Some patterns lead to nice bijections with trees, lattice paths, or permutations. Our approach relies on the density method, a powerful way to perform both random generation and enumeration of linear extensions of posets.
Compacted binary trees admit a stretched exponential

Andrew Elvey Price, Wenjie Fang, Michael Wallner

Journal of Combinatorial Theory, Series A, 177, 105306, 2021

www arXiv Maple Slides

Compacted binary trees of size $n$ grow like $\Theta\!\left(n!\cdot 4^n\cdot e^{3a_1 n^{1/3}}\cdot n^{3/4}\right)$; quadratic-complexity algorithm via two-parameter recurrence.

A compacted binary tree is a directed acyclic graph encoding a binary tree in which common subtrees are factored and shared, such that they are represented only once. We show that the number of compacted binary trees of size n grows asymptotically like $$\Theta \left( n! \, 4^n e^{3 a_1 n^{1/3}} n^{3/4} \right),$$ where $a_1 \approx 2.338$ is the largest root of the Airy function. Our method involves a new two parameter recurrence which yields an algorithm of quadratic arithmetic complexity. We use empirical methods to estimate the values of all terms defined by the recurrence, then we prove by induction that these estimates are sufficiently accurate for large n to determine the asymptotic form. Our results also lead to new bounds on the number of minimal finite automata recognizing a finite language on a binary alphabet. As a consequence, these also exhibit a stretched exponential.

2020

Latticepathology and Symmetric Functions

Cyril Banderier, Marie-Louise Lackner, Michael Wallner

31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), 2020

www Poster

Prime walks as natural structures for excursion decompositions; bivariate Spitzer/Wiener-Hopf formulas for lattice paths.

We revisit and extend a list of formulas based on lattice path surgery: cut-and-paste methods, factorizations, the kernel method, etc. For this purpose, we focus on the natural model of directed lattice paths (also called generalized Dyck paths). We introduce the notion of prime walks, which appear to be the key structure to get natural decompositions of excursions, meanders, bridges, directly leading to the associated context-free grammars. This allows us to give bijective proofs of bivariate versions of Spitzer/Sparre Andersen/Wiener--Hopf formulas, paving the way for many joint distribution studies. We also show that each of the fundamental families of symmetric polynomials correspond to a lattice path generating function, and that these symmetric polynomials are accordingly needed to express the asymptotic enumeration of these paths and some parameters of limit laws. En passant, we give two other small results which have their own interest for folklore conjectures of lattice paths (non-analyticity of the small roots in the kernel method, and universal positivity of the variability condition occurring in many Gaussian limit law schemes).
Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language

Andrew Elvey Price, Wenjie Fang, Michael Wallner

31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), 2020

www Maple

Minimal DFAs over a binary alphabet grow as $\Theta\!\left(n!\cdot 4^n\cdot e^{3a_1 n^{1/3}}\cdot n^{7/8}\right)$ where $a_1$ is the largest Airy root.

We show that the number of minimal discrete finite automata with n transient states recognizing a finite binary language grows asymptotically for n to infinity like $$\Theta \left( n! \, 4^n e^{3 a_1 n^{1/3}} n^{7/8} \right),$$ where $a_1 \approx 2.338$ is the largest root of the Airy function. For this purpose, we use a new asymptotic enumeration method proposed by the same authors in a recent preprint (2019). We first derive a new two parameter recurrence relation for the number of such automata up to a given size. Using this result, we prove by induction asymptotically tight bounds that are sufficiently accurate for large n to determine the asymptotic form using adapted Newton polygons.
Counting and sampling gene family evolutionary histories in the duplication-loss and duplication-loss-transfer models

Cedric Chauve, Yann Ponty, Michael Wallner

Journal of Mathematical Biology, 80(5), pp. 1353–1388, 2020

www arXiv

Formal grammars for gene family histories in the DLT-model; efficient counting and uniform random generation; horizontal transfer dramatically increases the number of histories.

Given a set of species whose evolution is represented by a species tree, a gene family is a group of genes having evolved from a single ancestral gene. A gene family evolves along the branches of a species tree through various mechanisms, including - but not limited to - speciation (S), gene duplication (D), gene loss (L), horizontal gene transfer (T). The reconstruction of a gene tree representing the evolution of a gene family constrained by a species tree is an important problem in phylogenomics. However, unlike in the multispecies coalescent evolutionary model that considers only speciation and incomplete lineage sorting events, very little is known about the search space for gene family histories accounting for gene duplication, gene loss and horizontal gene transfer (the DLT-model). In this work, we introduce the notion of evolutionary histories defined as a binary ordered rooted tree describing the evolution of a gene family, constrained by a species tree in the DLT-model. We provide formal grammars describing the set of all evolutionary histories that are compatible with a given species tree, whether it is ranked or unranked. These grammars allow us, using either analytic combinatorics or dynamic programming, to efficiently compute the number of histories of a given size, and also to generate random histories of a given size under the uniform distribution. We apply these tools to obtain exact asymptotics for the number of gene family histories for two species trees, the rooted caterpillar and the complete binary tree, as well as estimates of the range of the exponential growth factor of the number of histories for random species trees of size up to 25. Our results show that including horizontal gene transfer induce a dramatic increase of the number of evolutionary histories. We also show that, within ranked species trees, the number of evolutionary histories in the DLT-model is almost independent of the species tree topology. These results establish firm foundations for the development of ensemble methods for the prediction of reconciliations.
Periodic Pólya Urns, the Density Method, and Asymptotics of Young Tableaux

Cyril Banderier, Philippe Marchal, Michael Wallner

Annals of Probability, 48(4), pp. 1921–1965, 2020

www arXiv

Periodic Pólya urns have asymptotic fluctuations described by products of generalized gamma distributions; application to triangular Young tableaux.

Pólya urns are urns where at each unit of time a ball is drawn and replaced with some other balls according to its colour. We introduce a more general model: the replacement rule depends on the colour of the drawn ball and the value of the time (mod p). We extend the work of Flajolet et al. on Pólya urns: the generating function encoding the evolution of the urn is studied by methods of analytic combinatorics. We show that the initial differential equations lead to ordinary linear differential equations which are related to hypergeometric functions (giving the exact state of the urns at time n). When the time goes to infinity, we prove that these periodic Pólya urns have asymptotic fluctuations which are described by a product of generalized gamma distributions. With the additional help of what we call the density method (a method which offers access to enumeration and random generation of poset structures), we prove that the law of the south-east corner of a triangular Young tableau follows asymptotically a product of generalized gamma distributions. This allows us to tackle some questions related to the continuous limit of large random Young tableaux and links with random surfaces.
- ↳
  
  Periodic Pólya Urns and an Application to Young Tableaux (Extended abstract)
  
  29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018), Uppsala, 2018
  
  www arXiv
  
  Extended abstract. Periodic Pólya urns with time-modular replacement; $D$-finite moment generating functions; generalized Gamma distributions.
  
  Pólya urns are urns where at each unit of time a ball is drawn and is replaced with some other balls according to its colour. We introduce a more general model: The replacement rule depends on the colour of the drawn ball and the value of the time mod p. We discuss some intriguing properties of the differential operators associated to the generating functions encoding the evolution of these urns. The initial non-linear partial differential equation indeed leads to linear differential equations and we prove that the moment generating functions are D-finite. For a subclass, we exhibit a closed form for the corresponding generating functions (giving the exact state of the urns at time n). When the time goes to infinity, we show that these periodic Pólya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions. En passant, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux: This approach allows us to prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions.
Asymptotic Enumeration of Compacted Binary Trees of Bounded Right Height

Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers, Michael Wallner

Journal of Combinatorial Theory, Series A, 172, Article 105177, 2020

www arXiv

Asymptotic counting of compacted trees of bounded right height $k$: growth rates $(4\cos(\pi/(k+3))^2)^n$ with polynomial corrections.

A compacted 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 every subtree is unique. Such representations form a special class of directed acyclic graphs. We are interested in the asymptotic number of compacted trees of given size, where the size of a compacted tree is given by the number of its internal nodes. Due to its superexponential growth this problem poses many difficulties. Therefore we restrict our investigations to compacted trees of bounded right height, which is the maximal number of edges going to the right on any path from the root to a leaf. We solve the asymptotic counting problem for this class as well as a closely related, further simplified class. For this purpose, we develop a calculus on exponential generating functions for compacted trees of bounded right height and for relaxed trees of bounded right height, which differ from compacted trees by dropping the above described uniqueness condition. This enables us to derive a recursively defined sequence of differential equations for the exponential generating functions. The coefficients can then be determined by performing a singularity analysis of the solutions of these differential equations. Our main results are the computation of the asymptotic numbers of relaxed ($r_{k,n}$) as well as compacted trees ($c_{k,n}$) of bounded right height at most $k$ and given size $n$, when the size tends to infinity: \begin{align*} r_{k,n} &\sim \gamma_k n!\left(4 \cos\left(\frac{\pi}{k+3}\right)^2\right)^{n} n^{-\frac{k}{2}} \\ c_{k,n} &\sim \kappa_k n! \left(4 \cos\left(\frac{\pi}{k+3}\right)^2\right)^{n} n^{- \frac{k}{2} - \frac{1}{k+3} - \left(\frac{1}{4} - \frac{1}{k+3}\right)\cos\left(\frac{\pi}{k+3} \right)^{-2}} \end{align*} Here $\gamma_k$ and $\kappa_k$ are nonzero, positive constants which are independent of $n$.
A half-normal distribution scheme for generating functions

Michael Wallner

European Journal of Combinatorics, 87, 103138, 2020

www arXiv

General theorem: bivariate generating functions under zero drift yield half-normal distributions; applications to returns to zero, height, sign changes.

We present a general theorem on the structure of bivariate generating functions which gives sufficient conditions such that the limiting probability distribution is a half-normal distribution. If $X$ is a normally distributed random variable with zero mean, then $|X|$ obeys a half-normal distribution. In the second part, we apply our result to prove three natural appearances in the domain of lattice paths: the number of returns to zero, the height, and the sign changes are under zero drift distributed according to a half-normal distribution. This extends known results to a general step set. Finally, our result also gives a new proof of Banach's matchbox problem.
- ↳
  
  A half-normal distribution scheme for generating functions and the unexpected behavior of Motzkin paths (Extended abstract)
  
  27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2016), Kraków, 2016
  
  www arXiv
  
  Extended abstract. Extension of the Drmota-Soria theorem: conditions on bivariate generating functions implying half-normal limit distributions.
  
  We present an extension of a theorem by Michael Drmota and Michele Soria [Images and Preimages in Random Mappings, 1997] that can be used to identify the limiting distribution for a class of combinatorial schemata. This is achieved by determining analytical and algebraic properties of the associated bivariate generating function. We give sufficient conditions implying a half-normal limiting distribution, extending the known conditions leading to either a Rayleigh, a Gaussian, or a convolution of the last two distributions. We conclude with three natural appearances of such a limiting distribution in the domain of Motzkin paths.

2019

The Tu-Deng conjecture holds almost surely

Lukas Spiegelhofer, Michael Wallner

The Electronic Journal of Combinatorics, 26(1), Paper 1.28, 28 pp., 2019

www arXiv Maple

The Tu-Deng conjecture on binary Hamming weights holds almost surely as $k\to\infty$.

The Tu-Deng Conjecture is concerned with the sum of digits of $n$ in base $2$ (the Hamming weight $w(n)$ of the binary expansion of $n$) and states the following: assume that $k$ is a positive integer and $0 < t < 2^k-1$. Then $$\left|\left\{ (a,b) \in \{0,...,2^k-2\}^2 : a+b = t \text{ mod } 2^k-1 \text{ and } w(a)+w(b) < k \right\}\right| \leq 2^{k-1}.$$ We prove that the Tu-Deng conjecture holds almost surely in the following sense: the proportion of $t \in [1,2^k-2]$ is such that the above inequality holds approaches one as $k$ tends to infinity. Moreover, we prove that the Tu-Deng conjecture implies a conjecture due to T. W. Cusick concerning the sum of digits of $n$ and $n+t$.
A bijection of plane increasing trees with relaxed binary trees of right height at most one

Michael Wallner

Theoretical Computer Science, 755, pp. 1–12, 2019

www arXiv

Bijection between plane increasing trees and bounded relaxed binary trees; central limit theorems for leaf statistics; 20+ subclasses enumerated.

Plane increasing trees are rooted labeled trees embedded into the plane such that the sequence of labels is increasing on any branch starting at the root. Relaxed binary trees are a subclass of unlabeled directed acyclic graphs. We construct a bijection between these two combinatorial objects and study the therefrom arising connections of certain parameters. Furthermore, we show central limit theorems for two statistics on leaves. We end the study by considering more than 20 subclasses and their bijective counterparts. Many of these subclasses are enumerated by known counting sequences, and thus enrich their combinatorial interpretation.
Explicit formulas for enumeration of lattice paths: basketball and the kernel method

Cyril Banderier, Christian Krattenthaler, Alan Krinik, Dmitry Kruchinin, Vladimir Kruchinin, David Nguyen, Michael Wallner

Lattice Path Combinatorics and Applications (G. E. Andrews, C. Krattenthaler, A. Krinik, eds.), Developments in Mathematics, Springer-Verlag, Cham, pp. 78–118 , 2019

www arXiv

Kernel method yields explicit nested binomial sum formulas for directed lattice walks with altitude constraints; basketball walks treated in full.

This article deals with the enumeration of directed lattice walks on the integers with any finite set of steps, starting at a given altitude j and ending at a given altitude k, with additional constraints such as, for example, to never attain altitude 0 in-between. We first discuss the case of walks on the integers with steps $-h, \dots, -1, +1, \dots, +h$. The case $h=1$ is equivalent to the classical Dyck paths, for which many ways of getting explicit formulas involving Catalan-like numbers are known. The case $h=2$ corresponds to "basketball walks", which we treat in full detail. Then we move on to the more general case of walks with any finite set of steps, also allowing some weights/probabilities associated with each step. We show how a method of wide applicability, the so-called "kernel method", leads to explicit formulas for the number of walks of length n, for any h, in terms of nested sums of binomials. We finally relate some special cases to other combinatorial problems, or to problems arising in queuing theory.
The kernel method for lattice paths below a line of rational slope

Cyril Banderier, Michael Wallner

Lattice Path Combinatorics and Applications (G. E. Andrews, C. Krattenthaler, A. Krinik, eds.), Developments in Mathematics, Springer-Verlag, Cham, pp. 119–154 , 2019

www arXiv zbMATH

Kernel method extended to multiple dominant singularities for paths below rational slopes; Knuth's problem on paths under $y = 2x/5$ solved.

We analyze some enumerative and asymptotic properties of lattice paths below a line of rational slope. We illustrate our approach with Dyck paths under a line of slope $2/5$. This answers Knuth's problem #4 from his "Flajolet lecture" during the conference "Analysis of Algorithms" (AofA'2014) in Paris in June 2014. Our approach extends the work of Banderier and Flajolet for asymptotics and enumeration of directed lattice paths to the case of generating functions involving several dominant singularities. A key ingredient in the proof is the generalization of an old trick by Knuth himself (for enumerating permutations sortable by a stack), promoted by Flajolet and others as the "kernel method". All the corresponding generating functions are algebraic, and they offer some new combinatorial identities, which can also be tackled in the A=B spirit of Wilf-Zeilberger-Petkovsek. We show how to obtain similar results for other slopes than $2/5$. An interesting case being e.g. Dyck paths below the slope $2/3$, which corresponds to the so called Duchon's club model. We also show how to use our techniques for lattice paths below an irrational slope and illustrate this with Dyck paths below $y=x/\sqrt{2}$.
- ↳
  
  Lattice paths of slope 2/5 (Extended abstract)
  
  Fourteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2015), San Diego, pp. 105–113, 2015
  
  www arXiv
  
  Extended abstract. Dyck paths under $y = 2x/5$: Knuth's problem solved via kernel method with algebraic generating functions.
  
  We analyze some enumerative and asymptotic properties of Dyck paths under a line of slope 2/5.This answers to Knuth's problem #4 from his "Flajolet lecture" during the conference "Analysis of Algorithms" (AofA'2014) in Paris in June 2014.Our approach relies on the work of Banderier and Flajolet for asymptotics and enumeration of directed lattice paths. A key ingredient in the proof is the generalization of an old trick of Knuth himself (for enumerating permutations sortable by a stack),promoted by Flajolet and others as the "kernel method". All the corresponding generating functions are algebraic,and they offer some new combinatorial identities, which can be also tackled in the A=B spirit of Wilf--Zeilberger--Petkov{\v s}ek.We show how to obtain similar results for other slopes than 2/5, an interesting case being e.g. Dyck paths below the slope 2/3, which corresponds to the so called Duchon's club model.

2018

Local time for lattice paths and the associated limit laws

Cyril Banderier, Michael Wallner

GAScom 2018, Athens, 2018

www arXiv

Local time at zero for generalized Dyck paths; geometric, negative binomial, Rayleigh, and half-normal limit laws depending on drift and walk type.

For generalized Dyck paths (i.e., directed lattice paths with any finite set of jumps), we analyse their local time at zero (i.e., the number of times the path is touching or crossing the abscissa). As we are in a discrete setting, the event we analyse here is "invisible" to the tools of Brownian motion theory. It is interesting that the key tool for analysing directed lattice paths, which is the kernel method, is not directly applicable here. Therefore, we introduce a variant of this kernel method to get the trivariate generating function (length, final altitude, local time): this leads to an expression involving symmetric and algebraic functions. We apply this analysis to different types of constrained lattice paths (meanders, excursions, bridges, ...). Then, we illustrate this approach on "basketball walks" which are walks defined by the jumps $\{-2,-1,0,+1,+2\}$. We use singularity analysis to prove that the limit laws for the local time are (depending on the drift and the type of walk) the geometric distribution, the negative binomial distribution, the Rayleigh distribution, or the half-normal distribution (a universal distribution up to now rarely encountered in analytic combinatorics).
Rectangular Young tableaux with local decreases and the density method for uniform random generation

Cyril Banderier, Philippe Marchal, Michael Wallner

GAScom 2018, Athens, 2018

www arXiv

Young tableaux allowing decreasing consecutive pairs; hook-length variants and density method for enumeration and random generation.

In this article, we consider a generalization of Young Tableaux in which we allow some consecutive pairs of cells with decreasing labels. We show that this leads to a rich variety of combinatorial formulas, which suggest that these new objects could be related to deeper structures, similarly to the ubiquitous Young tableaux. Our methods rely on variants of hook-length type formulas, and also on a new efficient generic method (which we call the density method) which allows not only to generate constrained combinatorial objects, but also to enumerate them. We also investigate some repercussions of this method on the D-finiteness of the generating functions of combinatorial objects encoded by linear extension diagrams, and give a limit law result for the average number of local decreases.
Divisibility of binomial coefficients by powers of two

Lukas Spiegelhofer, Michael Wallner

Journal of Number Theory, 192, pp. 221–239, 2018

www arXiv

The family $j \mapsto \Theta(j,n)$ (Pascal's triangle entries not divisible by $2^{j+1}$) usually follows a normal distribution.

For nonnegative integers $j$ and $n$ let $\Theta(j,n)$ be the number of entries in the $n$-th row of Pascal's triangle that are not divisible by $2^{j+1}$. In this paper we prove that the family $j\mapsto\Theta(j,n)$ usually follows a normal distribution. The method used for proving this theorem involves the computation of first and second moments of $\Theta(j,n)$, and uses asymptotic analysis of multivariate generating functions by complex analytic methods, building on earlier work by Drmota (1994) and Drmota, Kauers and Spiegelhofer (2016).
On the shape of random Pólya structures

Bernhard Gittenberger, Emma Yu Jin, Michael Wallner

Discrete Mathematics, 341(4), pp. 896–911, 2018

www arXiv

Uniform random Pólya trees consist of a conditioned Galton-Watson tree and forests of size $\Theta(\log n)$; combinatorial interpretation of forest weights via automorphisms.

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 $n$ consists of a conditioned critical Galton-Watson tree $C_n$ and many small forests, where with probability tending to one, as $n$ tends to infinity, any forest $F_n(v)$, that is attached to a node $v$ in $C_n$, is maximally of size $\vert F_n(v)\vert=O(\log n)$. Their proof used the framework of a Boltzmann sampler and deviation inequalities. In this paper, first, we employ a unified framework in analytic combinatorics to prove this fact with additional improvements for $\vert F_n(v)\vert$, namely $\vert F_n(v)\vert=\Theta(\log n)$. Second, we give a combinatorial interpretation of the rational weights of these forests and the defining substitution process in terms of automorphisms associated to a given Pólya tree. Third, we derive the limit probability that for a random node $v$ the attached forest $F_n(v)$ is of a given size. Moreover, structural properties of those forests like the number of their components are studied. Finally, we extend all results to other Pólya structures.
- ↳
  
  A note on the scaling limits of random Pólya trees (Extended abstract)
  
  Fourteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2017), Barcelona, pp. 85–93, 2017
  
  www arXiv
  
  Extended abstract. Uniform random Pólya trees decompose into a critical Galton-Watson tree and forests of size $\Theta(\log n)$.
  
  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 size $n$ consists of a conditioned critical Galton-Watson tree $C_n$ and many small forests, where with probability tending to one as $n$ tends to infinity, any forest $F_n(v)$, that is attached to a node $v$ in $C_n$, is maximally of size $\vert F_n(v)\vert=O(\log n)$. Their proof used the framework of a Boltzmann sampler and deviation inequalities. In this paper, first, we employ a unified framework in analytic combinatorics to prove this fact with additional improvements on the bound of $\vert F_n(v)\vert$, namely $\vert F_n(v)\vert=\Theta(\log n)$. Second, we give a combinatorial interpretation of the rational weights of these forests and the defining substitution process in terms of automorphisms associated to a given Pólya tree. Third, we derive the limit probability that for a random node $v$ the attached forest $F_n(v)$ is of a given size. Finally, we extend all results to other P\'{o}lya structure.

2017

An explicit generating function arising in counting binomial coefficients divisible by powers of primes

Lukas Spiegelhofer, Michael Wallner

Acta Arithmetica, 181, pp. 27–55, 2017

www arXiv

Generating functions for the polynomials $P_j$ counting binomial coefficients divisible by $p^j$; efficient computation via recurrence relations.

For a prime $p$ and nonnegative integers $j$ and $n$ let $\vartheta_p(j,n)$ be the number of entries in the $n$-th row of Pascal's triangle that are exactly divisible by $p^j$. Moreover, for a finite sequence $w=(w_{r-1}\cdots w_0)\neq (0,\ldots,0)$ in $\{0,\ldots,p-1\}$ we denote by $\lvert n\rvert_w$ the number of times that $w$ appears as a factor (contiguous subsequence) of the base-$p$ expansion $n=(n_{\mu-1}\cdots n_0)_p$ of $n$. It follows from the work of Barat and Grabner (Distribution of binomial coefficients and digital functions, J. London Math. Soc. (2) 64(3), 2001), that $\vartheta_p(j,n)/\vartheta_p(0,n)$ is given by a polynomial $P_j$ in the variables $X_w$, where $w$ are certain finite words in $\{0,\ldots,p-1\}$, and each variable $X_w$ is set to $\lvert n\rvert_w$. This was later made explicit by Rowland (The number of nonzero binomial coefficients modulo $p^\alpha$, J. Comb. Number Theory 3(1), 2011), independently from Barat and Grabner's work, and Rowland described and implemented an algorithm computing these polynomials $P_j$. In this paper, we express the coefficients of $P_j$ using generating functions, and we prove that these generating functions can be determined explicitly by means of a recurrence relation. Moreover, we prove that $P_j$ is uniquely determined, and we note that the proof of our main theorem also provides a new proof of its existence. Besides providing insight into the structure of the polynomials $P_j$, our results allow us to compute them in a very efficient way.
Lattice paths with catastrophes

Cyril Banderier, Michael Wallner

Discrete Mathematics & Theoretical Computer Science, 19(1), 2017

www arXiv zbMATH

Lattice paths with resets-to-zero: bijections, continued fractions, enumeration and limit laws via kernel method and analytic combinatorics.

In queuing theory, it is usual to have some models with a "reset" of the queue. In terms of lattice paths, it is similar to having the possibility of jumping from any altitude to zero. These objects have the interesting feature: They do not have the same intuitive probabilistic behaviour as classical Dyck paths (the typical properties of which are strongly related to Brownian motion theory). This article quantifies some relations between these two types of paths. We give a bijection with some other lattice paths and we make a connection with a continued fraction expansion. Furthermore, we prove several formulae for related combinatorial structures conjectured in the On-Line Encyclopedia of Integer Sequences. We use the kernel method and other tools from analytic combinatorics in order to provide the enumeration and limit laws of these lattice paths with catastrophes for all finite sets of jumps. We conclude by providing an algorithm which generates such lattice paths uniformly at random.
- ↳
  
  Lattice paths with catastrophes (Extended abstract)
  
  Electronic Notes in Discrete Mathematics, 59 (GAScom 2016 proceedings), pp. 131–146, 2017
  
  www
  
  Extended abstract. Queue resets modeled as jumps to zero; kernel method for enumeration and limit laws of catastrophe paths.
  
  In queuing theory, it is usual to have some models with a "reset" of the queue. In terms of lattice paths, it is like having the possibility of jumping from any altitude to zero. These objects have the interesting feature that they do not have the same intuitive probabilistic behavior like classical Dyck paths (the typical properties of which are strongly related to Brownian motion theory), and this article quantifies some relations between these two types of paths. We give a bijection with some other lattice paths and a link with a continuous fraction expansion, and prove several formulae for related combinatorial structures conjectured in the On-line Encyclopedia of Integer Sequences. Thanks to the kernel method and via analytic combinatorics, we derive the enumeration and limit laws of these "lattice paths with catastrophes", for any finite set of jumps.

2014

Some reflections on directed lattice paths

Cyril Banderier, Michael Wallner

25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2014), Paris, pp. 25–36, 2014

arXiv HAL

Directed lattice paths with reflecting/absorbing boundaries; kernel method modifications; asymptotics for excursions, arches, meanders.

This article analyzes directed lattice paths, when a boundary reflecting or absorbing condition is added to the classical models. The lattice paths are characterized by two time-independent sets of rules (also called steps) which have a privileged direction of increase and are therefore essentially one-dimensional objects. Depending on the spatial coordinate, one of the two sets of rules applies, namely one for altitude 0 and one for altitude bigger than 0. The abscissa y=0 thus acts as a border which either absorbs or reflects steps. The absorption model corresponds to the model analyzed by Banderier and Flajolet ("Analytic combinatorics of directed lattice paths"), while the reflecting model leads to a more complicated situation. We show how the generating functions are then modified: the kernel method strikes again but here it unfortunately does not give a nice product formula. This makes the analysis more challenging, and, in the case of Lukasiewicz walks, we give the asymptotics for the number of excursions, arches and meanders. Limit laws for the number of returns to 0 of excursions are given. We also compute the limit laws of the final altitude of meanders. The full analytic situation is more complicated than the Banderier-Flajolet model (partly because new "critical compositions" appear, forcing us to introduce new key quantities, like the drift at 0), and we quantify to what extent the global drift, and the drift at 0 play a role in the "universal" behavior of such walks.
- ↳
  
  The reflection-absorption model for directed lattice paths (Extended abstract)
  
  VIENNA young SCIENTISTS SYMPOSIUM (VSS 2016), Vienna, pp. 98–99, 2016
  
  www Poster
  
  Extended abstract. Kernel method for lattice paths with altitude-dependent steps (reflecting or absorbing at $y=0$); new critical compositions arise, and the drift at zero plays a key role distinct from the global drift.
  
  In this abstract we analyze directed lattice paths, when a boundary reflecting or absorbing condition is added to the classical models. The lattice paths are characterized by two time-independent sets of rules (also called steps) which have a privileged direction of increase. Depending on the spatial coordinate, one of the two sets of rules applies, namely one for altitude 0 and one for altitude bigger than 0. The abscissa y = 0 thus acts as a border which either absorbs or reflects steps. The absorption model extends the model analyzed by Banderier and Flajolet [Basic analytic combinatorics of directed lattice paths, 2002], while the reflection model leads to a more complicated situation. More details are given in [Some reflections on lattice paths, 2014].

2026

A Combinatorial Framework for the Pons-Batle Identity: Young Tableaux, Lattice Paths, and Limit Laws

Hexuan Liu, Guan-Ru Yu, Michael Wallner

Accepted AofA 2026, 2026

Bijections between Pons-Batle words and Young tableaux with walls and holes; Beta and Uniform limit laws.

Tree-child networks model reticulate evolutionary processes. This paper studies bicombining tree-child networks through combinatorial and analytic approaches, using Young tableaux with walls and holes and constructing bijections to Pons-Batle words. We derive algebraic generating functions with differential operators for enumeration formulas and reveal probabilistic structures with Beta and Uniform limit distributions.
Bivariate asymptotics via random walks: application to large genus maps

Andrew Elvey Price, Wenjie Fang, Baptiste Louf, Michael Wallner

Preprint

arXiv zbMATH

Bivariate asymptotics for unicellular maps as size and genus grow simultaneously, via linear recurrences and complex analysis.

We obtain bivariate asymptotics for the number of (unicellular) combinatorial maps (a model of discrete surfaces) as both the size and the genus grow. This work is related to two research topics that have been very active recently: multivariate asymptotics and large genus geometry. Our method consists of studying a linear recurrence for these numbers, and can be applied to many other linear recurrences. In particular, we include a general theorem that yields asymptotics for such recurrences, provided that some assumptions are satisfied.
The decompressed tree size of k-ary chains

Michael Wallner

Accepted Annals of Combinatorics, 2026

www arXiv zbMATH

Expected decompressed tree size of a $k$-ary chain of size $n$ contains a stretched exponential $e^{c\,\sqrt{n}}$.

A chain is a directed acyclic graph (DAG) with one source and one sink, where the children are ordered and the spanning tree is a path. Such DAGs arise in the compression of trees and are therefore uniquely associated with a tree. The tree size of a DAG is therefore the size of the associated tree. For fixed finite out-degrees, we compute the expected decompressed tree size of a chain of size n chosen uniformly at random, and show that it contains a stretched exponential term of the form $e^{c \, \sqrt{n}}$. The key idea is to use a special generating function that generalizes exponential generating functions and allows the decompressed trees to be constructed symbolically.

2025

Bivariate asymptotics via random walks: application to large genus maps (Extended abstract)

Andrew Elvey Price, Wenjie Fang, Baptiste Louf, Michael Wallner

37th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2025), 2025

www arXiv

Extended Abstract. Bivariate asymptotics for unicellular maps as size and genus grow simultaneously, via linear recurrences and complex analysis.

We obtain bivariate asymptotics for the number of (unicellular) combinatorial maps (a model of discrete surfaces) as both the size and the genus grow. This work is related to two research topics that have been very active recently: multivariate asymptotics and large genus geometry. Our method consists in studying a linear recurrence for these numbers, and in fact it can be applied to many other linear recurrences. We discuss briefly the generality of our method and future research directions.
The decompressed tree size of k-ary chains (Extended abstract)

Michael Wallner

European Conference on Combinatorics, Graph Theory and Applications (Eurocomb'25), Budapest, 2025

www

Extended abstract. Stretched exponential $e^{c\sqrt{n}}$ in the expected decompressed tree size of a $k$-ary chain.

A chain is a directed acyclic graph (DAG) with one source and one sink, where the children are ordered and the spanning tree is a path. Such DAGs arise in the compression of trees and are therefore uniquely associated with a tree. The tree size of a DAG is therefore the size of the associated tree. For fixed finite out-degrees, we compute the expected decompressed tree size of a chain of size n chosen uniformly at random, and show that it contains a stretched exponential term of the form $e^{c \, \sqrt{n}}$. The key idea is to use a special generating function that generalizes exponential generating functions and allows the decompressed trees to be constructed symbolically.

2024

Asymptotics of relaxed k-ary trees

Manosij Ghosh Dastidar, Michael Wallner

35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024), 2024

www arXiv Maple zbMATH

Stretched exponential $e^{c n^{1/3}}$ in the asymptotics of relaxed $k$-ary trees, for all finite arities; recurrences for compacted trees and minimal DFA.

A relaxed $k$-ary tree is an ordered directed acyclic graph with a unique source and sink in which every node has out-degree $k$. These objects arise in the compression of trees in which some repeated subtrees are factored and repeated appearances are replaced by pointers. We prove an asymptotic theta-result for the number of relaxed $k$-ary tree with $n$ nodes for $n \to \infty$. This generalizes the previously proved binary case to arbitrary finite arity, and shows that the seldom observed phenomenon of a stretched exponential term $e^{c n^{1/3}}$ appears in all these cases. We also derive the recurrences for compacted $k$-ary trees in which all subtrees are unique and minimal deterministic finite automata accepting a finite language over a finite alphabet.
Composition schemes: q-enumerations and phase transitions in Gibbs models

Cyril Banderier, Markus Kuba, Stephan Wagner, Michael Wallner

35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024), 2024

www arXiv zbMATH

Phase transitions in $q$-enumeration via composition schemes: Mittag-Leffler, Gaussian, and Boltzmann limit laws depending on the regime.

Composition schemes are ubiquitous in combinatorics, statistical mechanics and probability theory. We give a unifying explanation to various phenomena observed in the combinatorial and statistical physics literature in the context of $q$-enumeration (this is a model where objects with a parameter of value $k$ have a Gibbs measure/Boltzmann weight $q^k$). For structures enumerated by a composition scheme, we prove a phase transition for any parameter having such a Gibbs measure: for a critical value $q=q_c$, the limit law of the parameter is a two-parameter Mittag-Leffler distribution, while it is Gaussian in the supercritical regime ($q>q_c$), and it is a Boltzmann distribution in the subcritical regime ( $0 < q < q_c$). We apply our results to fundamental statistics of lattice paths and quarter-plane walks. We also explain previously observed limit laws for pattern-restricted permutations, and a phenomenon uncovered by Krattenthaler for the wall contacts in watermelons.
A bijection between stacked directed polyominoes and Motzkin paths with alternative catastrophes

Florian Schager, Michael Wallner

GASCom 2024, 2024

www arXiv zbMATH

Novel bijection between stacked directed polyominoes and Motzkin paths with alternative catastrophes.

We present a novel bijection between stacked directed polyominoes and Motzkin paths with alternative catastrophes. Further, we show how this new connection can be used in order to obtain a better understanding of certain parameters of stacked directed animals.
Bijections and congruences involving lattice paths and integer compositions

Manosij Ghosh Dastidar, Michael Wallner

Submitted

arXiv zbMATH

New bijections explain the counting formula $4^{n-1}$ for Dyck paths and integer compositions; connections to mock theta functions and Fibonacci numbers.

We prove new bijections between different variants of Dyck paths and integer compositions, which give combinatorial explanations of their simple counting formula $4^{n−1}$. These give relations between different statistics, such as the number of crossings of the x-axis in classes of Dyck bridges or the distribution of peaks in classes of Dyck paths, and furthermore relate them with k- and g-compositions. These allow us to find and prove congruence results for Dyck paths and parity results for compositions. Our investigation uncovers unexpected connections to mock theta functions, Hardinian arrays, little Schröder paths, Fibonacci numbers, and irreducible pairs of compositions, offering new insights into the structures of paths, partitions and compositions.
Bijections between variants of Dyck paths and integer compositions (Extended abstract)

Manosij Ghosh Dastidar, Michael Wallner

GASCom 2024, 2024

www arXiv zbMATH

Extended abstract. Bijective results between Dyck path variants and integer compositions enumerated by $4^{n-1}$; congruence relationships.

We give bijective results between several variants of lattice paths and integer compositions all enumerated by the seemingly innocuous formula $4^{n-1}$. These associations lead us to make more connections between the two constructs such as congruence results.
Enumerative and Distributional Results for d-combining Tree-Child Networks

Yu-Sheng Chang, Michael Fuchs, Hexuan Liu, Guan-Ru Yu, Michael Wallner

Advances in Applied Mathematics, 157, 102704, 2024

www arXiv Maple zbMATH

Exact formulas and phase transitions (normal, Bessel, Poisson, degenerate) for shape parameters of $d$-combining tree-child networks.

Tree-child networks are one of the most prominent network classes for modeling evolutionary processes which contain reticulation events. Several recent studies have addressed counting questions for {\it bicombining tree-child networks} in which every reticulation node has exactly two parents. We extend these studies to {\it $d$-combining tree-child networks} where every reticulation node has now $d\geq 2$ parents, and we study one-component as well as general tree-child networks. Moreover, we also give results on the distributional behavior of shape parameters (e.g., number of reticulation nodes, Sackin index) of a network which is drawn uniformly at random from the set of all tree-child networks with the same number of leaves. We show phase transitions depending on $d$, leading to normal, Bessel, Poisson, and degenerate distributions. Some of our results are new even in the bicombining case.
Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions

Cyril Banderier, Markus Kuba, Michael Wallner

Annals of Applied Probability, 34(5), pp. 4635–4693, 2024

www arXiv zbMATH

Three-parameter Mittag-Leffler distribution as a universal law; double phase transitions involving Boltzmann and mixed Poisson distributions.

Multitudinous combinatorial structures are counted by generating functions satisfying a composition scheme $$F(z)=G(H(z)).$$ The corresponding asymptotic analysis becomes challenging when this scheme is critical (i.e., $G$ and $H$ are simultaneously singular). The singular exponents appearing in the Puiseux expansions of G and H then dictate the asymptotics. In this work, we first complement results of Flajolet et al. for a full family of singular exponents of $G$ and $H$. We identify the arising limit laws (for the number of $H$-components in $F$) and prove moment convergence. Then, motivated by many examples (random mappings, planar maps, directed lattice paths), we consider a natural extension of this scheme, namely $$F(z)=G(H(z))M(z).$$ We discuss the number of $H$-components of a given size in $F$; this leads to a nice world of limit laws involving products of beta and Mittag-Leffler distributions. We also obtain continuous to discrete phase transitions involving mixed Poisson distributions, giving an unified explanation of the associated thresholds. We end with extensions of the critical composition scheme to a cycle scheme and to the multivariate case, leading again to product distributions. Applications are presented for random walks, trees (supertrees of trees, increasingly labelled trees, preferential attachment trees), triangular Pólya urns, and the Chinese restaurant process.

2023

Dyck paths and inversion tables

Michael Wallner

Permutation Patterns 2023, pp. 142–144, 2023

www

Inversion tables generalized to boxed Dyck paths; bijections with increasing Cayley trees, binary trees, and relaxed binary trees.

We generalize inversion tables, which are in bijection with permutations, to boxed Dyck paths, where the number of markers in each row depends on a path that may differ from the staircase path. We demonstrate that subclasses of this family correspond to various combinatorial objects, including increasing Cayley trees, increasing binary trees, and relaxed binary trees. Moreover, we discuss the relationship between the path and the markers and enumerate some of the aforementioned subclasses.
The binary digits of n+t

Lukas Spiegelhofer, Michael Wallner

Annali della Scuola Normale Superiore di Pisa, Classe di Scienze, 24(1), pp. 1–31, 2023

www arXiv zbMATH

Cusick's conjecture proved for $t$ with sufficiently many blocks of 1s; Gaussian behavior of $s(n+t)-s(n)$.

The binary sum-of-digits function $s$ counts the number of $\mathtt 1$s in the base-$2$ expansion of a nonnegative integer. T. W. Cusick defined the asymptotic density $$c_t=\lim_{N\rightarrow \infty} \frac 1N \#\{0\leq n \lt N:s(n+t)\geq s(n)\}$$ for integers $t\geq 0$ and conjectured that $c_t>1/2$ for all $t$. We prove that indeed $c_t>1/2$ if the binary expansion of $t$ contains at least $K$ blocks of contiguous $1$s, where $K$ is an absolute, effective constant.
Walks avoiding a quadrant and the reflection principle

Mireille Bousquet-Mélou, Michael Wallner

European Journal of Combinatorics, 103803, 2023

www arXiv Maple Slides zbMATH

Generating function for king walks avoiding the negative quadrant: D-finite series plus algebraic component; algebraicity for Weyl step sets.

We continue the enumeration of plane lattice walks with small steps avoiding the negative quadrant, initiated by the first author in 2016. We solve in detail a new case, namely the king model where all eight nearest neighbour steps are allowed. The associated generating function is proved to be the sum of a simple, explicit D-finite series (related to the number of walks confined to the first quadrant), and an algebraic one. This was already the case for the two models solved by the first author in 2016. The principle of the approach is also the same, but challenging theoretical and computational difficulties arise as we now handle algebraic series of larger degree. We expect a similar algebraicity phenomenon to hold for the seven Weyl step sets, which are those for which walks confined to the first quadrant can be counted using the reflection principle. With this paper, this is now proved for three of them. For the remaining four, we predict the D-finite part of the solution, and in three of the four cases, give evidence for the algebraicity of the remaining part.
Combinatorics of nondeterministic walks

Élie de Panafieu, Michael Wallner

Submitted

arXiv Maple Git Slides

Nondeterministic bridges, excursions, and meanders with Dyck/Motzkin steps are algebraic; reachable endpoint sets; Python and Maple packages.

This paper introduces nondeterministic walks, a new variant of one-dimensional discrete walks. The main difference to classical walks is that its nondeterministic steps consist of sets of steps from a predefined set such that all possible extensions are explored in parallel. We discuss in detail the most natural nondeterministic step sets (Dyck and Motzkin step sets), and show that several nondeterministic classes of lattice paths, such as nondeterministic bridges, excursions, and meanders are algebraic. The key concept is the generalization of the ending point of a walk to its reachable points, i.e., a set of ending points. We extend our results to general step sets: We show that nondeterministic bridges and several subclasses of nondeterministic meanders are always algebraic. We conjecture the same is true for nondeterministic excursions, and we present python and Maple packages to support our conjecture. This research is motivated by the study of networks involving encapsulation and decapsulation of protocols. Our results are obtained using generating functions, analytic combinatorics, and additive combinatorics.

2022

Enumeration of d-combining Tree-Child Networks (Extended abstract)

Yu-Sheng Chang, Michael Fuchs, Hexuan Liu, Guan-Ru Yu, Michael Wallner

33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022), 2022

www arXiv Maple zbMATH

Extended abstract. Counting and distributional results for $d$-combining tree-child networks with $d\geq 2$ parents per reticulation node.

Tree-child networks are one of the most prominent network classes for modeling evolutionary processes which contain reticulation events. Several recent studies have addressed counting questions for bicombining tree-child networks which are tree-child networks with every reticulation node having exactly two parents. In this paper, we extend these studies to $d$-combining tree-child networks where every reticulation node has now $d\geq 2$ parents. Moreover, we also give results and conjectures on the distributional behavior of the number of reticulation nodes of a network which is drawn uniformly at random from the set of all tree-child networks with the same number of leaves.
On the critical exponents of generalized ballot sequences in three dimensions and large tandem walks

Michael Wallner

Aequationes Mathematicae, 96, pp. 815–826, 2022

www arXiv zbMATH

Ballot walk models are not $D$-finite; tandem walks generalized bijectively to ballot walks in three dimensions.

We answer some questions on the asymptotics of ballot walks raised in [Personal Journal Shalosh B Ekhad and Doron Zeilberger, Apr 5, 2021; see also arXiv:2104.01731] and prove that these models are not D-finite. This short note demonstrates how the powerful tools developed in the last decades on lattice paths in convex cones help us to answer some challenging problems that were out of reach for a long time. On the way we generalize tandem walks to the family of large tandem walks whose steps are of arbitrary length and map them bijectively to a generalization of ballot walks in three dimensions.

2021

Young tableaux with periodic walls: counting with the density method

Cyril Banderier, Michael Wallner

33rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2021), 2021

www zbMATH

Generalized Young tableaux with periodic walls (Jenga tableaux): algebraic, hypergeometric, $D$-finite, and differentially-algebraic generating functions.

We consider a generalization of Young tableaux in which we allow some consecutive pairs of cells with decreasing labels, conveniently visualized by a "wall" between the corresponding cells. Some shapes can be enumerated by variants of hook-length type formulas. We focus on families of tableaux (like the so-called "Jenga tableaux") having some periodic shapes, for which the generating functions are harder to obtain. We get some interesting new classes of recurrences, and a surprisingly rich zoo of generating functions (algebraic, hypergeometric, D-finite, differentially-algebraic). Some patterns lead to nice bijections with trees, lattice paths, or permutations. Our approach relies on the density method, a powerful way to perform both random generation and enumeration of linear extensions of posets.
Compacted binary trees admit a stretched exponential

Andrew Elvey Price, Wenjie Fang, Michael Wallner

Journal of Combinatorial Theory, Series A, 177, 105306, 2021

www arXiv Maple Slides

Compacted binary trees of size $n$ grow like $\Theta\!\left(n!\cdot 4^n\cdot e^{3a_1 n^{1/3}}\cdot n^{3/4}\right)$; quadratic-complexity algorithm via two-parameter recurrence.

A compacted binary tree is a directed acyclic graph encoding a binary tree in which common subtrees are factored and shared, such that they are represented only once. We show that the number of compacted binary trees of size n grows asymptotically like $$\Theta \left( n! \, 4^n e^{3 a_1 n^{1/3}} n^{3/4} \right),$$ where $a_1 \approx 2.338$ is the largest root of the Airy function. Our method involves a new two parameter recurrence which yields an algorithm of quadratic arithmetic complexity. We use empirical methods to estimate the values of all terms defined by the recurrence, then we prove by induction that these estimates are sufficiently accurate for large n to determine the asymptotic form. Our results also lead to new bounds on the number of minimal finite automata recognizing a finite language on a binary alphabet. As a consequence, these also exhibit a stretched exponential.

2020

More Models of Walks Avoiding a Quadrant (Extended abstract)

Mireille Bousquet-Mélou, Michael Wallner

31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), 2020

www arXiv Video zbMATH

Extended abstract. King walks avoiding the negative quadrant: D-finite plus algebraic generating function decomposition.

We continue the enumeration of plane lattice paths avoiding the negative quadrant initiated by the first author in [Bousquet-Mélou 2016]. We solve in detail a new case, where all 8 nearest neighbour steps are allowed. As in the two cases solved in [Bousquet-Mélou 2016], the associated generating function is proved to differ from a simple, explicit D-finite series (related to the enumeration of walks confined to the first quadrant) by an algebraic one. The principle of the approach is the same as in [Bousquet-Mélou 2016], but challenging theoretical and computational difficulties arise as we now handle algebraic series of larger degree. We also explain why we expect the observed algebraicity phenomenon to persist for 4 more models, for which the quadrant problem is solvable using the reflection principle.
Latticepathology and Symmetric Functions

Cyril Banderier, Marie-Louise Lackner, Michael Wallner

31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), 2020

www Poster

Prime walks as natural structures for excursion decompositions; bivariate Spitzer/Wiener-Hopf formulas for lattice paths.

We revisit and extend a list of formulas based on lattice path surgery: cut-and-paste methods, factorizations, the kernel method, etc. For this purpose, we focus on the natural model of directed lattice paths (also called generalized Dyck paths). We introduce the notion of prime walks, which appear to be the key structure to get natural decompositions of excursions, meanders, bridges, directly leading to the associated context-free grammars. This allows us to give bijective proofs of bivariate versions of Spitzer/Sparre Andersen/Wiener--Hopf formulas, paving the way for many joint distribution studies. We also show that each of the fundamental families of symmetric polynomials correspond to a lattice path generating function, and that these symmetric polynomials are accordingly needed to express the asymptotic enumeration of these paths and some parameters of limit laws. En passant, we give two other small results which have their own interest for folklore conjectures of lattice paths (non-analyticity of the small roots in the kernel method, and universal positivity of the variability condition occurring in many Gaussian limit law schemes).
Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language

Andrew Elvey Price, Wenjie Fang, Michael Wallner

31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), 2020

www Maple

Minimal DFAs over a binary alphabet grow as $\Theta\!\left(n!\cdot 4^n\cdot e^{3a_1 n^{1/3}}\cdot n^{7/8}\right)$ where $a_1$ is the largest Airy root.

We show that the number of minimal discrete finite automata with n transient states recognizing a finite binary language grows asymptotically for n to infinity like $$\Theta \left( n! \, 4^n e^{3 a_1 n^{1/3}} n^{7/8} \right),$$ where $a_1 \approx 2.338$ is the largest root of the Airy function. For this purpose, we use a new asymptotic enumeration method proposed by the same authors in a recent preprint (2019). We first derive a new two parameter recurrence relation for the number of such automata up to a given size. Using this result, we prove by induction asymptotically tight bounds that are sufficiently accurate for large n to determine the asymptotic form using adapted Newton polygons.
Counting and sampling gene family evolutionary histories in the duplication-loss and duplication-loss-transfer models

Cedric Chauve, Yann Ponty, Michael Wallner

Journal of Mathematical Biology, 80(5), pp. 1353–1388, 2020

www arXiv

Formal grammars for gene family histories in the DLT-model; efficient counting and uniform random generation; horizontal transfer dramatically increases the number of histories.

Given a set of species whose evolution is represented by a species tree, a gene family is a group of genes having evolved from a single ancestral gene. A gene family evolves along the branches of a species tree through various mechanisms, including - but not limited to - speciation (S), gene duplication (D), gene loss (L), horizontal gene transfer (T). The reconstruction of a gene tree representing the evolution of a gene family constrained by a species tree is an important problem in phylogenomics. However, unlike in the multispecies coalescent evolutionary model that considers only speciation and incomplete lineage sorting events, very little is known about the search space for gene family histories accounting for gene duplication, gene loss and horizontal gene transfer (the DLT-model). In this work, we introduce the notion of evolutionary histories defined as a binary ordered rooted tree describing the evolution of a gene family, constrained by a species tree in the DLT-model. We provide formal grammars describing the set of all evolutionary histories that are compatible with a given species tree, whether it is ranked or unranked. These grammars allow us, using either analytic combinatorics or dynamic programming, to efficiently compute the number of histories of a given size, and also to generate random histories of a given size under the uniform distribution. We apply these tools to obtain exact asymptotics for the number of gene family histories for two species trees, the rooted caterpillar and the complete binary tree, as well as estimates of the range of the exponential growth factor of the number of histories for random species trees of size up to 25. Our results show that including horizontal gene transfer induce a dramatic increase of the number of evolutionary histories. We also show that, within ranked species trees, the number of evolutionary histories in the DLT-model is almost independent of the species tree topology. These results establish firm foundations for the development of ensemble methods for the prediction of reconciliations.
Periodic Pólya Urns, the Density Method, and Asymptotics of Young Tableaux

Cyril Banderier, Philippe Marchal, Michael Wallner

Annals of Probability, 48(4), pp. 1921–1965, 2020

www arXiv

Periodic Pólya urns have asymptotic fluctuations described by products of generalized gamma distributions; application to triangular Young tableaux.

Pólya urns are urns where at each unit of time a ball is drawn and replaced with some other balls according to its colour. We introduce a more general model: the replacement rule depends on the colour of the drawn ball and the value of the time (mod p). We extend the work of Flajolet et al. on Pólya urns: the generating function encoding the evolution of the urn is studied by methods of analytic combinatorics. We show that the initial differential equations lead to ordinary linear differential equations which are related to hypergeometric functions (giving the exact state of the urns at time n). When the time goes to infinity, we prove that these periodic Pólya urns have asymptotic fluctuations which are described by a product of generalized gamma distributions. With the additional help of what we call the density method (a method which offers access to enumeration and random generation of poset structures), we prove that the law of the south-east corner of a triangular Young tableau follows asymptotically a product of generalized gamma distributions. This allows us to tackle some questions related to the continuous limit of large random Young tableaux and links with random surfaces.
Asymptotic Enumeration of Compacted Binary Trees of Bounded Right Height

Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers, Michael Wallner

Journal of Combinatorial Theory, Series A, 172, Article 105177, 2020

www arXiv

Asymptotic counting of compacted trees of bounded right height $k$: growth rates $(4\cos(\pi/(k+3))^2)^n$ with polynomial corrections.

A compacted 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 every subtree is unique. Such representations form a special class of directed acyclic graphs. We are interested in the asymptotic number of compacted trees of given size, where the size of a compacted tree is given by the number of its internal nodes. Due to its superexponential growth this problem poses many difficulties. Therefore we restrict our investigations to compacted trees of bounded right height, which is the maximal number of edges going to the right on any path from the root to a leaf. We solve the asymptotic counting problem for this class as well as a closely related, further simplified class. For this purpose, we develop a calculus on exponential generating functions for compacted trees of bounded right height and for relaxed trees of bounded right height, which differ from compacted trees by dropping the above described uniqueness condition. This enables us to derive a recursively defined sequence of differential equations for the exponential generating functions. The coefficients can then be determined by performing a singularity analysis of the solutions of these differential equations. Our main results are the computation of the asymptotic numbers of relaxed ($r_{k,n}$) as well as compacted trees ($c_{k,n}$) of bounded right height at most $k$ and given size $n$, when the size tends to infinity: \begin{align*} r_{k,n} &\sim \gamma_k n!\left(4 \cos\left(\frac{\pi}{k+3}\right)^2\right)^{n} n^{-\frac{k}{2}} \\ c_{k,n} &\sim \kappa_k n! \left(4 \cos\left(\frac{\pi}{k+3}\right)^2\right)^{n} n^{- \frac{k}{2} - \frac{1}{k+3} - \left(\frac{1}{4} - \frac{1}{k+3}\right)\cos\left(\frac{\pi}{k+3} \right)^{-2}} \end{align*} Here $\gamma_k$ and $\kappa_k$ are nonzero, positive constants which are independent of $n$.
A half-normal distribution scheme for generating functions

Michael Wallner

European Journal of Combinatorics, 87, 103138, 2020

www arXiv

General theorem: bivariate generating functions under zero drift yield half-normal distributions; applications to returns to zero, height, sign changes.

We present a general theorem on the structure of bivariate generating functions which gives sufficient conditions such that the limiting probability distribution is a half-normal distribution. If $X$ is a normally distributed random variable with zero mean, then $|X|$ obeys a half-normal distribution. In the second part, we apply our result to prove three natural appearances in the domain of lattice paths: the number of returns to zero, the height, and the sign changes are under zero drift distributed according to a half-normal distribution. This extends known results to a general step set. Finally, our result also gives a new proof of Banach's matchbox problem.

2019

De la probabilité de creuser un tunnel (French abstract)

Élie de Panafieu, Mohamed Lamine Lamali, Michael Wallner

AlgoTel 2019, Saint Laurent de la Cabrerisse, 2019

HAL

Feasibility probability of protocol paths with nested encapsulations/decapsulations computed via Dyck and Motzkin path generating functions (French-language abstract).

Un tunnel est une portion d'un chemin où un protocole de communication est encapsulé dans un autre. Les tunnels sont de plus en plus présents dans les réseaux. Ils sont utilisés pour la sécurité, l'interopérabilité, les réseaux virtuels, etc. Un chemin contenant un tunnel doit ^etre faisable, c'est-à-dire qu'il doit respecter l'ordre des encapsulations et des désencapsulations, parfois imbriquées. Les algorithmes de calcul de chemins avec prise en compte de tunnels ne sont pas les m^emes que dans un réseau classique. Afin de tester ces algorithmes, il serait utile de disposer d'un générateur de topologies aléatoires avec tunnels. Ce générateur devra produire des topologies ayant certaines caractéristiques (par exemple, que la probabilité qu'un chemin soit faisable soit un paramètre p quelconque). Il se trouve que ce problème est lié aux chemins de Dyck et de Motzkin en combinatoire. En effet, une encapsulation peut ^etre vue comme un pas montant et une désencapsulation peut ^etre vue comme un pas descendant. La question qui se pose est donc de savoir quelle est la probabilité qu'un chemin de Dyck ou de Motzkin ait certaines propriétés. Dans ce travail, en utilisant des outils de combinatoire analytique, nous donnons la probabilité qu'un chemin soit faisable en fonction de la distribution des encapsulations et des désencapsulations sur les sommets.
Combinatorics of nondeterministic walks of the Dyck and Motzkin type (Extended abstract)

Élie de Panafieu, Mohamed Lamine Lamali, Michael Wallner

Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2019), San Diego, 2019

www arXiv

Generating functions for nondeterministic Dyck/Motzkin walks (bridges, meanders, excursions); motivated by protocol encapsulation.

This paper introduces nondeterministic walks, a new variant of one-dimensional discrete walks. At each step, a nondeterministic walk draws a random set of steps from a predefined set of sets and explores all possible extensions in parallel. We introduce our new model on Dyck steps with the nondeterministic step set $\{ \{-1\}, \{1\}, \{-1,1\}\}$ and Motzkin steps with the nondeterministic step set $\{\{-1\}, \{0\}, \{1\}, \{-1,0\}, \{-1,1\}, \{0,1\}, \{-1,0,1\}\}$. For general lists of step sets and a given length, we express the generating function of nondeterministic walks where at least one of the walks explored in parallel is a bridge (ends at the origin). In the particular cases of Dyck and Motzkin steps, we also compute the asymptotic probability that at least one of those parallel walks is a meander (stays nonnegative) or an excursion (stays nonnegative and ends at the origin). This research is motivated by the study of networks involving encapsulations and decapsulations of protocols. Our results are obtained using generating functions and analytic combinatorics.
The Tu-Deng conjecture holds almost surely

Lukas Spiegelhofer, Michael Wallner

The Electronic Journal of Combinatorics, 26(1), Paper 1.28, 28 pp., 2019

www arXiv Maple

The Tu-Deng conjecture on binary Hamming weights holds almost surely as $k\to\infty$.

The Tu-Deng Conjecture is concerned with the sum of digits of $n$ in base $2$ (the Hamming weight $w(n)$ of the binary expansion of $n$) and states the following: assume that $k$ is a positive integer and $0 < t < 2^k-1$. Then $$\left|\left\{ (a,b) \in \{0,...,2^k-2\}^2 : a+b = t \text{ mod } 2^k-1 \text{ and } w(a)+w(b) < k \right\}\right| \leq 2^{k-1}.$$ We prove that the Tu-Deng conjecture holds almost surely in the following sense: the proportion of $t \in [1,2^k-2]$ is such that the above inequality holds approaches one as $k$ tends to infinity. Moreover, we prove that the Tu-Deng conjecture implies a conjecture due to T. W. Cusick concerning the sum of digits of $n$ and $n+t$.
A bijection of plane increasing trees with relaxed binary trees of right height at most one

Michael Wallner

Theoretical Computer Science, 755, pp. 1–12, 2019

www arXiv

Bijection between plane increasing trees and bounded relaxed binary trees; central limit theorems for leaf statistics; 20+ subclasses enumerated.

Plane increasing trees are rooted labeled trees embedded into the plane such that the sequence of labels is increasing on any branch starting at the root. Relaxed binary trees are a subclass of unlabeled directed acyclic graphs. We construct a bijection between these two combinatorial objects and study the therefrom arising connections of certain parameters. Furthermore, we show central limit theorems for two statistics on leaves. We end the study by considering more than 20 subclasses and their bijective counterparts. Many of these subclasses are enumerated by known counting sequences, and thus enrich their combinatorial interpretation.
Explicit formulas for enumeration of lattice paths: basketball and the kernel method

Cyril Banderier, Christian Krattenthaler, Alan Krinik, Dmitry Kruchinin, Vladimir Kruchinin, David Nguyen, Michael Wallner

Lattice Path Combinatorics and Applications (G. E. Andrews, C. Krattenthaler, A. Krinik, eds.), Developments in Mathematics, Springer-Verlag, Cham, pp. 78–118 , 2019

www arXiv

Kernel method yields explicit nested binomial sum formulas for directed lattice walks with altitude constraints; basketball walks treated in full.

This article deals with the enumeration of directed lattice walks on the integers with any finite set of steps, starting at a given altitude j and ending at a given altitude k, with additional constraints such as, for example, to never attain altitude 0 in-between. We first discuss the case of walks on the integers with steps $-h, \dots, -1, +1, \dots, +h$. The case $h=1$ is equivalent to the classical Dyck paths, for which many ways of getting explicit formulas involving Catalan-like numbers are known. The case $h=2$ corresponds to "basketball walks", which we treat in full detail. Then we move on to the more general case of walks with any finite set of steps, also allowing some weights/probabilities associated with each step. We show how a method of wide applicability, the so-called "kernel method", leads to explicit formulas for the number of walks of length n, for any h, in terms of nested sums of binomials. We finally relate some special cases to other combinatorial problems, or to problems arising in queuing theory.
The kernel method for lattice paths below a line of rational slope

Cyril Banderier, Michael Wallner

Lattice Path Combinatorics and Applications (G. E. Andrews, C. Krattenthaler, A. Krinik, eds.), Developments in Mathematics, Springer-Verlag, Cham, pp. 119–154 , 2019

www arXiv zbMATH

Kernel method extended to multiple dominant singularities for paths below rational slopes; Knuth's problem on paths under $y = 2x/5$ solved.

We analyze some enumerative and asymptotic properties of lattice paths below a line of rational slope. We illustrate our approach with Dyck paths under a line of slope $2/5$. This answers Knuth's problem #4 from his "Flajolet lecture" during the conference "Analysis of Algorithms" (AofA'2014) in Paris in June 2014. Our approach extends the work of Banderier and Flajolet for asymptotics and enumeration of directed lattice paths to the case of generating functions involving several dominant singularities. A key ingredient in the proof is the generalization of an old trick by Knuth himself (for enumerating permutations sortable by a stack), promoted by Flajolet and others as the "kernel method". All the corresponding generating functions are algebraic, and they offer some new combinatorial identities, which can also be tackled in the A=B spirit of Wilf-Zeilberger-Petkovsek. We show how to obtain similar results for other slopes than $2/5$. An interesting case being e.g. Dyck paths below the slope $2/3$, which corresponds to the so called Duchon's club model. We also show how to use our techniques for lattice paths below an irrational slope and illustrate this with Dyck paths below $y=x/\sqrt{2}$.

2018

Local time for lattice paths and the associated limit laws

Cyril Banderier, Michael Wallner

GAScom 2018, Athens, 2018

www arXiv

Local time at zero for generalized Dyck paths; geometric, negative binomial, Rayleigh, and half-normal limit laws depending on drift and walk type.

For generalized Dyck paths (i.e., directed lattice paths with any finite set of jumps), we analyse their local time at zero (i.e., the number of times the path is touching or crossing the abscissa). As we are in a discrete setting, the event we analyse here is "invisible" to the tools of Brownian motion theory. It is interesting that the key tool for analysing directed lattice paths, which is the kernel method, is not directly applicable here. Therefore, we introduce a variant of this kernel method to get the trivariate generating function (length, final altitude, local time): this leads to an expression involving symmetric and algebraic functions. We apply this analysis to different types of constrained lattice paths (meanders, excursions, bridges, ...). Then, we illustrate this approach on "basketball walks" which are walks defined by the jumps $\{-2,-1,0,+1,+2\}$. We use singularity analysis to prove that the limit laws for the local time are (depending on the drift and the type of walk) the geometric distribution, the negative binomial distribution, the Rayleigh distribution, or the half-normal distribution (a universal distribution up to now rarely encountered in analytic combinatorics).
Rectangular Young tableaux with local decreases and the density method for uniform random generation

Cyril Banderier, Philippe Marchal, Michael Wallner

GAScom 2018, Athens, 2018

www arXiv

Young tableaux allowing decreasing consecutive pairs; hook-length variants and density method for enumeration and random generation.

In this article, we consider a generalization of Young Tableaux in which we allow some consecutive pairs of cells with decreasing labels. We show that this leads to a rich variety of combinatorial formulas, which suggest that these new objects could be related to deeper structures, similarly to the ubiquitous Young tableaux. Our methods rely on variants of hook-length type formulas, and also on a new efficient generic method (which we call the density method) which allows not only to generate constrained combinatorial objects, but also to enumerate them. We also investigate some repercussions of this method on the D-finiteness of the generating functions of combinatorial objects encoded by linear extension diagrams, and give a limit law result for the average number of local decreases.
Periodic Pólya Urns and an Application to Young Tableaux (Extended abstract)

Cyril Banderier, Philippe Marchal, Michael Wallner

29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018), Uppsala, 2018

www arXiv

Extended abstract. Periodic Pólya urns with time-modular replacement; $D$-finite moment generating functions; generalized Gamma distributions.

Pólya urns are urns where at each unit of time a ball is drawn and is replaced with some other balls according to its colour. We introduce a more general model: The replacement rule depends on the colour of the drawn ball and the value of the time mod p. We discuss some intriguing properties of the differential operators associated to the generating functions encoding the evolution of these urns. The initial non-linear partial differential equation indeed leads to linear differential equations and we prove that the moment generating functions are D-finite. For a subclass, we exhibit a closed form for the corresponding generating functions (giving the exact state of the urns at time n). When the time goes to infinity, we show that these periodic Pólya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions. En passant, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux: This approach allows us to prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions.
Divisibility of binomial coefficients by powers of two

Lukas Spiegelhofer, Michael Wallner

Journal of Number Theory, 192, pp. 221–239, 2018

www arXiv

The family $j \mapsto \Theta(j,n)$ (Pascal's triangle entries not divisible by $2^{j+1}$) usually follows a normal distribution.

For nonnegative integers $j$ and $n$ let $\Theta(j,n)$ be the number of entries in the $n$-th row of Pascal's triangle that are not divisible by $2^{j+1}$. In this paper we prove that the family $j\mapsto\Theta(j,n)$ usually follows a normal distribution. The method used for proving this theorem involves the computation of first and second moments of $\Theta(j,n)$, and uses asymptotic analysis of multivariate generating functions by complex analytic methods, building on earlier work by Drmota (1994) and Drmota, Kauers and Spiegelhofer (2016).
On the shape of random Pólya structures

Bernhard Gittenberger, Emma Yu Jin, Michael Wallner

Discrete Mathematics, 341(4), pp. 896–911, 2018

www arXiv

Uniform random Pólya trees consist of a conditioned Galton-Watson tree and forests of size $\Theta(\log n)$; combinatorial interpretation of forest weights via automorphisms.

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 $n$ consists of a conditioned critical Galton-Watson tree $C_n$ and many small forests, where with probability tending to one, as $n$ tends to infinity, any forest $F_n(v)$, that is attached to a node $v$ in $C_n$, is maximally of size $\vert F_n(v)\vert=O(\log n)$. Their proof used the framework of a Boltzmann sampler and deviation inequalities. In this paper, first, we employ a unified framework in analytic combinatorics to prove this fact with additional improvements for $\vert F_n(v)\vert$, namely $\vert F_n(v)\vert=\Theta(\log n)$. Second, we give a combinatorial interpretation of the rational weights of these forests and the defining substitution process in terms of automorphisms associated to a given Pólya tree. Third, we derive the limit probability that for a random node $v$ the attached forest $F_n(v)$ is of a given size. Moreover, structural properties of those forests like the number of their components are studied. Finally, we extend all results to other Pólya structures.

2017

A note on the scaling limits of random Pólya trees (Extended abstract)

Bernhard Gittenberger, Emma Yu Jin, Michael Wallner

Fourteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2017), Barcelona, pp. 85–93, 2017

www arXiv

Extended abstract. Uniform random Pólya trees decompose into a critical Galton-Watson tree and forests of size $\Theta(\log n)$.

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 size $n$ consists of a conditioned critical Galton-Watson tree $C_n$ and many small forests, where with probability tending to one as $n$ tends to infinity, any forest $F_n(v)$, that is attached to a node $v$ in $C_n$, is maximally of size $\vert F_n(v)\vert=O(\log n)$. Their proof used the framework of a Boltzmann sampler and deviation inequalities. In this paper, first, we employ a unified framework in analytic combinatorics to prove this fact with additional improvements on the bound of $\vert F_n(v)\vert$, namely $\vert F_n(v)\vert=\Theta(\log n)$. Second, we give a combinatorial interpretation of the rational weights of these forests and the defining substitution process in terms of automorphisms associated to a given Pólya tree. Third, we derive the limit probability that for a random node $v$ the attached forest $F_n(v)$ is of a given size. Finally, we extend all results to other P\'{o}lya structure.
An explicit generating function arising in counting binomial coefficients divisible by powers of primes

Lukas Spiegelhofer, Michael Wallner

Acta Arithmetica, 181, pp. 27–55, 2017

www arXiv

Generating functions for the polynomials $P_j$ counting binomial coefficients divisible by $p^j$; efficient computation via recurrence relations.

For a prime $p$ and nonnegative integers $j$ and $n$ let $\vartheta_p(j,n)$ be the number of entries in the $n$-th row of Pascal's triangle that are exactly divisible by $p^j$. Moreover, for a finite sequence $w=(w_{r-1}\cdots w_0)\neq (0,\ldots,0)$ in $\{0,\ldots,p-1\}$ we denote by $\lvert n\rvert_w$ the number of times that $w$ appears as a factor (contiguous subsequence) of the base-$p$ expansion $n=(n_{\mu-1}\cdots n_0)_p$ of $n$. It follows from the work of Barat and Grabner (Distribution of binomial coefficients and digital functions, J. London Math. Soc. (2) 64(3), 2001), that $\vartheta_p(j,n)/\vartheta_p(0,n)$ is given by a polynomial $P_j$ in the variables $X_w$, where $w$ are certain finite words in $\{0,\ldots,p-1\}$, and each variable $X_w$ is set to $\lvert n\rvert_w$. This was later made explicit by Rowland (The number of nonzero binomial coefficients modulo $p^\alpha$, J. Comb. Number Theory 3(1), 2011), independently from Barat and Grabner's work, and Rowland described and implemented an algorithm computing these polynomials $P_j$. In this paper, we express the coefficients of $P_j$ using generating functions, and we prove that these generating functions can be determined explicitly by means of a recurrence relation. Moreover, we prove that $P_j$ is uniquely determined, and we note that the proof of our main theorem also provides a new proof of its existence. Besides providing insight into the structure of the polynomials $P_j$, our results allow us to compute them in a very efficient way.
Lattice paths with catastrophes

Cyril Banderier, Michael Wallner

Discrete Mathematics & Theoretical Computer Science, 19(1), 2017

www arXiv zbMATH

Lattice paths with resets-to-zero: bijections, continued fractions, enumeration and limit laws via kernel method and analytic combinatorics.

In queuing theory, it is usual to have some models with a "reset" of the queue. In terms of lattice paths, it is similar to having the possibility of jumping from any altitude to zero. These objects have the interesting feature: They do not have the same intuitive probabilistic behaviour as classical Dyck paths (the typical properties of which are strongly related to Brownian motion theory). This article quantifies some relations between these two types of paths. We give a bijection with some other lattice paths and we make a connection with a continued fraction expansion. Furthermore, we prove several formulae for related combinatorial structures conjectured in the On-Line Encyclopedia of Integer Sequences. We use the kernel method and other tools from analytic combinatorics in order to provide the enumeration and limit laws of these lattice paths with catastrophes for all finite sets of jumps. We conclude by providing an algorithm which generates such lattice paths uniformly at random.
Lattice paths with catastrophes (Extended abstract)

Cyril Banderier, Michael Wallner

Electronic Notes in Discrete Mathematics, 59 (GAScom 2016 proceedings), pp. 131–146, 2017

www

Extended abstract. Queue resets modeled as jumps to zero; kernel method for enumeration and limit laws of catastrophe paths.

In queuing theory, it is usual to have some models with a "reset" of the queue. In terms of lattice paths, it is like having the possibility of jumping from any altitude to zero. These objects have the interesting feature that they do not have the same intuitive probabilistic behavior like classical Dyck paths (the typical properties of which are strongly related to Brownian motion theory), and this article quantifies some relations between these two types of paths. We give a bijection with some other lattice paths and a link with a continuous fraction expansion, and prove several formulae for related combinatorial structures conjectured in the On-line Encyclopedia of Integer Sequences. Thanks to the kernel method and via analytic combinatorics, we derive the enumeration and limit laws of these "lattice paths with catastrophes", for any finite set of jumps.

2016

A half-normal distribution scheme for generating functions and the unexpected behavior of Motzkin paths (Extended abstract)

Michael Wallner

27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2016), Kraków, 2016

www arXiv

Extended abstract. Extension of the Drmota-Soria theorem: conditions on bivariate generating functions implying half-normal limit distributions.

We present an extension of a theorem by Michael Drmota and Michele Soria [Images and Preimages in Random Mappings, 1997] that can be used to identify the limiting distribution for a class of combinatorial schemata. This is achieved by determining analytical and algebraic properties of the associated bivariate generating function. We give sufficient conditions implying a half-normal limiting distribution, extending the known conditions leading to either a Rayleigh, a Gaussian, or a convolution of the last two distributions. We conclude with three natural appearances of such a limiting distribution in the domain of Motzkin paths.
The reflection-absorption model for directed lattice paths (Extended abstract)

Cyril Banderier, Michael Wallner

VIENNA young SCIENTISTS SYMPOSIUM (VSS 2016), Vienna, pp. 98–99, 2016

www Poster

Extended abstract. Kernel method for lattice paths with altitude-dependent steps (reflecting or absorbing at $y=0$); new critical compositions arise, and the drift at zero plays a key role distinct from the global drift.

In this abstract we analyze directed lattice paths, when a boundary reflecting or absorbing condition is added to the classical models. The lattice paths are characterized by two time-independent sets of rules (also called steps) which have a privileged direction of increase. Depending on the spatial coordinate, one of the two sets of rules applies, namely one for altitude 0 and one for altitude bigger than 0. The abscissa y = 0 thus acts as a border which either absorbs or reflects steps. The absorption model extends the model analyzed by Banderier and Flajolet [Basic analytic combinatorics of directed lattice paths, 2002], while the reflection model leads to a more complicated situation. More details are given in [Some reflections on lattice paths, 2014].

2015

Lattice paths of slope 2/5 (Extended abstract)

Cyril Banderier, Michael Wallner

Fourteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2015), San Diego, pp. 105–113, 2015

www arXiv

Extended abstract. Dyck paths under $y = 2x/5$: Knuth's problem solved via kernel method with algebraic generating functions.

We analyze some enumerative and asymptotic properties of Dyck paths under a line of slope 2/5.This answers to Knuth's problem #4 from his "Flajolet lecture" during the conference "Analysis of Algorithms" (AofA'2014) in Paris in June 2014.Our approach relies on the work of Banderier and Flajolet for asymptotics and enumeration of directed lattice paths. A key ingredient in the proof is the generalization of an old trick of Knuth himself (for enumerating permutations sortable by a stack),promoted by Flajolet and others as the "kernel method". All the corresponding generating functions are algebraic,and they offer some new combinatorial identities, which can be also tackled in the A=B spirit of Wilf--Zeilberger--Petkov{\v s}ek.We show how to obtain similar results for other slopes than 2/5, an interesting case being e.g. Dyck paths below the slope 2/3, which corresponds to the so called Duchon's club model.

2014

Some reflections on directed lattice paths

Cyril Banderier, Michael Wallner

25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2014), Paris, pp. 25–36, 2014

arXiv HAL

Directed lattice paths with reflecting/absorbing boundaries; kernel method modifications; asymptotics for excursions, arches, meanders.

This article analyzes directed lattice paths, when a boundary reflecting or absorbing condition is added to the classical models. The lattice paths are characterized by two time-independent sets of rules (also called steps) which have a privileged direction of increase and are therefore essentially one-dimensional objects. Depending on the spatial coordinate, one of the two sets of rules applies, namely one for altitude 0 and one for altitude bigger than 0. The abscissa y=0 thus acts as a border which either absorbs or reflects steps. The absorption model corresponds to the model analyzed by Banderier and Flajolet ("Analytic combinatorics of directed lattice paths"), while the reflecting model leads to a more complicated situation. We show how the generating functions are then modified: the kernel method strikes again but here it unfortunately does not give a nice product formula. This makes the analysis more challenging, and, in the case of Lukasiewicz walks, we give the asymptotics for the number of excursions, arches and meanders. Limit laws for the number of returns to 0 of excursions are given. We also compute the limit laws of the final altitude of meanders. The full analytic situation is more complicated than the Banderier-Flajolet model (partly because new "critical compositions" appear, forcing us to introduce new key quantities, like the drift at 0), and we quantify to what extent the global drift, and the drift at 0 play a role in the "universal" behavior of such walks.

► Lattice Paths (13)

A bijection between stacked directed polyominoes and Motzkin paths with alternative catastrophes

Florian Schager, Michael Wallner

GASCom 2024, 2024

www arXiv zbMATH

Novel bijection between stacked directed polyominoes and Motzkin paths with alternative catastrophes.

We present a novel bijection between stacked directed polyominoes and Motzkin paths with alternative catastrophes. Further, we show how this new connection can be used in order to obtain a better understanding of certain parameters of stacked directed animals.
Bijections and congruences involving lattice paths and integer compositions

Manosij Ghosh Dastidar, Michael Wallner

Submitted

arXiv zbMATH

New bijections explain the counting formula $4^{n-1}$ for Dyck paths and integer compositions; connections to mock theta functions and Fibonacci numbers.

We prove new bijections between different variants of Dyck paths and integer compositions, which give combinatorial explanations of their simple counting formula $4^{n−1}$. These give relations between different statistics, such as the number of crossings of the x-axis in classes of Dyck bridges or the distribution of peaks in classes of Dyck paths, and furthermore relate them with k- and g-compositions. These allow us to find and prove congruence results for Dyck paths and parity results for compositions. Our investigation uncovers unexpected connections to mock theta functions, Hardinian arrays, little Schröder paths, Fibonacci numbers, and irreducible pairs of compositions, offering new insights into the structures of paths, partitions and compositions.

↳

Bijections between variants of Dyck paths and integer compositions (Extended abstract)

GASCom 2024, 2024

www arXiv zbMATH

Extended abstract. Bijective results between Dyck path variants and integer compositions enumerated by $4^{n-1}$; congruence relationships.

We give bijective results between several variants of lattice paths and integer compositions all enumerated by the seemingly innocuous formula $4^{n-1}$. These associations lead us to make more connections between the two constructs such as congruence results.

Dyck paths and inversion tables

Michael Wallner

Permutation Patterns 2023, pp. 142–144, 2023

www

Inversion tables generalized to boxed Dyck paths; bijections with increasing Cayley trees, binary trees, and relaxed binary trees.

We generalize inversion tables, which are in bijection with permutations, to boxed Dyck paths, where the number of markers in each row depends on a path that may differ from the staircase path. We demonstrate that subclasses of this family correspond to various combinatorial objects, including increasing Cayley trees, increasing binary trees, and relaxed binary trees. Moreover, we discuss the relationship between the path and the markers and enumerate some of the aforementioned subclasses.
On the critical exponents of generalized ballot sequences in three dimensions and large tandem walks

Michael Wallner

Aequationes Mathematicae, 96, pp. 815–826, 2022

www arXiv zbMATH

Ballot walk models are not $D$-finite; tandem walks generalized bijectively to ballot walks in three dimensions.

We answer some questions on the asymptotics of ballot walks raised in [Personal Journal Shalosh B Ekhad and Doron Zeilberger, Apr 5, 2021; see also arXiv:2104.01731] and prove that these models are not D-finite. This short note demonstrates how the powerful tools developed in the last decades on lattice paths in convex cones help us to answer some challenging problems that were out of reach for a long time. On the way we generalize tandem walks to the family of large tandem walks whose steps are of arbitrary length and map them bijectively to a generalization of ballot walks in three dimensions.
Walks avoiding a quadrant and the reflection principle

Mireille Bousquet-Mélou, Michael Wallner

European Journal of Combinatorics, 103803, 2023

www arXiv Maple Slides zbMATH

Generating function for king walks avoiding the negative quadrant: D-finite series plus algebraic component; algebraicity for Weyl step sets.

We continue the enumeration of plane lattice walks with small steps avoiding the negative quadrant, initiated by the first author in 2016. We solve in detail a new case, namely the king model where all eight nearest neighbour steps are allowed. The associated generating function is proved to be the sum of a simple, explicit D-finite series (related to the number of walks confined to the first quadrant), and an algebraic one. This was already the case for the two models solved by the first author in 2016. The principle of the approach is also the same, but challenging theoretical and computational difficulties arise as we now handle algebraic series of larger degree. We expect a similar algebraicity phenomenon to hold for the seven Weyl step sets, which are those for which walks confined to the first quadrant can be counted using the reflection principle. With this paper, this is now proved for three of them. For the remaining four, we predict the D-finite part of the solution, and in three of the four cases, give evidence for the algebraicity of the remaining part.

↳

More Models of Walks Avoiding a Quadrant (Extended abstract)

31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), 2020

www arXiv Video zbMATH

Extended abstract. King walks avoiding the negative quadrant: D-finite plus algebraic generating function decomposition.

We continue the enumeration of plane lattice paths avoiding the negative quadrant initiated by the first author in [Bousquet-Mélou 2016]. We solve in detail a new case, where all 8 nearest neighbour steps are allowed. As in the two cases solved in [Bousquet-Mélou 2016], the associated generating function is proved to differ from a simple, explicit D-finite series (related to the enumeration of walks confined to the first quadrant) by an algebraic one. The principle of the approach is the same as in [Bousquet-Mélou 2016], but challenging theoretical and computational difficulties arise as we now handle algebraic series of larger degree. We also explain why we expect the observed algebraicity phenomenon to persist for 4 more models, for which the quadrant problem is solvable using the reflection principle.

Latticepathology and Symmetric Functions

Cyril Banderier, Marie-Louise Lackner, Michael Wallner

31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), 2020

www Poster

Prime walks as natural structures for excursion decompositions; bivariate Spitzer/Wiener-Hopf formulas for lattice paths.

We revisit and extend a list of formulas based on lattice path surgery: cut-and-paste methods, factorizations, the kernel method, etc. For this purpose, we focus on the natural model of directed lattice paths (also called generalized Dyck paths). We introduce the notion of prime walks, which appear to be the key structure to get natural decompositions of excursions, meanders, bridges, directly leading to the associated context-free grammars. This allows us to give bijective proofs of bivariate versions of Spitzer/Sparre Andersen/Wiener--Hopf formulas, paving the way for many joint distribution studies. We also show that each of the fundamental families of symmetric polynomials correspond to a lattice path generating function, and that these symmetric polynomials are accordingly needed to express the asymptotic enumeration of these paths and some parameters of limit laws. En passant, we give two other small results which have their own interest for folklore conjectures of lattice paths (non-analyticity of the small roots in the kernel method, and universal positivity of the variability condition occurring in many Gaussian limit law schemes).
Combinatorics of nondeterministic walks

Élie de Panafieu, Michael Wallner

Submitted

arXiv Maple Git Slides

Nondeterministic bridges, excursions, and meanders with Dyck/Motzkin steps are algebraic; reachable endpoint sets; Python and Maple packages.

This paper introduces nondeterministic walks, a new variant of one-dimensional discrete walks. The main difference to classical walks is that its nondeterministic steps consist of sets of steps from a predefined set such that all possible extensions are explored in parallel. We discuss in detail the most natural nondeterministic step sets (Dyck and Motzkin step sets), and show that several nondeterministic classes of lattice paths, such as nondeterministic bridges, excursions, and meanders are algebraic. The key concept is the generalization of the ending point of a walk to its reachable points, i.e., a set of ending points. We extend our results to general step sets: We show that nondeterministic bridges and several subclasses of nondeterministic meanders are always algebraic. We conjecture the same is true for nondeterministic excursions, and we present python and Maple packages to support our conjecture. This research is motivated by the study of networks involving encapsulation and decapsulation of protocols. Our results are obtained using generating functions, analytic combinatorics, and additive combinatorics.

↳

De la probabilité de creuser un tunnel (French abstract)

AlgoTel 2019, Saint Laurent de la Cabrerisse, 2019

HAL

Feasibility probability of protocol paths with nested encapsulations/decapsulations computed via Dyck and Motzkin path generating functions (French-language abstract).

Un tunnel est une portion d'un chemin où un protocole de communication est encapsulé dans un autre. Les tunnels sont de plus en plus présents dans les réseaux. Ils sont utilisés pour la sécurité, l'interopérabilité, les réseaux virtuels, etc. Un chemin contenant un tunnel doit ^etre faisable, c'est-à-dire qu'il doit respecter l'ordre des encapsulations et des désencapsulations, parfois imbriquées. Les algorithmes de calcul de chemins avec prise en compte de tunnels ne sont pas les m^emes que dans un réseau classique. Afin de tester ces algorithmes, il serait utile de disposer d'un générateur de topologies aléatoires avec tunnels. Ce générateur devra produire des topologies ayant certaines caractéristiques (par exemple, que la probabilité qu'un chemin soit faisable soit un paramètre p quelconque). Il se trouve que ce problème est lié aux chemins de Dyck et de Motzkin en combinatoire. En effet, une encapsulation peut ^etre vue comme un pas montant et une désencapsulation peut ^etre vue comme un pas descendant. La question qui se pose est donc de savoir quelle est la probabilité qu'un chemin de Dyck ou de Motzkin ait certaines propriétés. Dans ce travail, en utilisant des outils de combinatoire analytique, nous donnons la probabilité qu'un chemin soit faisable en fonction de la distribution des encapsulations et des désencapsulations sur les sommets.
↳

Combinatorics of nondeterministic walks of the Dyck and Motzkin type (Extended abstract)

Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2019), San Diego, 2019

www arXiv

Generating functions for nondeterministic Dyck/Motzkin walks (bridges, meanders, excursions); motivated by protocol encapsulation.

This paper introduces nondeterministic walks, a new variant of one-dimensional discrete walks. At each step, a nondeterministic walk draws a random set of steps from a predefined set of sets and explores all possible extensions in parallel. We introduce our new model on Dyck steps with the nondeterministic step set $\{ \{-1\}, \{1\}, \{-1,1\}\}$ and Motzkin steps with the nondeterministic step set $\{\{-1\}, \{0\}, \{1\}, \{-1,0\}, \{-1,1\}, \{0,1\}, \{-1,0,1\}\}$. For general lists of step sets and a given length, we express the generating function of nondeterministic walks where at least one of the walks explored in parallel is a bridge (ends at the origin). In the particular cases of Dyck and Motzkin steps, we also compute the asymptotic probability that at least one of those parallel walks is a meander (stays nonnegative) or an excursion (stays nonnegative and ends at the origin). This research is motivated by the study of networks involving encapsulations and decapsulations of protocols. Our results are obtained using generating functions and analytic combinatorics.

Local time for lattice paths and the associated limit laws

Cyril Banderier, Michael Wallner

GAScom 2018, Athens, 2018

www arXiv

Local time at zero for generalized Dyck paths; geometric, negative binomial, Rayleigh, and half-normal limit laws depending on drift and walk type.

For generalized Dyck paths (i.e., directed lattice paths with any finite set of jumps), we analyse their local time at zero (i.e., the number of times the path is touching or crossing the abscissa). As we are in a discrete setting, the event we analyse here is "invisible" to the tools of Brownian motion theory. It is interesting that the key tool for analysing directed lattice paths, which is the kernel method, is not directly applicable here. Therefore, we introduce a variant of this kernel method to get the trivariate generating function (length, final altitude, local time): this leads to an expression involving symmetric and algebraic functions. We apply this analysis to different types of constrained lattice paths (meanders, excursions, bridges, ...). Then, we illustrate this approach on "basketball walks" which are walks defined by the jumps $\{-2,-1,0,+1,+2\}$. We use singularity analysis to prove that the limit laws for the local time are (depending on the drift and the type of walk) the geometric distribution, the negative binomial distribution, the Rayleigh distribution, or the half-normal distribution (a universal distribution up to now rarely encountered in analytic combinatorics).
Explicit formulas for enumeration of lattice paths: basketball and the kernel method

Cyril Banderier, Christian Krattenthaler, Alan Krinik, Dmitry Kruchinin, Vladimir Kruchinin, David Nguyen, Michael Wallner

Lattice Path Combinatorics and Applications (G. E. Andrews, C. Krattenthaler, A. Krinik, eds.), Developments in Mathematics, Springer-Verlag, Cham, pp. 78–118 , 2019

www arXiv

Kernel method yields explicit nested binomial sum formulas for directed lattice walks with altitude constraints; basketball walks treated in full.

This article deals with the enumeration of directed lattice walks on the integers with any finite set of steps, starting at a given altitude j and ending at a given altitude k, with additional constraints such as, for example, to never attain altitude 0 in-between. We first discuss the case of walks on the integers with steps $-h, \dots, -1, +1, \dots, +h$. The case $h=1$ is equivalent to the classical Dyck paths, for which many ways of getting explicit formulas involving Catalan-like numbers are known. The case $h=2$ corresponds to "basketball walks", which we treat in full detail. Then we move on to the more general case of walks with any finite set of steps, also allowing some weights/probabilities associated with each step. We show how a method of wide applicability, the so-called "kernel method", leads to explicit formulas for the number of walks of length n, for any h, in terms of nested sums of binomials. We finally relate some special cases to other combinatorial problems, or to problems arising in queuing theory.
A half-normal distribution scheme for generating functions

Michael Wallner

European Journal of Combinatorics, 87, 103138, 2020

www arXiv

General theorem: bivariate generating functions under zero drift yield half-normal distributions; applications to returns to zero, height, sign changes.

We present a general theorem on the structure of bivariate generating functions which gives sufficient conditions such that the limiting probability distribution is a half-normal distribution. If $X$ is a normally distributed random variable with zero mean, then $|X|$ obeys a half-normal distribution. In the second part, we apply our result to prove three natural appearances in the domain of lattice paths: the number of returns to zero, the height, and the sign changes are under zero drift distributed according to a half-normal distribution. This extends known results to a general step set. Finally, our result also gives a new proof of Banach's matchbox problem.

↳

A half-normal distribution scheme for generating functions and the unexpected behavior of Motzkin paths (Extended abstract)

27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2016), Kraków, 2016

www arXiv

Extended abstract. Extension of the Drmota-Soria theorem: conditions on bivariate generating functions implying half-normal limit distributions.

We present an extension of a theorem by Michael Drmota and Michele Soria [Images and Preimages in Random Mappings, 1997] that can be used to identify the limiting distribution for a class of combinatorial schemata. This is achieved by determining analytical and algebraic properties of the associated bivariate generating function. We give sufficient conditions implying a half-normal limiting distribution, extending the known conditions leading to either a Rayleigh, a Gaussian, or a convolution of the last two distributions. We conclude with three natural appearances of such a limiting distribution in the domain of Motzkin paths.

Lattice paths with catastrophes

Cyril Banderier, Michael Wallner

Discrete Mathematics & Theoretical Computer Science, 19(1), 2017

www arXiv zbMATH

Lattice paths with resets-to-zero: bijections, continued fractions, enumeration and limit laws via kernel method and analytic combinatorics.

In queuing theory, it is usual to have some models with a "reset" of the queue. In terms of lattice paths, it is similar to having the possibility of jumping from any altitude to zero. These objects have the interesting feature: They do not have the same intuitive probabilistic behaviour as classical Dyck paths (the typical properties of which are strongly related to Brownian motion theory). This article quantifies some relations between these two types of paths. We give a bijection with some other lattice paths and we make a connection with a continued fraction expansion. Furthermore, we prove several formulae for related combinatorial structures conjectured in the On-Line Encyclopedia of Integer Sequences. We use the kernel method and other tools from analytic combinatorics in order to provide the enumeration and limit laws of these lattice paths with catastrophes for all finite sets of jumps. We conclude by providing an algorithm which generates such lattice paths uniformly at random.

↳

Lattice paths with catastrophes (Extended abstract)

Electronic Notes in Discrete Mathematics, 59 (GAScom 2016 proceedings), pp. 131–146, 2017

www

Extended abstract. Queue resets modeled as jumps to zero; kernel method for enumeration and limit laws of catastrophe paths.

In queuing theory, it is usual to have some models with a "reset" of the queue. In terms of lattice paths, it is like having the possibility of jumping from any altitude to zero. These objects have the interesting feature that they do not have the same intuitive probabilistic behavior like classical Dyck paths (the typical properties of which are strongly related to Brownian motion theory), and this article quantifies some relations between these two types of paths. We give a bijection with some other lattice paths and a link with a continuous fraction expansion, and prove several formulae for related combinatorial structures conjectured in the On-line Encyclopedia of Integer Sequences. Thanks to the kernel method and via analytic combinatorics, we derive the enumeration and limit laws of these "lattice paths with catastrophes", for any finite set of jumps.

The kernel method for lattice paths below a line of rational slope

Cyril Banderier, Michael Wallner

Lattice Path Combinatorics and Applications (G. E. Andrews, C. Krattenthaler, A. Krinik, eds.), Developments in Mathematics, Springer-Verlag, Cham, pp. 119–154 , 2019

www arXiv zbMATH

Kernel method extended to multiple dominant singularities for paths below rational slopes; Knuth's problem on paths under $y = 2x/5$ solved.

We analyze some enumerative and asymptotic properties of lattice paths below a line of rational slope. We illustrate our approach with Dyck paths under a line of slope $2/5$. This answers Knuth's problem #4 from his "Flajolet lecture" during the conference "Analysis of Algorithms" (AofA'2014) in Paris in June 2014. Our approach extends the work of Banderier and Flajolet for asymptotics and enumeration of directed lattice paths to the case of generating functions involving several dominant singularities. A key ingredient in the proof is the generalization of an old trick by Knuth himself (for enumerating permutations sortable by a stack), promoted by Flajolet and others as the "kernel method". All the corresponding generating functions are algebraic, and they offer some new combinatorial identities, which can also be tackled in the A=B spirit of Wilf-Zeilberger-Petkovsek. We show how to obtain similar results for other slopes than $2/5$. An interesting case being e.g. Dyck paths below the slope $2/3$, which corresponds to the so called Duchon's club model. We also show how to use our techniques for lattice paths below an irrational slope and illustrate this with Dyck paths below $y=x/\sqrt{2}$.

↳

Lattice paths of slope 2/5 (Extended abstract)

Fourteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2015), San Diego, pp. 105–113, 2015

www arXiv

Extended abstract. Dyck paths under $y = 2x/5$: Knuth's problem solved via kernel method with algebraic generating functions.

We analyze some enumerative and asymptotic properties of Dyck paths under a line of slope 2/5.This answers to Knuth's problem #4 from his "Flajolet lecture" during the conference "Analysis of Algorithms" (AofA'2014) in Paris in June 2014.Our approach relies on the work of Banderier and Flajolet for asymptotics and enumeration of directed lattice paths. A key ingredient in the proof is the generalization of an old trick of Knuth himself (for enumerating permutations sortable by a stack),promoted by Flajolet and others as the "kernel method". All the corresponding generating functions are algebraic,and they offer some new combinatorial identities, which can be also tackled in the A=B spirit of Wilf--Zeilberger--Petkov{\v s}ek.We show how to obtain similar results for other slopes than 2/5, an interesting case being e.g. Dyck paths below the slope 2/3, which corresponds to the so called Duchon's club model.

Some reflections on directed lattice paths

Cyril Banderier, Michael Wallner

25th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2014), Paris, pp. 25–36, 2014

arXiv HAL

Directed lattice paths with reflecting/absorbing boundaries; kernel method modifications; asymptotics for excursions, arches, meanders.

This article analyzes directed lattice paths, when a boundary reflecting or absorbing condition is added to the classical models. The lattice paths are characterized by two time-independent sets of rules (also called steps) which have a privileged direction of increase and are therefore essentially one-dimensional objects. Depending on the spatial coordinate, one of the two sets of rules applies, namely one for altitude 0 and one for altitude bigger than 0. The abscissa y=0 thus acts as a border which either absorbs or reflects steps. The absorption model corresponds to the model analyzed by Banderier and Flajolet ("Analytic combinatorics of directed lattice paths"), while the reflecting model leads to a more complicated situation. We show how the generating functions are then modified: the kernel method strikes again but here it unfortunately does not give a nice product formula. This makes the analysis more challenging, and, in the case of Lukasiewicz walks, we give the asymptotics for the number of excursions, arches and meanders. Limit laws for the number of returns to 0 of excursions are given. We also compute the limit laws of the final altitude of meanders. The full analytic situation is more complicated than the Banderier-Flajolet model (partly because new "critical compositions" appear, forcing us to introduce new key quantities, like the drift at 0), and we quantify to what extent the global drift, and the drift at 0 play a role in the "universal" behavior of such walks.

↳

The reflection-absorption model for directed lattice paths (Extended abstract)

VIENNA young SCIENTISTS SYMPOSIUM (VSS 2016), Vienna, pp. 98–99, 2016

www Poster

Extended abstract. Kernel method for lattice paths with altitude-dependent steps (reflecting or absorbing at $y=0$); new critical compositions arise, and the drift at zero plays a key role distinct from the global drift.

In this abstract we analyze directed lattice paths, when a boundary reflecting or absorbing condition is added to the classical models. The lattice paths are characterized by two time-independent sets of rules (also called steps) which have a privileged direction of increase. Depending on the spatial coordinate, one of the two sets of rules applies, namely one for altitude 0 and one for altitude bigger than 0. The abscissa y = 0 thus acts as a border which either absorbs or reflects steps. The absorption model extends the model analyzed by Banderier and Flajolet [Basic analytic combinatorics of directed lattice paths, 2002], while the reflection model leads to a more complicated situation. More details are given in [Some reflections on lattice paths, 2014].

► DAGs & Compacted Structures (7)

Bivariate asymptotics via random walks: application to large genus maps

Andrew Elvey Price, Wenjie Fang, Baptiste Louf, Michael Wallner

Preprint

arXiv zbMATH

Bivariate asymptotics for unicellular maps as size and genus grow simultaneously, via linear recurrences and complex analysis.

We obtain bivariate asymptotics for the number of (unicellular) combinatorial maps (a model of discrete surfaces) as both the size and the genus grow. This work is related to two research topics that have been very active recently: multivariate asymptotics and large genus geometry. Our method consists of studying a linear recurrence for these numbers, and can be applied to many other linear recurrences. In particular, we include a general theorem that yields asymptotics for such recurrences, provided that some assumptions are satisfied.

↳

Bivariate asymptotics via random walks: application to large genus maps (Extended abstract)

37th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2025), 2025

www arXiv

Extended Abstract. Bivariate asymptotics for unicellular maps as size and genus grow simultaneously, via linear recurrences and complex analysis.

We obtain bivariate asymptotics for the number of (unicellular) combinatorial maps (a model of discrete surfaces) as both the size and the genus grow. This work is related to two research topics that have been very active recently: multivariate asymptotics and large genus geometry. Our method consists in studying a linear recurrence for these numbers, and in fact it can be applied to many other linear recurrences. We discuss briefly the generality of our method and future research directions.

Asymptotics of relaxed k-ary trees

Manosij Ghosh Dastidar, Michael Wallner

35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024), 2024

www arXiv Maple zbMATH

Stretched exponential $e^{c n^{1/3}}$ in the asymptotics of relaxed $k$-ary trees, for all finite arities; recurrences for compacted trees and minimal DFA.

A relaxed $k$-ary tree is an ordered directed acyclic graph with a unique source and sink in which every node has out-degree $k$. These objects arise in the compression of trees in which some repeated subtrees are factored and repeated appearances are replaced by pointers. We prove an asymptotic theta-result for the number of relaxed $k$-ary tree with $n$ nodes for $n \to \infty$. This generalizes the previously proved binary case to arbitrary finite arity, and shows that the seldom observed phenomenon of a stretched exponential term $e^{c n^{1/3}}$ appears in all these cases. We also derive the recurrences for compacted $k$-ary trees in which all subtrees are unique and minimal deterministic finite automata accepting a finite language over a finite alphabet.
The decompressed tree size of k-ary chains

Michael Wallner

Accepted Annals of Combinatorics, 2026

www arXiv zbMATH

Expected decompressed tree size of a $k$-ary chain of size $n$ contains a stretched exponential $e^{c\,\sqrt{n}}$.

A chain is a directed acyclic graph (DAG) with one source and one sink, where the children are ordered and the spanning tree is a path. Such DAGs arise in the compression of trees and are therefore uniquely associated with a tree. The tree size of a DAG is therefore the size of the associated tree. For fixed finite out-degrees, we compute the expected decompressed tree size of a chain of size n chosen uniformly at random, and show that it contains a stretched exponential term of the form $e^{c \, \sqrt{n}}$. The key idea is to use a special generating function that generalizes exponential generating functions and allows the decompressed trees to be constructed symbolically.

↳

The decompressed tree size of k-ary chains (Extended abstract)

European Conference on Combinatorics, Graph Theory and Applications (Eurocomb'25), Budapest, 2025

www

Extended abstract. Stretched exponential $e^{c\sqrt{n}}$ in the expected decompressed tree size of a $k$-ary chain.

A chain is a directed acyclic graph (DAG) with one source and one sink, where the children are ordered and the spanning tree is a path. Such DAGs arise in the compression of trees and are therefore uniquely associated with a tree. The tree size of a DAG is therefore the size of the associated tree. For fixed finite out-degrees, we compute the expected decompressed tree size of a chain of size n chosen uniformly at random, and show that it contains a stretched exponential term of the form $e^{c \, \sqrt{n}}$. The key idea is to use a special generating function that generalizes exponential generating functions and allows the decompressed trees to be constructed symbolically.

Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language

Andrew Elvey Price, Wenjie Fang, Michael Wallner

31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020), 2020

www Maple

Minimal DFAs over a binary alphabet grow as $\Theta\!\left(n!\cdot 4^n\cdot e^{3a_1 n^{1/3}}\cdot n^{7/8}\right)$ where $a_1$ is the largest Airy root.

We show that the number of minimal discrete finite automata with n transient states recognizing a finite binary language grows asymptotically for n to infinity like $$\Theta \left( n! \, 4^n e^{3 a_1 n^{1/3}} n^{7/8} \right),$$ where $a_1 \approx 2.338$ is the largest root of the Airy function. For this purpose, we use a new asymptotic enumeration method proposed by the same authors in a recent preprint (2019). We first derive a new two parameter recurrence relation for the number of such automata up to a given size. Using this result, we prove by induction asymptotically tight bounds that are sufficiently accurate for large n to determine the asymptotic form using adapted Newton polygons.
Compacted binary trees admit a stretched exponential

Andrew Elvey Price, Wenjie Fang, Michael Wallner

Journal of Combinatorial Theory, Series A, 177, 105306, 2021

www arXiv Maple Slides

Compacted binary trees of size $n$ grow like $\Theta\!\left(n!\cdot 4^n\cdot e^{3a_1 n^{1/3}}\cdot n^{3/4}\right)$; quadratic-complexity algorithm via two-parameter recurrence.

A compacted binary tree is a directed acyclic graph encoding a binary tree in which common subtrees are factored and shared, such that they are represented only once. We show that the number of compacted binary trees of size n grows asymptotically like $$\Theta \left( n! \, 4^n e^{3 a_1 n^{1/3}} n^{3/4} \right),$$ where $a_1 \approx 2.338$ is the largest root of the Airy function. Our method involves a new two parameter recurrence which yields an algorithm of quadratic arithmetic complexity. We use empirical methods to estimate the values of all terms defined by the recurrence, then we prove by induction that these estimates are sufficiently accurate for large n to determine the asymptotic form. Our results also lead to new bounds on the number of minimal finite automata recognizing a finite language on a binary alphabet. As a consequence, these also exhibit a stretched exponential.
A bijection of plane increasing trees with relaxed binary trees of right height at most one

Michael Wallner

Theoretical Computer Science, 755, pp. 1–12, 2019

www arXiv

Bijection between plane increasing trees and bounded relaxed binary trees; central limit theorems for leaf statistics; 20+ subclasses enumerated.

Plane increasing trees are rooted labeled trees embedded into the plane such that the sequence of labels is increasing on any branch starting at the root. Relaxed binary trees are a subclass of unlabeled directed acyclic graphs. We construct a bijection between these two combinatorial objects and study the therefrom arising connections of certain parameters. Furthermore, we show central limit theorems for two statistics on leaves. We end the study by considering more than 20 subclasses and their bijective counterparts. Many of these subclasses are enumerated by known counting sequences, and thus enrich their combinatorial interpretation.
Asymptotic Enumeration of Compacted Binary Trees of Bounded Right Height

Antoine Genitrini, Bernhard Gittenberger, Manuel Kauers, Michael Wallner

Journal of Combinatorial Theory, Series A, 172, Article 105177, 2020

www arXiv

Asymptotic counting of compacted trees of bounded right height $k$: growth rates $(4\cos(\pi/(k+3))^2)^n$ with polynomial corrections.

A compacted 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 every subtree is unique. Such representations form a special class of directed acyclic graphs. We are interested in the asymptotic number of compacted trees of given size, where the size of a compacted tree is given by the number of its internal nodes. Due to its superexponential growth this problem poses many difficulties. Therefore we restrict our investigations to compacted trees of bounded right height, which is the maximal number of edges going to the right on any path from the root to a leaf. We solve the asymptotic counting problem for this class as well as a closely related, further simplified class. For this purpose, we develop a calculus on exponential generating functions for compacted trees of bounded right height and for relaxed trees of bounded right height, which differ from compacted trees by dropping the above described uniqueness condition. This enables us to derive a recursively defined sequence of differential equations for the exponential generating functions. The coefficients can then be determined by performing a singularity analysis of the solutions of these differential equations. Our main results are the computation of the asymptotic numbers of relaxed ($r_{k,n}$) as well as compacted trees ($c_{k,n}$) of bounded right height at most $k$ and given size $n$, when the size tends to infinity: \begin{align*} r_{k,n} &\sim \gamma_k n!\left(4 \cos\left(\frac{\pi}{k+3}\right)^2\right)^{n} n^{-\frac{k}{2}} \\ c_{k,n} &\sim \kappa_k n! \left(4 \cos\left(\frac{\pi}{k+3}\right)^2\right)^{n} n^{- \frac{k}{2} - \frac{1}{k+3} - \left(\frac{1}{4} - \frac{1}{k+3}\right)\cos\left(\frac{\pi}{k+3} \right)^{-2}} \end{align*} Here $\gamma_k$ and $\kappa_k$ are nonzero, positive constants which are independent of $n$.

► Composition Schemes & Phase Transitions (2)

Composition schemes: q-enumerations and phase transitions in Gibbs models

Cyril Banderier, Markus Kuba, Stephan Wagner, Michael Wallner

35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024), 2024

www arXiv zbMATH

Phase transitions in $q$-enumeration via composition schemes: Mittag-Leffler, Gaussian, and Boltzmann limit laws depending on the regime.

Composition schemes are ubiquitous in combinatorics, statistical mechanics and probability theory. We give a unifying explanation to various phenomena observed in the combinatorial and statistical physics literature in the context of $q$-enumeration (this is a model where objects with a parameter of value $k$ have a Gibbs measure/Boltzmann weight $q^k$). For structures enumerated by a composition scheme, we prove a phase transition for any parameter having such a Gibbs measure: for a critical value $q=q_c$, the limit law of the parameter is a two-parameter Mittag-Leffler distribution, while it is Gaussian in the supercritical regime ($q>q_c$), and it is a Boltzmann distribution in the subcritical regime ( $0 < q < q_c$). We apply our results to fundamental statistics of lattice paths and quarter-plane walks. We also explain previously observed limit laws for pattern-restricted permutations, and a phenomenon uncovered by Krattenthaler for the wall contacts in watermelons.
Phase transitions of composition schemes: Mittag-Leffler and mixed Poisson distributions

Cyril Banderier, Markus Kuba, Michael Wallner

Annals of Applied Probability, 34(5), pp. 4635–4693, 2024

www arXiv zbMATH

Three-parameter Mittag-Leffler distribution as a universal law; double phase transitions involving Boltzmann and mixed Poisson distributions.

Multitudinous combinatorial structures are counted by generating functions satisfying a composition scheme $$F(z)=G(H(z)).$$ The corresponding asymptotic analysis becomes challenging when this scheme is critical (i.e., $G$ and $H$ are simultaneously singular). The singular exponents appearing in the Puiseux expansions of G and H then dictate the asymptotics. In this work, we first complement results of Flajolet et al. for a full family of singular exponents of $G$ and $H$. We identify the arising limit laws (for the number of $H$-components in $F$) and prove moment convergence. Then, motivated by many examples (random mappings, planar maps, directed lattice paths), we consider a natural extension of this scheme, namely $$F(z)=G(H(z))M(z).$$ We discuss the number of $H$-components of a given size in $F$; this leads to a nice world of limit laws involving products of beta and Mittag-Leffler distributions. We also obtain continuous to discrete phase transitions involving mixed Poisson distributions, giving an unified explanation of the associated thresholds. We end with extensions of the critical composition scheme to a cycle scheme and to the multivariate case, leading again to product distributions. Applications are presented for random walks, trees (supertrees of trees, increasingly labelled trees, preferential attachment trees), triangular Pólya urns, and the Chinese restaurant process.

► Young Tableaux & Pólya Urns (4)

Young tableaux with periodic walls: counting with the density method

Cyril Banderier, Michael Wallner

33rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2021), 2021

www zbMATH

Generalized Young tableaux with periodic walls (Jenga tableaux): algebraic, hypergeometric, $D$-finite, and differentially-algebraic generating functions.

We consider a generalization of Young tableaux in which we allow some consecutive pairs of cells with decreasing labels, conveniently visualized by a "wall" between the corresponding cells. Some shapes can be enumerated by variants of hook-length type formulas. We focus on families of tableaux (like the so-called "Jenga tableaux") having some periodic shapes, for which the generating functions are harder to obtain. We get some interesting new classes of recurrences, and a surprisingly rich zoo of generating functions (algebraic, hypergeometric, D-finite, differentially-algebraic). Some patterns lead to nice bijections with trees, lattice paths, or permutations. Our approach relies on the density method, a powerful way to perform both random generation and enumeration of linear extensions of posets.
Rectangular Young tableaux with local decreases and the density method for uniform random generation

Cyril Banderier, Philippe Marchal, Michael Wallner

GAScom 2018, Athens, 2018

www arXiv

Young tableaux allowing decreasing consecutive pairs; hook-length variants and density method for enumeration and random generation.

In this article, we consider a generalization of Young Tableaux in which we allow some consecutive pairs of cells with decreasing labels. We show that this leads to a rich variety of combinatorial formulas, which suggest that these new objects could be related to deeper structures, similarly to the ubiquitous Young tableaux. Our methods rely on variants of hook-length type formulas, and also on a new efficient generic method (which we call the density method) which allows not only to generate constrained combinatorial objects, but also to enumerate them. We also investigate some repercussions of this method on the D-finiteness of the generating functions of combinatorial objects encoded by linear extension diagrams, and give a limit law result for the average number of local decreases.
Periodic Pólya Urns, the Density Method, and Asymptotics of Young Tableaux

Cyril Banderier, Philippe Marchal, Michael Wallner

Annals of Probability, 48(4), pp. 1921–1965, 2020

www arXiv

Periodic Pólya urns have asymptotic fluctuations described by products of generalized gamma distributions; application to triangular Young tableaux.

Pólya urns are urns where at each unit of time a ball is drawn and replaced with some other balls according to its colour. We introduce a more general model: the replacement rule depends on the colour of the drawn ball and the value of the time (mod p). We extend the work of Flajolet et al. on Pólya urns: the generating function encoding the evolution of the urn is studied by methods of analytic combinatorics. We show that the initial differential equations lead to ordinary linear differential equations which are related to hypergeometric functions (giving the exact state of the urns at time n). When the time goes to infinity, we prove that these periodic Pólya urns have asymptotic fluctuations which are described by a product of generalized gamma distributions. With the additional help of what we call the density method (a method which offers access to enumeration and random generation of poset structures), we prove that the law of the south-east corner of a triangular Young tableau follows asymptotically a product of generalized gamma distributions. This allows us to tackle some questions related to the continuous limit of large random Young tableaux and links with random surfaces.

↳

Periodic Pólya Urns and an Application to Young Tableaux (Extended abstract)

29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018), Uppsala, 2018

www arXiv

Extended abstract. Periodic Pólya urns with time-modular replacement; $D$-finite moment generating functions; generalized Gamma distributions.

Pólya urns are urns where at each unit of time a ball is drawn and is replaced with some other balls according to its colour. We introduce a more general model: The replacement rule depends on the colour of the drawn ball and the value of the time mod p. We discuss some intriguing properties of the differential operators associated to the generating functions encoding the evolution of these urns. The initial non-linear partial differential equation indeed leads to linear differential equations and we prove that the moment generating functions are D-finite. For a subclass, we exhibit a closed form for the corresponding generating functions (giving the exact state of the urns at time n). When the time goes to infinity, we show that these periodic Pólya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions. En passant, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux: This approach allows us to prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions.

On the shape of random Pólya structures

Bernhard Gittenberger, Emma Yu Jin, Michael Wallner

Discrete Mathematics, 341(4), pp. 896–911, 2018

www arXiv

Uniform random Pólya trees consist of a conditioned Galton-Watson tree and forests of size $\Theta(\log n)$; combinatorial interpretation of forest weights via automorphisms.

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 $n$ consists of a conditioned critical Galton-Watson tree $C_n$ and many small forests, where with probability tending to one, as $n$ tends to infinity, any forest $F_n(v)$, that is attached to a node $v$ in $C_n$, is maximally of size $\vert F_n(v)\vert=O(\log n)$. Their proof used the framework of a Boltzmann sampler and deviation inequalities. In this paper, first, we employ a unified framework in analytic combinatorics to prove this fact with additional improvements for $\vert F_n(v)\vert$, namely $\vert F_n(v)\vert=\Theta(\log n)$. Second, we give a combinatorial interpretation of the rational weights of these forests and the defining substitution process in terms of automorphisms associated to a given Pólya tree. Third, we derive the limit probability that for a random node $v$ the attached forest $F_n(v)$ is of a given size. Moreover, structural properties of those forests like the number of their components are studied. Finally, we extend all results to other Pólya structures.

↳

A note on the scaling limits of random Pólya trees (Extended abstract)

Fourteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2017), Barcelona, pp. 85–93, 2017

www arXiv

Extended abstract. Uniform random Pólya trees decompose into a critical Galton-Watson tree and forests of size $\Theta(\log n)$.

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 size $n$ consists of a conditioned critical Galton-Watson tree $C_n$ and many small forests, where with probability tending to one as $n$ tends to infinity, any forest $F_n(v)$, that is attached to a node $v$ in $C_n$, is maximally of size $\vert F_n(v)\vert=O(\log n)$. Their proof used the framework of a Boltzmann sampler and deviation inequalities. In this paper, first, we employ a unified framework in analytic combinatorics to prove this fact with additional improvements on the bound of $\vert F_n(v)\vert$, namely $\vert F_n(v)\vert=\Theta(\log n)$. Second, we give a combinatorial interpretation of the rational weights of these forests and the defining substitution process in terms of automorphisms associated to a given Pólya tree. Third, we derive the limit probability that for a random node $v$ the attached forest $F_n(v)$ is of a given size. Finally, we extend all results to other P\'{o}lya structure.

► Phylogenetic Networks & Biological Combinatorics (3)

A Combinatorial Framework for the Pons-Batle Identity: Young Tableaux, Lattice Paths, and Limit Laws

Hexuan Liu, Guan-Ru Yu, Michael Wallner

Accepted AofA 2026, 2026

Bijections between Pons-Batle words and Young tableaux with walls and holes; Beta and Uniform limit laws.

Tree-child networks model reticulate evolutionary processes. This paper studies bicombining tree-child networks through combinatorial and analytic approaches, using Young tableaux with walls and holes and constructing bijections to Pons-Batle words. We derive algebraic generating functions with differential operators for enumeration formulas and reveal probabilistic structures with Beta and Uniform limit distributions.
Enumerative and Distributional Results for d-combining Tree-Child Networks

Yu-Sheng Chang, Michael Fuchs, Hexuan Liu, Guan-Ru Yu, Michael Wallner

Advances in Applied Mathematics, 157, 102704, 2024

www arXiv Maple zbMATH

Exact formulas and phase transitions (normal, Bessel, Poisson, degenerate) for shape parameters of $d$-combining tree-child networks.

Tree-child networks are one of the most prominent network classes for modeling evolutionary processes which contain reticulation events. Several recent studies have addressed counting questions for {\it bicombining tree-child networks} in which every reticulation node has exactly two parents. We extend these studies to {\it $d$-combining tree-child networks} where every reticulation node has now $d\geq 2$ parents, and we study one-component as well as general tree-child networks. Moreover, we also give results on the distributional behavior of shape parameters (e.g., number of reticulation nodes, Sackin index) of a network which is drawn uniformly at random from the set of all tree-child networks with the same number of leaves. We show phase transitions depending on $d$, leading to normal, Bessel, Poisson, and degenerate distributions. Some of our results are new even in the bicombining case.

↳

Enumeration of d-combining Tree-Child Networks (Extended abstract)

33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022), 2022

www arXiv Maple zbMATH

Extended abstract. Counting and distributional results for $d$-combining tree-child networks with $d\geq 2$ parents per reticulation node.

Tree-child networks are one of the most prominent network classes for modeling evolutionary processes which contain reticulation events. Several recent studies have addressed counting questions for bicombining tree-child networks which are tree-child networks with every reticulation node having exactly two parents. In this paper, we extend these studies to $d$-combining tree-child networks where every reticulation node has now $d\geq 2$ parents. Moreover, we also give results and conjectures on the distributional behavior of the number of reticulation nodes of a network which is drawn uniformly at random from the set of all tree-child networks with the same number of leaves.

Counting and sampling gene family evolutionary histories in the duplication-loss and duplication-loss-transfer models

Cedric Chauve, Yann Ponty, Michael Wallner

Journal of Mathematical Biology, 80(5), pp. 1353–1388, 2020

www arXiv

Formal grammars for gene family histories in the DLT-model; efficient counting and uniform random generation; horizontal transfer dramatically increases the number of histories.

Given a set of species whose evolution is represented by a species tree, a gene family is a group of genes having evolved from a single ancestral gene. A gene family evolves along the branches of a species tree through various mechanisms, including - but not limited to - speciation (S), gene duplication (D), gene loss (L), horizontal gene transfer (T). The reconstruction of a gene tree representing the evolution of a gene family constrained by a species tree is an important problem in phylogenomics. However, unlike in the multispecies coalescent evolutionary model that considers only speciation and incomplete lineage sorting events, very little is known about the search space for gene family histories accounting for gene duplication, gene loss and horizontal gene transfer (the DLT-model). In this work, we introduce the notion of evolutionary histories defined as a binary ordered rooted tree describing the evolution of a gene family, constrained by a species tree in the DLT-model. We provide formal grammars describing the set of all evolutionary histories that are compatible with a given species tree, whether it is ranked or unranked. These grammars allow us, using either analytic combinatorics or dynamic programming, to efficiently compute the number of histories of a given size, and also to generate random histories of a given size under the uniform distribution. We apply these tools to obtain exact asymptotics for the number of gene family histories for two species trees, the rooted caterpillar and the complete binary tree, as well as estimates of the range of the exponential growth factor of the number of histories for random species trees of size up to 25. Our results show that including horizontal gene transfer induce a dramatic increase of the number of evolutionary histories. We also show that, within ranked species trees, the number of evolutionary histories in the DLT-model is almost independent of the species tree topology. These results establish firm foundations for the development of ensemble methods for the prediction of reconciliations.

► Number Theory & Digital Functions (4)

The binary digits of n+t

Lukas Spiegelhofer, Michael Wallner

Annali della Scuola Normale Superiore di Pisa, Classe di Scienze, 24(1), pp. 1–31, 2023

www arXiv zbMATH

Cusick's conjecture proved for $t$ with sufficiently many blocks of 1s; Gaussian behavior of $s(n+t)-s(n)$.

The binary sum-of-digits function $s$ counts the number of $\mathtt 1$s in the base-$2$ expansion of a nonnegative integer. T. W. Cusick defined the asymptotic density $$c_t=\lim_{N\rightarrow \infty} \frac 1N \#\{0\leq n \lt N:s(n+t)\geq s(n)\}$$ for integers $t\geq 0$ and conjectured that $c_t>1/2$ for all $t$. We prove that indeed $c_t>1/2$ if the binary expansion of $t$ contains at least $K$ blocks of contiguous $1$s, where $K$ is an absolute, effective constant.
Divisibility of binomial coefficients by powers of two

Lukas Spiegelhofer, Michael Wallner

Journal of Number Theory, 192, pp. 221–239, 2018

www arXiv

The family $j \mapsto \Theta(j,n)$ (Pascal's triangle entries not divisible by $2^{j+1}$) usually follows a normal distribution.

For nonnegative integers $j$ and $n$ let $\Theta(j,n)$ be the number of entries in the $n$-th row of Pascal's triangle that are not divisible by $2^{j+1}$. In this paper we prove that the family $j\mapsto\Theta(j,n)$ usually follows a normal distribution. The method used for proving this theorem involves the computation of first and second moments of $\Theta(j,n)$, and uses asymptotic analysis of multivariate generating functions by complex analytic methods, building on earlier work by Drmota (1994) and Drmota, Kauers and Spiegelhofer (2016).
The Tu-Deng conjecture holds almost surely

Lukas Spiegelhofer, Michael Wallner

The Electronic Journal of Combinatorics, 26(1), Paper 1.28, 28 pp., 2019

www arXiv Maple

The Tu-Deng conjecture on binary Hamming weights holds almost surely as $k\to\infty$.

The Tu-Deng Conjecture is concerned with the sum of digits of $n$ in base $2$ (the Hamming weight $w(n)$ of the binary expansion of $n$) and states the following: assume that $k$ is a positive integer and $0 < t < 2^k-1$. Then $$\left|\left\{ (a,b) \in \{0,...,2^k-2\}^2 : a+b = t \text{ mod } 2^k-1 \text{ and } w(a)+w(b) < k \right\}\right| \leq 2^{k-1}.$$ We prove that the Tu-Deng conjecture holds almost surely in the following sense: the proportion of $t \in [1,2^k-2]$ is such that the above inequality holds approaches one as $k$ tends to infinity. Moreover, we prove that the Tu-Deng conjecture implies a conjecture due to T. W. Cusick concerning the sum of digits of $n$ and $n+t$.
An explicit generating function arising in counting binomial coefficients divisible by powers of primes

Lukas Spiegelhofer, Michael Wallner

Acta Arithmetica, 181, pp. 27–55, 2017

www arXiv

Generating functions for the polynomials $P_j$ counting binomial coefficients divisible by $p^j$; efficient computation via recurrence relations.

For a prime $p$ and nonnegative integers $j$ and $n$ let $\vartheta_p(j,n)$ be the number of entries in the $n$-th row of Pascal's triangle that are exactly divisible by $p^j$. Moreover, for a finite sequence $w=(w_{r-1}\cdots w_0)\neq (0,\ldots,0)$ in $\{0,\ldots,p-1\}$ we denote by $\lvert n\rvert_w$ the number of times that $w$ appears as a factor (contiguous subsequence) of the base-$p$ expansion $n=(n_{\mu-1}\cdots n_0)_p$ of $n$. It follows from the work of Barat and Grabner (Distribution of binomial coefficients and digital functions, J. London Math. Soc. (2) 64(3), 2001), that $\vartheta_p(j,n)/\vartheta_p(0,n)$ is given by a polynomial $P_j$ in the variables $X_w$, where $w$ are certain finite words in $\{0,\ldots,p-1\}$, and each variable $X_w$ is set to $\lvert n\rvert_w$. This was later made explicit by Rowland (The number of nonzero binomial coefficients modulo $p^\alpha$, J. Comb. Number Theory 3(1), 2011), independently from Barat and Grabner's work, and Rowland described and implemented an algorithm computing these polynomials $P_j$. In this paper, we express the coefficients of $P_j$ using generating functions, and we prove that these generating functions can be determined explicitly by means of a recurrence relation. Moreover, we prove that $P_j$ is uniquely determined, and we note that the proof of our main theorem also provides a new proof of its existence. Besides providing insight into the structure of the polynomials $P_j$, our results allow us to compute them in a very efficient way.

Work in Progress

Enumeration of graphs with twin-width 1 – with Bernhard Gittenberger, Zbigniew Gołębiewski, Małgorzata Sulkowska
On beta-reduction of random closed linear lambda terms – with Olivier Bodini, Bernhard Gittenberger, Alexandros Singh, Noam Zeilberger
On the question of parity in integer partitions and Dyck paths – with George Andrews, Manosij Ghosh Dastidar
Critical composition schemes II: stable laws and Boltzmann distributions – with Cyril Banderier, Markus Kuba
Stretched exponentials in Dyck-like recurrence relations – with Andrew Elvey Price, Wenjie Fang
Lattice paths with biased boundary interactions – with Cyril Banderier

Theses

Combinatorial Analysis of Directed Acyclic Graphs, Young Tableaux, and Lattice Paths

Habilitation thesis, TU Wien, 2022
Combinatorics of Lattice Paths and Tree-Like Structures

PhD thesis, TU Wien, 2016 – supervised by Bernhard Gittenberger
Lattice Path Combinatorics

Master's thesis, TU Wien, 2013 – supervised by Michael Drmota
Algebraic Multigrid Methods for Higher-Order Finite Element Discretization with parallelization

Master's thesis, Brunel University, London, 2012 – supervised by Matthias Maischak

Scripts and Lecture Notes

An Invitation to Analytic Combinatorics and Lattice Path Counting

with Marie-Louise Lackner; Lecture notes from a mini-course, ALEA in Europe Young Researchers' Workshop, University of Bath, UK, 2015

News

About

Research interest

Methodology and Recent Results

Broader Applications

Grants & Projects

Collaborators

Students

PhD Students

Master's Students

Publications

2026

2024

2023

2022

2021

2020

2019

2018

2017

2014

2026

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

► Lattice Paths (13)

► DAGs & Compacted Structures (7)

► Composition Schemes & Phase Transitions (2)

► Young Tableaux & Pólya Urns (4)

► Phylogenetic Networks & Biological Combinatorics (3)

► Number Theory & Digital Functions (4)

Work in Progress

Theses

Scripts and Lecture Notes

Presentations

Invited and Contributed Talks

Posters

Teaching

Organization & Service

Popularization & Outreach

Curriculum Vitae