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 1 + root 2, 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-Melou (see, for example, references [M. Bousquet-Melou, Counting walks in the quarter plane, in: Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, Trends Math., Birkhauser,2002, pp. 49-67; M. Bousquet-Melou, Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels, Electron. J. Combin. 9 (2) (2003) R19; M. Bousquet-Melou, M. Petkovsek, Walks confined in a quadrant are not always D-finitc, 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 theta-functions, and have natural boundaries on the unit circle. (C) 2007 Elsevier Inc. All rights reserved.