\(Q\)-grammars and wall polyominoes
type: Item
instance of: scholarly article
title: \(Q\)-grammars and wall polyominoes
zbMATH Open document ID: 0939.05025
DOI: 10.1007/BF01608790
author: Philippe Duchon
published in: Annals of Combinatorics
publication date: 1999-10-05T00:00:00Z
review text: A wall polyomino (or bar-graph polygon or solid-on-solid walk) is defined as a vertically convex polyomino in which all columns have their lowest cell at the same level. The upper path of such a polyomino can be bijectively coded with words using letters \(x\), \(y\), \(\overline y\) (corresponding to east, north and south steps). The language of nonempty words coding such polyominoes is algebraic and is generated by an unambiguous grammar. A slightly different grammar corresponds to coding directed positive words. The grammars lead to functional equations for generating functions for the polyominoes. The form of these equations, and some simple singularity computations, are used to prove that the area of wall polyominoes of perimeter \(2n\) has the Airy distribution as a limit law.
Mathematics Subject Classification ID: 05B50
Mathematics Subject Classification ID: 05A16
Mathematics Subject Classification ID: 39B32
Mathematics Subject Classification ID: 82B23
zbMATH DE Number: 1347715
zbMATH Keywords: asymptotic enumeration
zbMATH Keywords: polyomino
zbMATH Keywords: words
zbMATH Keywords: coding
zbMATH Keywords: grammar
zbMATH Keywords: generating functions
reviewed by: E. Keith Lloyd
MaRDI profile type: Publication
cites work: A method for the enumeration of various classes of column-convex polygons
cites work: Attribute grammars are useful for combinatorics
cites work: Enumeriation of parallelogram polyominoes with given bond and site perimeter
cites work: Q3836540
cites work: A new way of counting the column-convex polyominoes by perimeter
cites work: On the analysis of linear probing hashing
cites work: The Brownian excursion area: A numerical analysis
cites work: Kac's formula, levy's local time and brownian excursion
cites work: Exact solution of the discrete \((1+1)\)-dimensional SOS model with field and surface interactions
cites work: Critical exponents from nonlinear functional equations for partially directed cluster models
cites work: Q4283160
cites work: Combinatorial Problems Suggested by the Statistical Mechanics of Domains and of Rubber-Like Molecules
full work available at URL: https://doi.org/10.1007/bf01608790
OpenAlex ID: W2092841585
description: scientific article; zbMATH DE number 1347715