Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-13T05:13:10.603Z Has data issue: false hasContentIssue false
  • English
  • Français

Area Limit Laws for Symmetry Classes of Staircase Polygons

Published online by Cambridge University Press:  27 January 2010

U. SCHWERDTFEGER,
C. RICHARD and
B. THATTE
U. SCHWERDTFEGER
Affiliation:
Fakultät für Mathematik, Universität Bielefeld, Postfach 10 01 31, 33501 Bielefeld, Germany (e-mail: uschwerd@math.uni-bielefeld.de)
C. RICHARD
Affiliation:
Department für Mathematik, Universität Erlangen–Nürnberg, Bismarckstraße 1 1/2, 91054 Erlangen, Germany (e-mail: richard@mi.uni-erlangen.de)
B. THATTE
Affiliation:
Mathematics and Computer Science Building, University of Canterbury, Private Bag 40800, Christchurch, New Zealand (e-mail: b.thatte@math.canterbury.ac.nz)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We derive area limit laws for the various symmetry classes of staircase polygons on the square lattice, in a uniform ensemble where, for fixed perimeter, each polygon occurs with the same probability. This complements a previous study by Leroux and Rassart, where explicit expressions for the area and perimeter generating functions of these classes have been derived.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 3 , May 2010, pp. 441 - 461
Copyright
Copyright © Cambridge University Press 2010

References

