Mathematics – Combinatorics
Scientific paper
2010-11-29
Mathematics
Combinatorics
27 pages, 6 figures
Scientific paper
Prudent walks are special self-avoiding walks that never take a step towards an already occupied site, and \emph{$k$-sided prudent walks} (with $k=1,2,3,4$) are, in essence, only allowed to grow along $k$ directions. Prudent polygons are prudent walks that return to a point adjacent to their starting point. Prudent walks and polygons have been previously enumerated by length and perimeter (Bousquet-M\'elou, Schwerdtfeger; 2010). We consider the enumeration of \emph{prudent polygons} by \emph{area}. For the 3-sided variety, we find that the generating function is expressed in terms of a $q$-hypergeometric function, with an accumulation of poles towards the dominant singularity. This expression reveals an unusual asymptotic structure of the number of polygons of area $n$, where the critical exponent is the transcendental number $\log_23$ and and the amplitude involves tiny oscillations. Based on numerical data, we also expect similar phenomena to occur for 4-sided polygons. The asymptotic methodology involves an original combination of Mellin transform techniques and singularity analysis, which is of potential interest in a number of other asymptotic enumeration problems.
Beaton Nicholas R.
Flajolet Philippe
Guttmann Anthony J.
No associations
LandOfFree
The Enumeration of Prudent Polygons by Area and its Unusual Asymptotics 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 The Enumeration of Prudent Polygons by Area and its Unusual Asymptotics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Enumeration of Prudent Polygons by Area and its Unusual Asymptotics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-220704