[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Smooth Column Convex Polyominoes

  • Published:
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

In this paper, we introduce and study several statistics on some families of polyominoes, named smooth column convex polyominoes and lower/upper smooth column convex polyominoes. We find the generating function in each case according to half of the number of horizontal and vertical steps in the boundary of polyominoes. In particular, we show that the number of smooth column convex polyominoes with semi-perimeter n is asymptotic to \(4^{n+4}{\sqrt{3}}/({289\sqrt{\pi n^3}})\), as \(n\rightarrow \infty \). In deriving our results, we solve various types of functional equations that are satisfied by the generating functions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. Banderier, C., Bousquet-Mélou, M., Denise, A., Flajolet, P., Gardy, D., Gouyou-Beauchamps, D.: Generating functions for generating trees. Discrete Math. 246(1–3), 29–55 (2002)

    Article  MathSciNet  Google Scholar 

  2. Barcucci, E., Del Lungo, A., Nivat, M., Pinzani, R.: Reconstructing convex polyominoes from horizontal and vertical projections. Theor. Comput. Sci. 155(2), 321–347 (1996)

    Article  MathSciNet  Google Scholar 

  3. Barcucci, E., Frosini, A., Rinaldi, S.: On directed-convex polyominoes in a rectangle. Discrete Math. 298(1–3), 62–78 (2005)

    Article  MathSciNet  Google Scholar 

  4. Beauquier, D., Nivat, M.: On translating one polyomino to tile the plane. Discrete Comput. Geom. 6(6), 575–592 (1991)

    Article  MathSciNet  Google Scholar 

  5. Beauquier, D., Nivat, M., Remila, É., Robson, M.: Tiling figures of the plane with two bars. Comput. Geom. 5(1), 1–25 (1995)

    Article  MathSciNet  Google Scholar 

  6. Berger, R.: Undecidability of the Domino Problem. Memoirs of the American Mathematical Society, vol. 66. American Mathematical Society, Providence (1966)

  7. Bousquet-Mélou, M., Brak, R.: Exactly solved models. In: Polygons, Polyominoes and Polycubes. Lecture Notes in Physics, vol. 775, pp. 43–78. Springer, Dordrecht (2009)

  8. Bousquet-Mélou, M., Rechnitzer, A.: The site-perimeter of bargraphs. Adv. Appl. Math. 31(1), 86–112 (2003)

    Article  MathSciNet  Google Scholar 

  9. Broadbent, S.R., Hammersley, J.M.: Percolation processes. I. Crystals and mazes. Proc. Camb. Philos. Soc. 53, 629–641 (1957)

    Article  MathSciNet  Google Scholar 

  10. Brunetti, S., Daurat, A.: Random generation of \(Q\)-convex sets. Theor. Comput. Sci. 347(1–2), 393–414 (2005)

    Article  MathSciNet  Google Scholar 

  11. Cannon, J.W., Floyd, W.J., Parry, W.R.: Combinatorially regular polyomino tilings. Discrete Comput. Geom. 35(2), 269–285 (2006)

    Article  MathSciNet  Google Scholar 

  12. Castiglione, G., Restivo, A., Vaglica, R.: A reconstruction algorithm for \(L\)-convex polyominoes. Theor. Comput. Sci. 356(1–2), 58–72 (2006)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  14. Conway, A.R., Guttmann, A.J.: On two-dimensional percolation. J. Phys. A 28(4), 891–904 (1995)

    Article  Google Scholar 

  15. Delest, M.-P., Viennot, G.: Algebraic languages and polyominoes enumeration. Theor. Comput. Sci. 34(1–2), 169–206 (1984)

    Article  MathSciNet  Google Scholar 

  16. Del Lungo, A., Mirolli, M., Pinzani, R., Rinaldi, S.: A bijection for directed-convex polyominoes. Discrete Math. Theor. Comput. Sci. AA, 133–144 (2001)

    MathSciNet  MATH  Google Scholar 

  17. Enting, I.G., Guttmann, A.J.: Polygons on the honeycomb lattice. J. Phys. A 22(9), 1371–1384 (1989)

    Article  MathSciNet  Google Scholar 

  18. Feretić, S.: A perimeter enumeration of column-convex polyominoes. Discrete Math. Theor. Comput. Sci. 9(1), 57–83 (2007)

    MathSciNet  MATH  Google Scholar 

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

    Book  Google Scholar 

  20. Golomb, S.W.: Checker boards and polyominoes. Am. Math. Mon. 61(10), 675–682 (1954)

    Article  MathSciNet  Google Scholar 

  21. Goodman, J.E., O’Rourke, J., Tóth, C.D. (eds.): Handbook of Discrete and Computational Geometry. 3rd ed. Discrete Mathematics and Its Applications (Boca Raton). CRC Press, Boca Raton (2018)

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

    Article  MathSciNet  Google Scholar 

  23. Grünbaum, B., Shephard, G.C.: Tilings and Patterns. A Series of Books in the Mathematical Sciences. W.H. Freeman and Company, New York (1989)

  24. Hakim, V., Nadal, J.P.: Exact results for 2D directed animals on a strip of finite width. J. Phys. A 16(7), L213–L218 (1983)

    Article  Google Scholar 

  25. Heubach, S., Mansour, T.: Combinatorics of Compositions and Words. Discrete Mathematics and Its Applications (Boca Raton). CRC Press, Boca Raton (2010)

  26. Hou, Q.-H., Mansour, T.: Kernel method and linear recurrence system. J. Comput. Appl. Math. 216(1), 227–242 (2008)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  28. Jensen, I., Guttmann, A.J.: Statistics of lattice animals (polyominoes) and polygons. J. Phys. A 33(29), L257–L263 (2000)

    Article  MathSciNet  Google Scholar 

  29. Klarner, D.A.: Some results concerning polyominoes. Fibonacci Quart. 3, 9–20 (1965)

    MathSciNet  MATH  Google Scholar 

  30. Klarner, D.A.: Packing a rectangle with congruent \(n\)-ominoes. J. Comb. Theory 7, 107–115 (1969)

    Article  MathSciNet  Google Scholar 

  31. Klarner, D.: My life among the polyominoes. Nieuw Arch. Wisk. 29(2), 156–177 (1981)

    MathSciNet  MATH  Google Scholar 

  32. Knopfmacher, A., Mansour, T.: Up-smooth samples of geometric variables. J. Comb. Math. Comb. Comput. 83, 51–63 (2012)

    MathSciNet  MATH  Google Scholar 

  33. Knopfmacher, A., Mansour, T., Munagi, A.: Smooth compositions and smooth words. Pure Math. Appl. 22(2), 209–226 (2011)

    MathSciNet  MATH  Google Scholar 

  34. Mansour, T.: Smooth partitions and Chebyshev polynomials. Bull. Lond. Math. Soc. 41(6), 961–970 (2009)

    Article  MathSciNet  Google Scholar 

  35. Peard, P.J., Gaunt, D.S.: \(1/d\)-expansions for the free energy of lattice animal models of a self-interacting branched polymer. J. Phys. A 28(21), 6109–6124 (1995)

    Article  MathSciNet  Google Scholar 

  36. Prellberg, T., Brak, R.: Critical exponents from nonlinear functional equations for partially directed cluster models. J. Stat. Phys. 78(3–4), 701–730 (1995)

    Article  Google Scholar 

  37. Privman, V., Švrakić, N.M.: Difference equations in statistical mechanics. I. Cluster statistics models. J. Stat. Phys. 51(5–6), 1091–1110 (1988)

    Article  MathSciNet  Google Scholar 

  38. Privman, V., Švrakić, N.M.: Directed Models of Polymers, Interfaces, and Clusters: Scaling and Finite-Size Properties. Lecture Notes in Physics, vol. 338. Springer, Berlin (1989)

  39. Prodinger, H.: The kernel method: a collection of examples. Sém. Lothar. Comb. 50, # B50f (2003/04)

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

    Article  MathSciNet  Google Scholar 

  41. Viennot, G.: Problèmes combinatoires posés par la physique statistique. Astérisque 121–122, 225–246 (1985)

    MATH  Google Scholar 

  42. Viennot, X.G.: A survey of polyominoes enumeration. In: 4th International Conference on Formal Power Series and Algebraic Combinatorics (Montreal 1992). Publications du Laboratoire de Combinatoire et d’Informatique Mathématique, vol. 11, pp. 399–420. LACIM, Montreal (1992)

  43. Zeilberger, D.: The umbral transfer-matrix method. I. Foundations. J. Comb. Theory Ser. A 91(1–2), 451–463 (2000)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We thank the anonymous referees for their careful reading of our manuscript and their insightful comments and suggestions.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Haifa, 3498838, Haifa, Israel

    Toufik Mansour

  2. Department of Mathematics, University of Pristina, 10000, Pristina, Republic of Kosovo

    Armend Sh. Shabani

Authors
  1. Toufik Mansour
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Armend Sh. Shabani
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Armend Sh. Shabani.

Additional information

Editor in Charge: Kenneth Clarkson

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Mansour, T., Shabani, A.S. Smooth Column Convex Polyominoes. Discrete Comput Geom 68, 525–539 (2022). https://doi.org/10.1007/s00454-022-00405-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00454-022-00405-9

Keywords

Mathematics Subject Classification

Search

Navigation