The number of $k$-parallelogram polyominoes
A convex polyomino is $k$-$\textit{convex}$ if every pair of its cells can be connected by means of a $\textit{monotone path}$, internal to the polyomino, and having at most $k$ changes of direction. The number $k$-convex polyominoes of given semi-perimeter has been determined only for small values...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2013-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2370/pdf |
| _version_ | 1797270271064801280 |
|---|---|
| author | Daniela Battaglino Jean-Marc Fédou Simone Rinaldi Samanta Socci |
| author_facet | Daniela Battaglino Jean-Marc Fédou Simone Rinaldi Samanta Socci |
| author_sort | Daniela Battaglino |
| collection | DOAJ |
| description | A convex polyomino is $k$-$\textit{convex}$ if every pair of its cells can be connected by means of a $\textit{monotone path}$, internal to the polyomino, and having at most $k$ changes of direction. The number $k$-convex polyominoes of given semi-perimeter has been determined only for small values of $k$, precisely $k=1,2$. In this paper we consider the problem of enumerating a subclass of $k$-convex polyominoes, precisely the $k$-$\textit{convex parallelogram polyominoes}$ (briefly, $k$-$\textit{parallelogram polyominoes}$). For each $k \geq 1$, we give a recursive decomposition for the class of $k$-parallelogram polyominoes, and then use it to obtain the generating function of the class, which turns out to be a rational function. We are then able to express such a generating function in terms of the $\textit{Fibonacci polynomials}$. |
| first_indexed | 2024-04-25T02:01:37Z |
| format | Article |
| id | doaj.art-3e0d86ce64574a599af73a52947906b6 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:01:37Z |
| publishDate | 2013-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-3e0d86ce64574a599af73a52947906b62024-03-07T14:52:36ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502013-01-01DMTCS Proceedings vol. AS,...Proceedings10.46298/dmtcs.23702370The number of $k$-parallelogram polyominoesDaniela Battaglino0Jean-Marc Fédou1Simone Rinaldi2https://orcid.org/0000-0003-3377-5331Samanta Socci3Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe MC3Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe MC3Dipartimento di Matematica e Informatica [Siena]Dipartimento di Matematica e Informatica [Siena]A convex polyomino is $k$-$\textit{convex}$ if every pair of its cells can be connected by means of a $\textit{monotone path}$, internal to the polyomino, and having at most $k$ changes of direction. The number $k$-convex polyominoes of given semi-perimeter has been determined only for small values of $k$, precisely $k=1,2$. In this paper we consider the problem of enumerating a subclass of $k$-convex polyominoes, precisely the $k$-$\textit{convex parallelogram polyominoes}$ (briefly, $k$-$\textit{parallelogram polyominoes}$). For each $k \geq 1$, we give a recursive decomposition for the class of $k$-parallelogram polyominoes, and then use it to obtain the generating function of the class, which turns out to be a rational function. We are then able to express such a generating function in terms of the $\textit{Fibonacci polynomials}$.https://dmtcs.episciences.org/2370/pdfconvex polyominoesl-convex polyominoesrational generating functionsfibonacci polynomials[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Daniela Battaglino Jean-Marc Fédou Simone Rinaldi Samanta Socci The number of $k$-parallelogram polyominoes Discrete Mathematics & Theoretical Computer Science convex polyominoes l-convex polyominoes rational generating functions fibonacci polynomials [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | The number of $k$-parallelogram polyominoes |
| title_full | The number of $k$-parallelogram polyominoes |
| title_fullStr | The number of $k$-parallelogram polyominoes |
| title_full_unstemmed | The number of $k$-parallelogram polyominoes |
| title_short | The number of $k$-parallelogram polyominoes |
| title_sort | number of k parallelogram polyominoes |
| topic | convex polyominoes l-convex polyominoes rational generating functions fibonacci polynomials [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/2370/pdf |
| work_keys_str_mv | AT danielabattaglino thenumberofkparallelogrampolyominoes AT jeanmarcfedou thenumberofkparallelogrampolyominoes AT simonerinaldi thenumberofkparallelogrampolyominoes AT samantasocci thenumberofkparallelogrampolyominoes AT danielabattaglino numberofkparallelogrampolyominoes AT jeanmarcfedou numberofkparallelogrampolyominoes AT simonerinaldi numberofkparallelogrampolyominoes AT samantasocci numberofkparallelogrampolyominoes |