×
Delest, Marie-Pierre; Viennot, Gérard

Algebraic languages and polyominoes enumeration. (English) Zbl 0985.68516

Theor. Comput. Sci. 34, No. 1-2, 169-206 (1984).
Summary: We show the use of algebraic language theory in solving an open problem in combinatorics. By constructing a bijection between convex polyominoes and words of an algebraic language, and by solving the corresponding algebraic system, we prove that the number of convex polyominoes with perimeter \(2n+8\) is \((2n+11)4^n- 4(2n+1)\binom{2n}{n}\).

Cited in 1 Review
Cited in 131 Documents

MSC:

68Q42 Grammars and rewriting systems
05B50 Polyominoes
68R05 Combinatorics in computer science
PDF BibTeX XML Cite
\textit{M.-P. Delest} and \textit{G. Viennot}, Theor. Comput. Sci. 34, 169--206 (1984; Zbl 0985.68516)
Full Text: DOI

Online Encyclopedia of Integer Sequences:

Number of convex polygons of perimeter 2n on square lattice.
Number of convex polygons of length 2n on square lattice whose leftmost bottom vertex is strictly to the left of the rightmost top vertex.
Number of convex polygons of length 2n on square lattice whose leftmost bottom vertex is strictly to the right of the rightmost top vertex.
Number of convex polygons of length 2n on square lattice whose leftmost bottom vertex and rightmost top vertex have the same x-coordinate.

References:

[1] Bender, E.: Convex n-ominoes. Discrete math. 8, 31-40 (1974) · Zbl 0284.05009
[2] Berge, C.; Chen, C. C.; Chvátal, V.; Seow, C. S.: Combinatorial properties of polyominoes. Combinatorica 1, 217-224 (1981) · Zbl 0491.05048
[3] Berstel, J.: Transduction and context-free languages. (1979) · Zbl 0424.68040
[4] Boasson, L.: Langages algébriques, paires itérantes et transductions rationnelles. Theoret. comput. Sci. 2, 209-223 (1976) · Zbl 0378.68037
[5] Chomsky, N.; Schützenberger, M. P.: The algebraic theory of context-free languages. Computer programming and formal systems (1963) · Zbl 0148.00804
[6] Cori, R.: Un code pour LES graphes planaires et ses applications. Astérisque 27 (1975) · Zbl 0313.05115
[7] R. Cori, S. Dulucq and G. Viennot, Shuffle of parenthesis systems and Baxter permutations, J. Combinatorial Theory Serie A., submitted. · Zbl 0662.05004
[8] Cori, R.; Vauquelin, B.: Planar maps are well labeled trees. Canad. J. Math. 33, 1023-1042 (1981) · Zbl 0415.05020
[9] Chaiken, S.; Kleitman, D. J.; Saks, M.; Shearer, J.: Covering regions by rectangles. SIAM J. Discrete and algebraic methods 2, 394-410 (1981) · Zbl 0506.05022
[10] M.-P. Delest, Generating function for column-convex polyominoes, submitted. · Zbl 0736.05030
[11] Eden, M.: A two-dimensional growth process. Proc. 4th Berkeley symp. On mathematical statistics and probability 4, 223-239 (1961) · Zbl 0104.13801
[12] Gessel, J.: A noncommutative generalization and q-analog of the Lagrange inversion formua. Trans. amer. Math. soc. 257, 455-482 (1980) · Zbl 0459.05014
[13] Gessel, I.; Viennot, G.: Binomial determinants, paths and hook lengths formulae. (1983) · Zbl 0579.05004
[14] Ginsburg, S.: The mathematical theory of context-free languages. (1966) · Zbl 0184.28401
[15] Goldman, J.: Formal languages and enumeration. J. combinatorial theory serie A 24, 318-338 (1978) · Zbl 0411.05010
[16] Golomb, S.: Polyominoes. (1965) · Zbl 0143.44202
[17] Gross, M.: Applications géométriques des langages formels. I.C.C. bulletin 5, 141-168 (1961)
[18] Hofbauer, J.; Furlinger, J.: Q-Catalan numbers. (1983)
[19] Klarner, D.: Some results concerning polyominoes. Fibonacci quart 3, 9-20 (1965) · Zbl 0128.24504
[20] Klarner, D.: Cell growth problems. Canad. J. Math. 19, 851-863 (1967) · Zbl 0178.00904
[21] Klarner, D.; Rivest, R.: Asymptotic bounds for the number of convex n-ominoes. Discrete math. 8, 31-40 (1974) · Zbl 0274.05111
[22] Kreweras, G.: Sur LES éventails de segments. Cahiers du B.U.R.O. 15, 1-41 (1970)
[23] Kuich, W.: Enumeration problems and context free languages. Colloquia Mathematica, 729-735 (1975)
[24] Kuich, W.: A context-free language and enumeration problems on infinite trees and diagraphs. J. combinatorial theory 10, 135-142 (1971) · Zbl 0211.02001
[25] Latteux, M.: Cones rationnels commutatifs. J. comput. Systems sci. 18, 307-333 (1979) · Zbl 0421.68074
[26] W. Masek, Personal communication qouted in [9], 1979.
[27] Miyano, S.: Remark on multihead pushdown automata and multihead stack automata. J. comput. System sci. 27, 116-124 (1983) · Zbl 0516.68044
[28] Nivat, M.: Séries formelles algébriques. Séries formelles en variables non commutative et applications, 219-230 (1978)
[29] Ogden, W.: A helpful result for proving inherent ambiguity. Math. syst. Theory 2, 191-194 (1968) · Zbl 0175.27802
[30] Polya, G.: On the number of certain lattice polygons. J. combinatorial theory 6, 102-105 (1969) · Zbl 0327.05010
[31] Read, R. C.: Contributions to the cell growth problem. Canad. J. Math. 14, 1-20 (1962) · Zbl 0105.13510
[32] Rosenberg, A. I.: On multihead finite automata. IBM J. Res. develop. 10, 388-394 (1966) · Zbl 0168.01303
[33] Salomaa, A.; Soittola, M.: Automata-theoretic aspects of formal power series. (1978) · Zbl 0377.68039
[34] Schützenberger, M. P.: Certain elementary families of automata. Proc. symp. On mathematical theory of automata, 139-153 (1962)
[35] Schützenberger, M. P.: Context-free languages and pushdown automata. Information and control 6, 246-264 (1963) · Zbl 0123.12502
[36] L.W. Shapiro and D. Zeilberger, A Markov chain occuring in enzyme kinetics, J. Math. Biology, submitted. · Zbl 0504.92019
[37] Tutte, W. T.: A census of planar maps. Canad. J. Math. 15, 249-271 (1963) · Zbl 0115.17305
[38] Van Leeuwen, J.: Periodic storage schemes with minimum number of memory banks. Proc. ”workshop on graph-theoric concepts in computer science” (1983)
[39] De Chaumont, M. Vauchaussade; Viennot, G.: Enumeration of rnas by complexity. Internat. conf. On medicine and biology (1983) · Zbl 0579.92012
[40] Viennot, G.: Problèmes combinatoires posés par la physique statistique, exposé no. 626. Astérisque (1983/1984)
[41] G. Viennot, Up-down sequence of trees and parallelogram polyominoes, In preparation.
[42] Wright, E. M.: Stacks. Quart. J. Math. Oxford 19, No. 2, 313-320 (1968) · Zbl 0253.05007
[43] Yao, A. C.; Rivest, R. L.: K + 1 heads are better than k. J. assoc. Comput. Mach 25, 337-340 (1980) · Zbl 0372.68017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.