Why Delannoy numbers?

This article is not a research paper, but a little note on the history of combinatorics: we present here a tentative short biography of Henri Delannoy, and a survey of his most notable works. This answers the question raised in the title, as these works are related to lattice paths enumeration, to the so-called Delannoy numbers, and were the first general way to solve Ballot-like problems.     

Symmetric Sheffer sequences and their applications to lattice path counting

A sequence of Sheffer polynomials is symmetric, if the value of the nth degree polynomial at any natural number m agrees with the mth degree polynomial at n. While the above property sounds rather esoteric, symmetric Sheffer sequences frequently describe the elegant results of standard lattice path enumeration. We characterize all symmetric Sheffer sequences, and explain their role from the initial value problem point of view. Applications occur in the enumeration of nonintersecting weighted lattice paths, and the discussion of certain correlated random walks.     

Riordan matrices and higher-dimensional lattice walks

An algebraic combinatorial method is used to count higher-dimensional lattice walks in Z^m${\mathbb{Z}}^m$ that are of length n ending at height k. As a consequence of using the method, Sands’ two-dimensional lattice walk counting problem is generalized to higher dimensions. In addition to Sands’ problem, another subclass of higher-dimensional lattice walks is also counted. Catalan type solutions are obtained and the first moments of the walks are computed. The first moments are then used to compute the average heights of the walks. Asymptotic estimates are also given.     

On Some Applications of a Symbolic Representation of Non Centered Lévy Processes

By using a symbolic technique known in the literature as the classical umbral calculus, we characterize two classes of polynomials related to Lévy processes: the Kailath-Segall and the time-space harmonic polynomials. We provide the Kailath-Segall formula in terms of cumulants and we recover simple closed-forms for several families of polynomials with respect to not centered Lévy processes, such as the Hermite polynomials with Brownian motion, Poisson-Charlier polynomials with Poisson processes, actuarial polynomials with Gamma processes, first kind Meixner polynomials with Pascal processes, and Bernoulli, Euler, and Krawtchuk polynomials with suitable random walks.     

Lattice path counting and the theory of queues

In this paper we will show how recent advances in the combinatorics of lattice paths can be applied to solve interesting and nontrivial problems in the theory of queues. The problems we discuss range from classical ones like M^a/M^b/1$M^a/M^b/1$ systems to open tandem systems with and without global blocking and to queueing models that are related to random walks in a quarter plane like the Flatto–Hahn model or systems with preemptive priorities.     

Lattices of lattice paths

We consider posets of lattice paths (endowed with a natural order) and begin the study of such structures. We give an algebraic condition to recognize which ones of these posets are lattices. Next we study the class of Dyck lattices (i.e., lattices of Dyck paths) and give a recursive construction for them. The last section is devoted to the presentation of a couple of open problems.     

Ballot theorem and lattice path crossings

We consider lattice paths which cross the diagonal exactly r times, and by a simple method determine the number of such paths when the endpoint is given. Then as a byproduct we easily obtain Feller's (1968, p.84) result for crossings when the length is given.     

A note on the asymptotics of lattice paths with general boundaries

Lattice paths which are restricted by one or two nonlinear boundaries are of increasing importance in many applications of lattice path combinatorics, for instance in sequential statistics. It is typical for such applications that the number of paths which avoid certain boundaries has to be determined when the number of steps is large. Counting results, if available, and recursion are not very well suited in these cases. In this paper we present some asymptotic approximations which are easy to calculate and provide an accuracy which is sufficient for many practical purposes.     

Jacobi and Laguerre polynomial approximations for the distributions of statistics useful in testing for outliers in exponential and gamma samples

Recently, Sanjel and Balakrishnan [A Laguerre Polynomial Approximation for a goodness-of-fit test for exponential distribution based on progressively censored data, J. Stat. Comput. Simul. 78 (2008), pp. 503–513] proposed the use of Laguerre orthogonal polynomials for a goodness-of-fit test for the exponential distribution based on progressively censored data. In this paper, we use Jacobi and Laguerre orthogonal polynomials in order to obtain density approximants for some test statistics useful in testing for outliers in gamma and exponential samples. We first obtain the exact moments of the statistics and then the density approximants, based on these moments, are expressed in terms of Jacobi and Laguerre polynomials. A comparative study is carried out of the critical values obtained by using the proposed methods to the corresponding results given by Barnett and Lewis [Outliers in Statistical Data, 3rd ed., John Wiley & Sons, New York, 1993]. This reveals that the proposed techniques provide very accurate approximations to the distributions. Finally, we present some numerical examples to illustrate the proposed approximations. Monte Carlo simulations suggest that the proposed approximate densities are very accurate.     

Some robust designs for polynomial regression models

The author identifies static optimal designs for polynomial regression models with or without intercept. His optimality criterion is an average between the D‐optimality criterion for the estimation of low‐degree terms and the D₈‐optimality criterion for testing the significance of higher degree terms. His work relies on classical results concerning canonical moments and the theory of continued fractions.     

A memory reduction method in pricing American options

