341 research outputs found
Combinatorics : past and present
No full text13 A4 pages in pdf format.Inaugural address delivered by Prof Helmut Prodinger on 3 May 2006, Stellenbosch University
Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus
No full textThe summatory function of a q-regular sequence in the sense of Allouche and Shallit is analysed asymptotically. The result is a sum of periodic fluctuations multiplied by a scaling factor. Each summand corresponds to an eigenvalues of absolute value larger than the joint spectral radius of the matrices of a linear representation of the sequence. The Fourier coefficients of the fluctuations are expressed in terms of residues of the corresponding Dirichlet generating function. A known pseudo Tauberian argument is extended in order to overcome convergence problems in Mellin-Perron summation.
Two examples are discussed in more detail: The case of sequences defined as the sum of outputs written by a transducer when reading a q-ary expansion of the input and the number of odd entries in the rows of Pascal's rhombus
Counting Ascents in Generalized Dyck Paths
No full textNon-negative Lukasiewicz paths are special two-dimensional lattice paths never passing below their starting altitude which have only one single special type of down step. They are well-known and -studied combinatorial objects, in particular due to their bijective relation to trees with given node degrees.
We study the asymptotic behavior of the number of ascents (i.e., the number of maximal sequences of consecutive up steps) of given length for classical subfamilies of general non-negative Lukasiewicz paths: those with arbitrary ending altitude, those ending on their starting altitude, and a variation thereof. Our results include precise asymptotic expansions for the expected number of such ascents as well as for the corresponding variance
Summations in Bernoulli's triangles via generating functions
No full textCITATION: Oliver, K. & Prodinger, H. 2017. Summations in Bernoulli's triangles via generating functions. Journal of Integer Sequences, 20, Article 17.1.3.The original publication is available at https://cs.uwaterloo.ca/journals/JIS/We revisit sums along straight lines of indices in Bernoulli triangles, and emphasize the use of generating functions as the appropriate tool. This leads to more direct and extended results, compared with a recent paper in this journal.https://cs.uwaterloo.ca/journals/JIS/VOL20/Prodinger/prod22.htmlPublisher's versio
Hypothetical analyses: approximate counting in the style of Knuth, path length in the style of Flajolet
No full textAbstractThe first analysis of approximate counting is due to Flajolet (1985), whereas the first satisfactory analysis of the average path length in digital search trees has been performed by Knuth (1973). Both authors have used the Mellin integral transform, but in rather different ways. It was shown by Kirschenhofer and Prodinger (1991) that both problems are very similar. (This note contains also an “explanation” of this phenomenon.)It is amusing to figure out what Flajolet and Knuth would have done by considering the exchanged problems. The aim of this note is to perform these analyses
Some combinatorial matrices and their LU-decomposition
No full textCITATION: Prodinger, H. 2020. Some combinatorial matrices and their LU-decomposition. Special Matrices, 8:61–67, doi:10.1515/spma-2020-0007.The original publication is available at https://www.degruyter.comThree combinatorial matrices were considered and their LU-decompositions were found. This is typically done by (creative) guessing, and the proofs are more or less routine calculations.Publisher's versio
Visibility problems related to skip lists
No full textCITATION: Prodinger, H. 2018. Visibility problems related to skip lists. Australasian Journal of Combinatorics, 72(3):509–515.The original publication is available at https://ajc.maths.uq.edu.auFor sequences (words) of geometric random variables, visibility problems related to a sun positioned in the north-west are considered. This leads to a skew version of such words. Various parameters are analyzed, such as left-to-right maxima, descents and inversions.Publisher's versio
- …
