Skip to Main content Skip to Navigation
Conference papers

The number of $k$-parallelogram polyominoes

Abstract : 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}$.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01229685
Contributor : Alain Monteil <>
Submitted on : Tuesday, November 17, 2015 - 10:19:55 AM
Last modification on : Monday, October 12, 2020 - 10:30:32 AM
Long-term archiving on: : Thursday, February 18, 2016 - 11:38:08 AM

File

dmAS0194.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01229685, version 1

Collections

Citation

Daniela Battaglino, Jean-Marc Fédou, Simone Rinaldi, Samanta Socci. The number of $k$-parallelogram polyominoes. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.1113-1124. ⟨hal-01229685⟩

Share

Metrics

Record views

134

Files downloads

650