[1]Aldous, D. (1991) The continuum random tree I. Ann. Probab. 19 1–28.CrossRefGoogle Scholar
[2]Aldous, D. (1991) The continuum random tree II: An overview. In Stochastic Analysis, Vol. 167 of London Math. Soc. Lecture Notes, Cambridge University Press, Cambridge, pp. 23–70.CrossRefGoogle Scholar
[3]Aldous, D. (1993) The continuum random tree III. Ann. Probab. 21 248–289.CrossRefGoogle Scholar
[4]Belkin, B. (1972) An invariance principle for conditioned recurrent random walk attracted to a stable law. Z. Wahrscheinlichkeitstheorie Verw. Gebiete 21 45–64.CrossRefGoogle Scholar
[5]Billingsley, P. (1995) Probability and Measure, 3rd edn, Wiley, New York.Google Scholar
[6]Bousquet-Mélou, M. (1996) A method for the enumeration of various classes of column-convex polygons. Discrete Math. 154 1–25.CrossRefGoogle Scholar
[7]Bousquet-Mélou, M. and Viennot, X. G. (1992) Empilements de segments et q-énumération de polyominoes convexes dirigés. J. Combin. Theory Ser. A 60 196–224.CrossRefGoogle Scholar
[8]Chung, K. L. (1974) A Course in Probability Theory, 2nd edn, Academic Press, New York.Google Scholar
[9]Cifarelli, D. M. and Regazzini, E. (1973) Sugli stimatori non distorti a varianza minima di una classe di funzioni di probabilità troncate. Giorn. Econom. Ann. Econom. 32 492–501.Google Scholar
[10]Constantine, G. M. and Savits, T. H. (1996) A multivariate Faà di Bruno formula with applications. Trans. Amer. Math. Soc. 348 503–520.CrossRefGoogle Scholar
[11]Delest, M.-P., Gouyou-Beauchamps, D. and Vauquelin, B. (1987) Enumeration of parallelogram polyominoes with given bond and site perimeter. Graphs Combin. 3 325–339.CrossRefGoogle Scholar
[12]Delest, M.-P. and Viennot, X. G. (1984) Algebraic languages and polyominoes enumeration. Theor. Comput. Sci. 34 169–206.CrossRefGoogle Scholar
[13]Drmota, M. (2004) Stochastic analysis of tree-like data structures. Proc. Royal Soc. London Ser. A 460 271–307.CrossRefGoogle Scholar
[14]Duchon, P. (1999) Q-grammars and wall polyominoes. Ann. Combin. 3 311–321.CrossRefGoogle Scholar
[15]Feller, W. (1970) An Introduction to Probability Theory and its Applications, Vol. II, 2nd edn, Wiley, New York.Google Scholar
[16]Fill, J. A., Flajolet, P. and Kapur, N. (2005) Singularity analysis, Hadamard products, and tree recurrences. J. Comput. Appl. Math. 174 271–313.CrossRefGoogle Scholar
[17]Flajolet, P. and Louchard, G. (2001) Analytic variations on the Airy distribution. Algorithmica 31 361–377.CrossRefGoogle Scholar
[18]Flajolet, P. and Odlyzko, A. M. (1990) Singularity analysis of generating functions. SIAM J. Discrete Math. 3 216–240.CrossRefGoogle Scholar
[19]Flajolet, P., Poblete, P. and Viola, A. (1998) On the analysis of linear probing hashing. Algorithmica 22 37–71.CrossRefGoogle Scholar
[20]Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press, Cambridge.CrossRefGoogle Scholar
[21]Gessel, I. (1980) A noncommutative generalization and q-analog of the Lagrange inversion formula. Trans. Amer. Math. Soc. 257 455–482.Google Scholar
[22]Gittenberger, B. (1999) On the contour of random trees. SIAM J. Discrete Math. 12 434–458.CrossRefGoogle Scholar
[23]Gouyou-Beauchamps, D. and Leroux, P. (2005) Enumeration of symmetry classes of convex polyominoes on the honeycomb lattice. Theor. Comput. Sci. 346 307–334.CrossRefGoogle Scholar
[24]Gutjahr, W. and Pflug, G. C. (1992) The asymptotic contour process of a binary tree is a Brownian excursion. Stochastic Process. Appl. 41 69–89.CrossRefGoogle Scholar
[25]Guttmann, A. J., ed. (2009) Polygons, Polyominoes and Polycubes, Vol. 775 of Lecture Notes in Physics, Springer, Berlin/Heidelberg. pp. 247–299.CrossRefGoogle Scholar
[26]Iglehart, D. L. (1974) Functional central limit theorems for random walks conditioned to stay positive. Ann. Probab. 2 608–619.CrossRefGoogle Scholar
[27]Janson, S. (2007) Brownian excursion area, Wright's constants in graph enumeration, and other Brownian areas. Prob. Surv. 4 80–145.CrossRefGoogle Scholar
[28]Kearney, M. J., Majumdar, S. N. and Martin, R. J. (2007) The first-passage area for drifted Brownian motion and the moments of the Airy distribution. J. Phys. A: Math. Theor. 40 F863–F869.CrossRefGoogle Scholar
[29]Leroux, P. and Rassart, É. (2001) Enumeration of symmetry classes of parallelogram polyominoes. Ann. Sci. Math. Québec 25 71–90.Google Scholar
[30]Leroux, P., Rassart, É. and Robitaille, A. (1998) Enumeration of symmetry classes of convex polyominoes in the square lattice. Adv. Appl. Math. 21 343–380.CrossRefGoogle Scholar
[31]Lin, K. Y. (2007) Rigorous derivation of the radius of gyration generating function for staircase polygons. J. Phys. A: Math. Theor. 40 1419–1426.CrossRefGoogle Scholar
[32]Louchard, G. (1984) The Brownian excursion area: A numerical analysis. Comput. Math. Appl. 10 413–417.CrossRefGoogle Scholar
[33]Louchard, G. (1986) Erratum: ‘The Brownian excursion area: A numerical analysis’. Comput. Math. Appl. 12 375.Google Scholar
[34]Madras, N. and Slade, G. (1993) The Self-Avoiding Walk, Birkhäuser, Boston.Google Scholar
[35]Meir, A. and Moon, J. W. (1978) On the altitude of nodes in random trees. Canad. J. Math. 30 997–1015.CrossRefGoogle Scholar
[36]Nguyễn Thế, M. (2003) Area of Brownian Motion with Generatingfunctionology. In Discrete Random Walks: DRW'03 (Banderier, C. and Krattenthaler, C., eds), Discr. Math. and Theoret. Comput. Sci. Proceedings AC, pp. 229–242.CrossRefGoogle Scholar
[37]Perman, M. and Wellner, J. A. (1996) On the distribution of Brownian areas. Ann. Appl. Probab. 6 1091–1111.CrossRefGoogle Scholar
[38]Prellberg, T. and Brak, R. (1995) Critical exponents from non-linear functional equations for partially directed cluster models. J. Statist. Phys. 78 701–730.CrossRefGoogle Scholar
[39]Revuz, D. and Yor, M. (1998) Continuous Martingales and Brownian Motion, Springer, New York.Google Scholar
[40]Richard, C. (2002) Scaling behaviour of two-dimensional polygon models. J. Statist. Phys. 108 459–493.CrossRefGoogle Scholar
[41]Richard, C. (2006) Staircase polygons: Moments of diagonal lengths and column heights. J. Phys.: Conf. Ser. 42 239–257.Google Scholar
[42]Richard, C. (2009) On q-functional equations and excursion moments. Discrete Math. 309 207–230.CrossRefGoogle Scholar
[43]Richard, C. (2009) Limit distributions and scaling functions. In Polygons, Polyominoes and Polycubes (Guttmann, A. J., ed.), Vol. 775 of Lecture Notes in Physics, Springer, Berlin/Heidelberg, pp. 247–299.CrossRefGoogle Scholar
[44]Richard, C., Guttmann, A. J. and Jensen, I. (2001) Scaling function and universal amplitude combinations for self-avoiding polygons. J. Phys. A: Math. Gen. 34 L495–L501.CrossRefGoogle Scholar
[45]Shepp, L. A. (1982) On the integral of the absolute value of the pinned Wiener process, Ann. Probab. 10 234–239.CrossRefGoogle Scholar
[46]Shepp, L. A. (1991) Acknowledgment of priority: ‘On the integral of the absolute value of the pinned Wiener process’. Ann. Probab. 19 1397.CrossRefGoogle Scholar
[47]Takács, L. (1991) A Bernoulli excursion and its various applications. Adv. Appl. Probab. 23 557–585.CrossRefGoogle Scholar
[48]Takács, L. (1995) Limit distributions for the Bernoulli meander. J. Appl. Probab. 32 375–395.CrossRefGoogle Scholar
[49]Vöge, M. and Guttmann, A. J. (2002) On the number of benzenoid hydrocarbons. J. Chem. Inf. Comput. Sci. 42 456–466.CrossRefGoogle ScholarPubMed