Bijective counting of Kreweras walks and loopless triangulations

Details Bijective counting of Kreweras walks and loopless triangulations Bijective counting of Kreweras walks and loopless triangulations

2006-05-12

arxiv.org/abs/math/0605320v1

Journal of Combinatorial Theory Series A 114, 5 (2007) 931-956

Mathematics

Combinatorics

25 pages

Scientific paper

We consider lattice walks in the plane starting at the origin, remaining in the first quadrant and made of West, South and North-East steps. In 1965, Germain Kreweras discovered a remarkably simple formula giving the number of these walks (with prescribed length and endpoint). Kreweras' proof was very involved and several alternative derivations have been proposed since then. But the elegant simplicity of the counting formula remained unexplained. We give the first purely combinatorial explanation of this formula. Our approach is based on a bijection between Kreweras walks and triangulations with a distinguished spanning tree. We obtain simultaneously a bijective way of counting loopless triangulations.

Affiliated with

Also associated with

No associations

Rating

Bijective counting of Kreweras walks and loopless triangulations 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 Bijective counting of Kreweras walks and loopless triangulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bijective counting of Kreweras walks and loopless triangulations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-596587