Walks confined in a quadrant are not always D-finite

Details Walks confined in a quadrant are not always D-finite Walks confined in a quadrant are not always D-finite

2002-11-27

arxiv.org/abs/math/0211432v1

Mathematics

Combinatorics

To appear in Theoret. Comput. Sci. (special issue devoted to random generation of combinatorial objects and bijective combinat

Scientific paper

We consider planar lattice walks that start from a prescribed position, take their steps in a given finite subset of Z^2, and always stay in the quadrant x >= 0, y >= 0. We first give a criterion which guarantees that the length generating function of these walks is D-finite, that is, satisfies a linear differential equation with polynomial coefficients. This criterion applies, among others, to the ordinary square lattice walks. Then, we prove that walks that start from (1,1), take their steps in {(2,-1), (-1,2)} and stay in the first quadrant have a non-D-finite generating function. Our proof relies on a functional equation satisfied by this generating function, and on elementary complex analysis.

Affiliated with

Also associated with

No associations

Rating

Walks confined in a quadrant are not always D-finite does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Walks confined in a quadrant are not always D-finite, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Walks confined in a quadrant are not always D-finite will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-140668