nach oben

Mathematics in Computer Science

Erschienen in:

01.03.2022

A Decomposition of Column-Convex Polyominoes and Two Vertex Statistics

verfasst von: Nenad Cakić, Toufik Mansour, Gökhan Yıldırım

Erschienen in: Mathematics in Computer Science | Ausgabe 1/2022

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We introduce a decomposition method for column-convex polyominoes and enumerate them in terms of two statistics: the number of internal vertices and the number of corners in the boundary. We first find the generating function for the column-convex polyominoes according to the horizontal and vertical half-perimeter, and the number of interior vertices. In particular, we show that the average number of interior vertices over all column-convex polyominoes of perimeter 2n is asymptotic to \(\alpha _o n^{3/2}\) where \(\alpha _o\approx 0.57895563\ldots .\) We also find the generating function for the column-convex polyominoes according to the horizontal and vertical half-perimeter, and the number of corners in the boundary. In particular, we show that the average number of corners over all column-convex polyominoes of perimeter 2n is asymptotic to \(\alpha _1n\) where \(\alpha _1\approx 1.17157287\ldots .\)

Vorheriger Artikel Topological Analysis of Syntactic Structures

Nächster Artikel Localizations of a Ring at Localizable Sets, their Groups of Units and Saturations

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Asakly, W., Blecher, A., Brennan, C., Knopfmacher, A., Mansour, T., Wagner, S.: Set partition asymptotics and a conjecture of Gould and Quaintance. J. Math. Anal. Appl. 416, 672–682 (2014)MathSciNetCrossRefMATH

Banderier, C., Bousquet-Mélou, M., Denise, A., Flajolet, P., Gardy, D., GouyouBeauchamps, D.: Generating functions for generating trees. Discr. Math. 246(1–3), 29–55 (2000)MathSciNetMATH

Barcucci, E., Frosini, A., Rinaldi, S.: In: Brak, R., Foda, O., Greenhill, C., Guttman, T., Owczarek, A. (eds.) Direct-convex polyominoes: ECO method and bijective results. In: Proceedings of Formal Power Series and Algebraic Combinatorics 2002, Melbourne (2002)

Blecher, A., Brennan, C., Knopfmacher, A., Mansour, T.: Counting corners in partitions. Ramanujan J. 39(1), 201–224 (2016)MathSciNetCrossRefMATH

Blecher, A., Brennan, C., Knopfmacher, A.: Peaks in bargraphs. Trans. Royal Soc. S. Afr. 71, 97–103 (2016)CrossRefMATH

Blecher, A., Brennan, C., Knopfmacher, A.: Combinatorial parameters in bargraphs. Quaest. Math. 39, 619–635 (2016)MathSciNetCrossRefMATH

Conway, A.: Enumerating \(2D\) percolation series by the finite-lattice method: theory. J. Phys. A 28(2), 335–349 (1995)MathSciNetCrossRefMATH

Delest, M., Viennot, X.G.: Algebraic languages and polyominoes enumeration. Theoret. Comput. Sci. 34, 169–206 (1984)MathSciNetCrossRefMATH

Del Lungo, A., Mirolli, M., Pinzani, R., Rinaldi, S.: A bijection for directed-convex polyominoes, In: Proceedings of DM-CCG 2001, Discrete Math. Theoret. Comput. Sci. AA (2001) 133–144

10.

Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)CrossRefMATH

11.

Golomb, S.W.: Checker boards and polyominoes. Amer. Math. Monthly 61, 675–682 (1954)MathSciNetCrossRefMATH

12.

Goupil, A., Cloutier, H., Pellerin, M.-E.: Generating functions for inscribed polyominoes. Discrete Appl. Math. 161, 151–166 (2013)MathSciNetCrossRefMATH

13.

Feretić, S., Svrtan, D.: On the number of column-convex polyominoes with given perimeter and number of columns. In: Barlotti, A., Delest, M., Pinzani, R. (eds.) 5th FPSAC Proceedings, pp. 201–214. , Firenze (1993)

14.

Feretić, S.: A perimeter enumeration of column-convex polyominoes. Discrete Math. Theoret. Comput. Sci. 9, 57–84 (2007)MathSciNetMATH

15.

Jensen, I.: Enumerations of lattice animals and trees. J. Stat. Phys. 102(3–4), 865–881 (2001)MathSciNetCrossRefMATH

16.

Jensen, I., Guttmann, A.J.: Statistics of lattice animals (polyominoes) and polygons. J. Phys. A 33(29), 257–263 (2000)MathSciNetCrossRefMATH

17.

Lin, K.Y.: Perimeter generating function for row-convex polygons on the rectangular lattice. J. Phys. A 23, 4703–4705 (1990)MathSciNetCrossRefMATH

18.

Lin, K.Y., Tzeng, W.J.: Perimeter and area generating functions of the staircase and row-convex polygons on the rectangular lattice. Internat. J. Mod. Phys. B 5, 1913–1925 (1991)MathSciNetCrossRef

19.

Louchard, G.: Probabilistic analysis of column-convex and directed diagonally-convex animals. Random Struct. Alg. 11(2), 151–178 (1997)MathSciNetCrossRefMATH

20.

Louchard, G.: Probabilistic analysis of column-convex and directed diagonally-convex animals. II. Trajectories and shapes. Random Struct. Alg. 15(1), 1–23 (1999)

21.

Mansour, T.: Interior vertices in set partitions. Adv. Appl. Math. 101, 60–69 (2018)MathSciNetCrossRefMATH

22.

Mansour, T., Rastegar, R., Shabani, ASh.: On column-convex and convex Carlitz polyominoes. Math. Comput. Sci. 15(4), 889–898 (2021)

23.

Mansour, T., Shabani, ASh.: Interior vertices and edges in bargraphs. Notes Number Theory Discr. Math. 25(2), 181–189 (2019)

24.

Mansour, T., Shabani, ASh., Shattuck, M.: Counting corners in compositions and set partitions presented as bargraphs. J. Diff. Eq. Appl. 24(6), 992–1015 (2018)

25.

Mansour, T., Yildirim, G.: Enumerations of bargraphs with respect to corner statistics. Appl. Anal. Discr. Math. 14, 221–238 (2020)MathSciNetCrossRefMATH

26.

Read, R.C.: Contributions to the cell growth problem. Canadian J. Math., 14, 1-20. https://doi.org/10.4153/CJM-1962-001-2

27.

Temperley, H.N.V.: Combinatorial problems suggested by the statistical mechanics of domains and of rubber-like molecules. Phys. Rev. 103, 1–16 (1956)MathSciNetCrossRefMATH

28.

Viennot, X.G.: A survey of polyominoes enumeration. 4th FPSAC Proc. Publications du LACIM 11, 399–420 (1992)

Titel: A Decomposition of Column-Convex Polyominoes and Two Vertex Statistics
verfasst von: Nenad Cakić
Toufik Mansour
Gökhan Yıldırım
Publikationsdatum: 01.03.2022
Verlag: Springer International Publishing
Erschienen in: Mathematics in Computer Science / Ausgabe 1/2022
Print ISSN: 1661-8270
Elektronische ISSN: 1661-8289
DOI: https://doi.org/10.1007/s11786-022-00528-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2022

Localizations of a Ring at Localizable Sets, their Groups of Units and Saturations

Load Bearing Capacity of Light Timber Frame Walls Under Fire

Topological Analysis of Syntactic Structures

Protected Cells in Compositions

Play-Hysteresis in the Joint Dynamics of Employment and Investment

Symbolic Approach to 2-Orthogonal Polynomial Solutions of a Third Order Differential Equation

Premium Partner