Overpartitions, lattice paths, and Rogers-Ramanujan identities

We extend partition-theoretic work of Andrews, Bressoud, and Burge to overpartitions, defining the notions of successive ranks, generalized Durfee squares, and generalized lattice paths, and then relating these to overpartitions defined by multiplicity conditions on the parts. This leads to many new partition and overpartition identities, and provides a unification of a number of well-known identities of the Rogers-Ramanujan type. Among these are Gordon's generalization of the Rogers-Ramanujan identities, Andrews' generalization of the Göllnitz-Gordon identities, and Lovejoy's “Gordon's theorems for overpartitions.”     

Cumulants, lattice paths, and orthogonal polynomials

A formula expressing free cumulants in terms of Jacobi parameters of the corresponding orthogonal polynomials is derived. It combines Flajolet's theory of continued fractions and the Lagrange inversion formula. For the converse we discuss Gessel–Viennot theory to express Hankel determinants in terms of various cumulants.     

The number of lattice paths below a cyclically shifting boundary

We count the number of lattice paths lying under a cyclically shifting piecewise linear boundary of varying slope. Our main result can be viewed as an extension of well-known enumerative formulae concerning lattice paths dominated by lines of integer slope (e.g. the generalized ballot theorem). Its proof is bijective, involving a classical “reflection” argument. Moreover, a straightforward refinement of our bijection allows for the counting of paths with a specified number of corners. We also show how the result can be applied to give elegant derivations for the number of lattice walks under certain periodic boundaries. In particular, we recover known expressions concerning paths dominated by a line of half-integer slope, and some new and old formulae for paths lying under special “staircases.”     

The genesis of involutions (Polarizations and lattice paths)

The number of Borel orbits in the symmetric space $S{L}_n∕S(G{L}_p\times G{L}_q)$ is analyzed, various (bivariate) generating functions are found. Relations to lattice path combinatorics are explored.     

Partially directed paths in a wedge

The enumeration of lattice paths in wedges poses unique mathematical challenges. These models are not translationally invariant, and the absence of this symmetry complicates both the derivation of a functional equation for the generating function, and solving for it. In this paper we consider a model of partially directed walks from the origin in the square lattice confined to both a symmetric wedge defined by Y=±pX, and an asymmetric wedge defined by the lines Y=pX and Y=0, where p>0 is an integer. We prove that the growth constant for all these models is equal to , independent of the angle of the wedge. We derive function equations for both models, and obtain explicit expressions for the generating functions when p=1. From these we find asymptotic formulas for the number of partially directed paths of length n in a wedge when p=1.The functional equations are solved by a variation of the kernel method, which we call the “iterated kernel method.” This method appears to be similar to the obstinate kernel method used by Bousquet-Mélou (see, for example, references [M. Bousquet-Mélou, Counting walks in the quarter plane, in: Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, Trends Math., Birkhäuser, 2002, pp. 49-67; M. Bousquet-Mélou, Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels, Electron. J. Combin. 9 (2) (2003) R19; M. Bousquet-Mélou, M. Petkovšek, Walks confined in a quadrant are not always D-finite, Theoret. Comput. Sci. 307 (2) (2003) 257-276]). This method requires us to consider iterated compositions of the roots of the kernel. These compositions turn out to be surprisingly tractable, and we are able to find simple explicit expressions for them. However, in spite of this, the generating functions turn out to be similar in form to Jacobi θ-functions, and have natural boundaries on the unit circle.     

Rank and biclique partitions of the complement of paths

The problem was posed of determining the biclique partition number of the complement of a Hamiltonian path (Monson, Rees, and Pullman, Bull. Inst. Combinatorics and Appl. 14 (1995), 17–86). We define the complement of a path P, denoted P , as the complement of P in K_m,n where P is a subgraph of K_m,n for some m and n. We give an exact formula for the biclique partition number of the complement of a path. In particular, we solve the problem posed in [9]. We also summarize our more general results on biclique partitions of the complement of forests. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 111–122, 1998     

Lattice paths and generalized cluster complexes

In this paper we propose a variant of the generalized Schröder paths and generalized Delannoy paths by giving a restriction on the positions of certain steps. This generalization turns out to be reasonable, as attested by the connection with the faces of generalized cluster complexes of types A and B. As a result, we derive Krattenthaler's F-triangles for these two types by a combinatorial approach in terms of lattice paths.     

Limits of areas under lattice paths

We consider sequences of polynomials which count lattice paths by area. In some cases the reversed polynomials approach a formal power series as the length of the paths tend to infinity. We find the limiting series for generalized Schröder, Motzkin, and Catalan paths. The limiting series for Schröder paths and their generalizations are shown to count partitions with restrictions on the multiplicities of odd parts and no restrictions on even parts. The limiting series for generalized Motzkin and Catalan paths are shown to count generalized Frobenius partitions and some related arrays.     

The complexity of computing metric distances between partitions

Quantitative measurement of the similarity of partitions is a problem of particular relevance to the social and behavioral sciences, where experimental procedures necessitate the analysis and comparison of partitions of objects. Since metrics used for this purpose vary considerably in computational complexity. I describe two related metric models that permit methodical enumeration of metrics which may be useful and computationally tractable. Twelve metrics on partitions are identified in this way. Five of them have appeared in the literature, while seven appear to be new. Four of them seem difficult to compute, but efficient algorithms for the remaining eight exist and exhibit time complexities ranging from O(n) to O(n³), where n is the number of objects in the partitions. These algorithms are all based on lattice- and graph-theoretic representations of the computational problems.     

贪婪格点路径的一些性质

