Enumeration of Symmetry Classes of Convex Polyominoes in the Square Lattice
✍ Scribed by P. Leroux; E. Rassart; A. Robitaille
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 544 KB
- Volume
- 21
- Category
- Article
- ISSN
- 0196-8858
No coin nor oath required. For personal study only.
✦ Synopsis
This paper concerns the enumeration of rotation-type and congruence-type convex polyominoes on the square lattice. These can be defined as orbits of the Ž groups ᑝ , of rotations, and ᑞ , of symmetries, of the square, acting on transla-4 4 . tion-type polyominoes. By virtue of Burnside's lemma, it is sufficient to enumerate Ž . the various symmetry classes fixed points of polyominoes defined by the elements of ᑝ and ᑞ . Using the Temperley᎐Bousquet-Melou methodology, we solve this 4 4 problem and provide explicit or recursive formulas for their generating functions according to width, height, and area. We also enumerate the class of asymmetric convex polyominoes, using Mobius inversion, and prove that their number is äsymptotically equivalent to the number of convex polyominoes, a fact which is empirically evident. Cet article porte sur l'enumeration de polyominos a rotations et reflexions pres ´´´d ans un reseau carre. Ces polyominos peuvent etre consideres comme des orbites ´´ˆ´d e l'action du groupe diedral ᑞ du carre et de son sous-groupe ᑝ , le groupe des ´4 4 Ž . rotations du carre, sur l'ensemble des polyominos convexes a translations pres . Le ´l emme de Burnside reduit alors le probleme a l'enumeration des ensembles de ´``´Ž . points fixes classes de symetrie de l'action. Utilisant la methodologie de Temper-´ĺey-Bousquet-Melou, nous donnons des formules explicites ou recursives pour les ´śeries generatrices de ces types de polyominos selon la largueur, la hauteur et ´´ĺ 'aire. Nous enumerons aussi, a l'aide de l'inversion de Mobius, la classe des ´´`p olyominos convexes asymetriques et prouvons que ce nombre est asymptotique a ´celui des polyominos convexes, un fait mis en evidence experimentalement. ᮊ ´1998 Academic Press Ž . Ž .
📜 SIMILAR VOLUMES
## Abstract I introduce an effective enumeration of all effective enumerations of classes of r. e. sets and define with this the index set __IE__ of injectively enumerable classes. It is easy to see that this set is ∑~5~ in the Arithmetical Hierarchy and I describe a proof for the ∑~5~‐hardness of
Let G=(V, E) be an undirected graph and C a subset of vertices. If the sets B r (v) 5 C, v ¥ V, are all nonempty and different, where B r (v) denotes the set of all points within distance r from v, we call C an r-identifying code. We give bounds on the best possible density of r-identifying codes in