scientific article; zbMATH DE number 3390782

MaRDI QIDQ5659554zbMATH OpenFDO

Authors Donald E. Knuth, Stephen Rice, N. G. de Bruijn

Publication date 1972

Mathematics Subject Classification ID

Trees (05C05) Information theory (general) (94A15) Asymptotic results on arithmetic functions (11N37) Fibonacci and Lucas numbers and polynomials and generalizations (11B39)

Cited in

(93)

• The height of two types of generalised Motzkin paths
• Why Delannoy numbers?
• The Sock Problem Revisited
• scientific article; zbMATH DE number 3829270 (Why is no real title available?)
• Mellin transforms and asymptotics: Harmonic sums
• On the stack-size of general tries
• Bijections for a class of labeled plane trees
• Left-to-right maxima in Dyck paths
• The shape of unlabeled rooted random trees
• Retakh's Motzkin paths and some combinatorial comments
• Solution of a problem of Yekutieli and Mandelbrot
• On \({k}\)-Dyck paths with a negative boundary
• Enumeration of partial Łukasiewicz paths
• Asymptotic results on the maximal deviation of simple random walks
• On some problems about ternary paths: a linear algebra approach
• Laws relating runs and steps in gambler's ruin
• Batcher's odd-even exchange revisited: a generating functions approach
• The height of multiple edge plane trees
• Production matrices
• On growing random binary trees
• Two-sided prudent walks: a solvable non-directed model of polymer adsorption
• A bijection between directed column-convex polyominoes and ordered trees of height at most three
• On the recursion depth of special tree traversal algorithms
• The average height of binary trees and other simple trees
• Enumerations of plane trees with multiple edges and Raney lattice paths
• Extreme value statistics of correlated random variables: a pedagogical review
• On \(q\)-functional equations and excursion moments
• On the average number of nodes in a subtree of a tree
• On weighted heights of random trees
• On the average hyperoscillations of planted plane trees
• Random real trees
• Grand Motzkin paths and \(\{0,1,2\}\)-trees -- a simple bijection
• A new interpretation of the Catalan numbers arising in the theory of crystals
• Combinatorial aspects of continued fractions
• The number of maximal independent sets of \((k+1)\)-valent trees
• The combinatorics of N. G. de Bruijn
• Words with a generalized restricted growth property
• Combinatorial aspects of continued fractions. (Reprint)
• Associative spectra of graph algebras. I: Foundations, undirected graphs, antiassociative graphs
• The average height of planted plane trees with M leaves
• The average number of registers needed to evaluate a binary tree optimally
• The number of registers required for evaluating arithmetic expressions
• The number of directed \(k\)-convex polyominoes
• The average height of r-tuply rooted planted plane trees
• A note on a result of R. Kemp on r-tuply rooted planted plane trees
• The joint distribution of first return times and of the number of distinct sites visited by a 1d random walk before returning to the origin
• New equidistributions on plane trees and decompositions of 132-avoiding permutations
• Philippe Flajolet's early work in combinatorics
• Heights of butterfly trees
• The cycle lemma and some applications
• Reinforced weak convergence of stochastic processes
• Patterns in Shi tableaux and Dyck paths
• On exact simulation algorithms for some distributions related to Jacobi theta functions
• Chebyshev polynomials involved in the Householder's method for square roots
• The outer-distance of nodes in random trees
• An analytic approach to the asymptotic variance of trie statistics and related structures
• The average size of ordered binary subgraphs
• Random trees have height \(O(\sqrt{n})\)
• Bounded capacity priority queues
• Permutations generated by token passing in graphs
• Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees
• On the average oscillation of a stack
• The stack-size of tries: A combinatorial study
• Asymptotic analysis of regular sequences
• On the number of deepest nodes in ordered trees
• Simulating theta random variates
• Trees with exponential height dependent weight
• Watermelon uniform random generation with applications
• On a problem of Yekutieli and Mandelbrot about the bifurcation ratio of binary trees
• On the average depth of a prefix of the Dycklanguage \(D_ 1\).
• Progressive and rushed Dyck paths
• The average height of the second highest leaf of a planted plane tree
• Fringe analysis of plane trees related to cutting and pruning
• Analysis of bidirectional ballot sequences and random walks ending in their maximum
• The shape of stretched planar trees
• On the Average Shape of Binary Trees
• Two Bessel bridges conditioned never to collide, double Dirichlet series, and Jacobi theta function
• On the Most Probable Shape of a Search Tree Grown from a Random Permutation
• Deepest nodes in marked ordered trees
• The properties of random trees
• Asymptotics for logical limit laws: When the growth of the components is in an RT class
• Two short proofs of Kemp's identity for rooted plane trees
• An exponential formula for polynomial vector fields. II: Lie series, exponential substitution, and rooted trees
• Trees with power-like height dependent weight
• Protection number in plane trees
• A walk in my lattice path garden
• Some combinatorial matrices and their LU-decomposition
• Height of walks with resets, the Moran model, and the discrete Gumbel distribution
• On the number of combinations without a fixed distance
• Logarithms of a binomial series: A Stirling number approach
• Combinatorics on words and generating Dirichlet series of automatic sequences
• Analytic analysis of algorithms
• A three-way correspondence between partitions

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5659554)