This paper is concerned with the pricing of American options by simulation methods. In the traditional methods, in order to determine when to exercise, we have to store the simulated asset prices at all time steps on all paths. If N time steps and M paths are used, then the storage requirement is O(MN). In this paper, we present a simulation method for pricing American options where the number of storage required only grows like O(M). The only additional computational cost is that we have to generate each random number twice instead of once. For machines with limited memory, we can now use a larger N to improve the accuracy in pricing the options.     

Visualizing Vandermonde's determinant through nonintersecting lattice paths

We use the Lindström–Gessel–Viennot Theorem to count nonintersecting lattice paths in a carefully chosen acyclic weighted digraph to give a visual combinatorial proof of Vandermonde's classic determinant.     

On three and four vicious walkers

We establish a reflection principle for three lattice walkers and use this principle to reduce the enumeration of configurations of three vicious walkers to the enumeration of configurations of two vicious walkers. More precisely, the reflection principle leads to a bijection between three walks (L₁, L₂, L₃) such that L₂ intersects both L₁ and L₃ and three walks (L₁, L₂, L₃) such that L₁ intersects L₃. Hence we find a combinatorial interpretation of the formula for the generating function for the number of configurations of three vicious walkers, originally derived by Bousquet-Mélou by using the kernel method, and independently by Gessel by using tableaux and symmetric functions. This answers a question posed by Gessel and Bousquet-Mélou. We also find a reflection principle for four vicious walks that leads to a combinatorial interpretation of a formula derived from Gessel's theorem.     

Young bitableaux,lattice paths and Hilbert functions

A recent result on the enumeration of p-tuples of nonintersecting lattice paths in an integral rectangle is used to deduce a formula of Abhyankar for standard Young bitableaux of certain type, which gives the Hilbert function of a class of determinantal ideals. The lattice path formula is also shown to yield the numerator of the Hilbert series of these determinantal ideals and the h-vectors of the associated simplicial complexes. As a consequence, the a-invariant of these determinantal ideals is obtained in some cases, extending an earlier result of Gräbe. Some problems concerning generalizations of these results to ‘higher dimensions’ are also discussed. In an appendix, the equivalence of Abhyankar's formula for unitableaux of a given shape and a formula of Hodge, obtained in connection with his determination of Hilbert functions of Schubert varieties in Grassmannians, is outlined.     

Determinants of (generalised) Catalan numbers

We show that recent determinant evaluations involving Catalan numbers and generalisations thereof have most convenient explanations by combining the Lindström–Gessel–Viennot theorem on non-intersecting lattice paths with a simple determinant lemma from Krattenthaler (1990). This approach leads also naturally to extensions and generalisations.     

An exhaustive analysis of prime modulus multiplicative congruential random number generators with modulus smaller than 215

This paper presents the results of an exhaustive analysis of all of the prime modulus multiplicative congruential random number (RN) generators with moduli smaller than 2¹⁵. In an amount of around 20 million multipliers which are able to produce a full period of RNs, 239 multipliers have a good lattice structure. Among which 52 multipliers further pass a comprehensive battery of empirical tests. These 52 multipliers thus possess good local and global statistical properties. It is worthwhile to note that some empirically tested multipliers recommended in some previous studies are not on this list. The conclusion is that both theoretical and empirical tests are mandatory to sieve out good multipliers. To generate RNs of very long period, many existing techniques can be applied without further effort.     

Lattice paths combinatorics applied to transient queue length distribution of C2/M/1 queues and busy period analysis of bulk queues C2/M/1

This paper aims at deriving explicit transient queue length distribution for GI/M/1 system and busy period analysis of bulk queue GI^b/M/1 through lattice paths (LPs) combinatorics. The general interarrival time distribution is approximated by two-phase Cox distribution, C₂, that has Markovian property, enabling us to represent the processes by two-dimensional LPs. As distributions C₂ cover a wide class of distributions that have rational Laplace–Stieltjes transforms (LSTs) with square coefficient of variation lying in , the results obtained are applicable to a large class of real life situations. Some numerical results for the C₂^b/M/1 model are also given.     

On some probability distributions associated with random walks

The probability distribution of the total number of games to ruin in a gambler's ruin random walk with initial position n, the probability distribution of the total size of an epidemic starting with n cases and the probability distribution of the number of customers served during a busy period M/M/1 when the service starts with n waiting customers are identical. All these can be easily obtained by using Lagrangian expansions instead of long combinatorial methods. The binomial, trinomial, quadrinomial and polynomial random walks of a particle have been considered with an absorbing barrier at 0 when the particle starts its walks from a point n, and the pgfs. and the probability distributions of the total number of jumps (trials) before absorption at 0 have been obtained. The values for the mean and variance of such walks have also been given.     

A statistical analysis of the screening measure of multiple recursive random number generators of orders one and two

This paper presents the results of a comprehensive empirical analysis of the screening measure of multiple recursive generators (MRGs) of orders one and two. Two kinds of screening measures are distinguished: spectral test and lattice test. With regard to these screening measures, two exhaustive searches of the twenty best MRGs of orders one and two are conducted. Some empirical comparisons reveal that the screening procedure with maximum spectral value criterion is preferred in terms of efficiency and thus, is a good way of obtaining ideal MRGs of higher orders. Several extensively tested second-order MRGs are also presented and are therefore recommended.