设{Xv:v∈Zd}是一族独立同分布的随机变量序列,对Zd上的任意一路径π,定义S(π)=∑v∈πXv,记Mn=maxπ∈Π0(n)S(π),Π0(n)表示从原点出发大小为n的自不相交的路径的全体.论文讨论Mn的性质,得到了类似完全收敛性的结果,即对任意的ε>0,∑∞n=11nPMnn-M>ε<∞.另外还讨论了Xv允许取负值的情形,得到类似的结果,从而推广了Gandolfi和Kesten所研究的贪婪格点路径模型.     

Two-boundary lattice paths and parking functions

We describe an involution on a set of sequences associated with lattice paths with north or east steps constrained to lie between two arbitrary boundaries. This involution yields recursions (from which determinantal formulas can be derived) for the number and area enumerator of such paths. An analogous involution can be defined for parking functions with arbitrary lower and upper bounds. From this involution, we obtained determinantal formulas for the number and sum enumerator of such parking functions. For parking functions, there is an alternate combinatorial inclusion–exclusion approach. The recursions also yield Appell relations. In certain special cases, these Appell relations can be converted into rational or algebraic generating functions.     

The research and progress of the enumeration of lattice paths

The enumeration of lattice paths is an important counting model in enumerative combinatorics. Because it can provide powerful methods and technical support in the study of discrete structural objects in different disciplines, it has attracted much attention and is a hot research field. In this paper, we summarize two kinds of the lattice path counting models that are single lattice paths and family of nonintersecting lattice paths and their applications in terms of the change of dimensions, steps, constrained conditions, the positions of starting and end points, and so on. (1) The progress of classical lattice path such as Dyck lattice is introduced. (2) A method to study the enumeration of lattice paths problem by generating function is introduced. (3) Some methods of studying the enumeration of lattice paths problem by matrix are introduced. (4) The family of lattice paths problem and some counting methods are introduced. (5) Some applications of family of lattice paths in symmetric function theory are introduced, and a related open problem is proposed.     

Counting lattice chains and Delannoy paths in higher dimensions

Lattice chains and Delannoy paths represent two different ways to progress through a lattice. We use elementary combinatorial arguments to derive new expressions for the number of chains and the number of Delannoy paths in a lattice of arbitrary finite dimension. Specifically, fix nonnegative integers n₁,…,n_d, and let L denote the lattice of points (a₁,…,a_d)∈Z^d that satisfy 0≤a_i≤n_i for 1≤i≤d. We prove that the number of chains in L is given by where . We also show that the number of Delannoy paths in L equals Setting n_i=n (for all i) in these expressions yields a new proof of a recent result of Duchi and Sulanke [9] relating the total number of chains to the central Delannoy numbers. We also give a novel derivation of the generating functions for these numbers in arbitrary dimension.     

Integrals, partitions and MacMahon's Theorem

In two previous papers, the study of partitions with short sequences has been developed both for its intrinsic interest and for a variety of applications. The object of this paper is to extend that study in various ways. First, the relationship of partitions with no consecutive integers to a theorem of MacMahon and mock theta functions is explored independently. Secondly, we derive in a succinct manner a relevant definite integral related to the asymptotic enumeration of partitions with short sequences. Finally, we provide the generating function for partitions with no sequences of length K and part exceeding N.     

Enumeration of lattice paths and generating functions for skew plane partitions

n-dimensional lattice paths not touching the hyperplanesX _i–X _i+1=–1,i=1,2,...,n, are counted by four different statistics, one of which is MacMahon's major index. By a reflection-like proof, heavily relying on Zeilberger's (Discrete Math. 44(1983), 325–326) solution of then-candidate ballot problem, determinantal expressions are obtained. As corollaries the generating functions for skew plane partitions, column-strict skew plane partitions, reverse skew plane plane partitions and column-strict reverse skew plane partitions, respectively, are evaluated, thus establishing partly new results, partly new proofs for known theorems in the theory of plane partitions.     

The lattice of integer partitions and its infinite extension

In this paper, we use a simple discrete dynamical model to study integer partitions and their lattice. The set of reachable configurations of the model, with the order induced by the transition rule defined on it, is the lattice of all partitions of a positive integer, equipped with a dominance ordering. We first explain how this lattice can be constructed by an algorithm in linear time with respect to its size by showing that it has a self-similar structure. Then, we define a natural extension of the model to infinity, which we compare with the Young lattice. Using a self-similar tree, we obtain an encoding of the obtained lattice which makes it possible to enumerate easily and efficiently all the partitions of a given integer. This approach also gives a recursive formula for the number of partitions of an integer, and some informations on special sets of partitions, such as length bounded partitions.     

Graphs, partitions and Fibonacci numbers

The Fibonacci number of a graph is the number of independent vertex subsets. In this paper, we investigate trees with large Fibonacci number. In particular, we show that all trees with n edges and Fibonacci number >2^n-1+5 have diameter ?4 and determine the order of these trees with respect to their Fibonacci numbers. Furthermore, it is shown that the average Fibonacci number of a star-like tree (i.e. diameter ?4) is asymptotically for constants A,B as n→∞. This is proved by using a natural correspondence between partitions of integers and star-like trees.     

Exchange relations, Dyck paths and copolymer adsorption

We consider a lattice model of fully directed copolymer adsorption equivalent to the enumeration of vertex-coloured Dyck paths. For two infinite families of periodic colourings we are able to solve the model exactly using a type of symmetry we call an exchange relation. For one of these families we are able to find an asymptotic expression for the location of the critical adsorption point as a function of the period of the colouring. This expression describes the effect of a regular inhomogeneity in the polymer on the adsorption transition.