Journal of Combinatorics

Volume 9 (2018)

Number 1

3-dimensional polygons determined by permutations

Pages: 57 – 94

DOI: http://dx.doi.org/10.4310/JOC.2018.v9.n1.a5

Authors

Enrica Duchi (IRIF, Université Paris Diderot, Paris, France)

Simone Rinaldi (Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche, Università di Siena, Italy)

Samanta Socci (Dipartimento di Ingegneria dell’Informazione e Scienze Matematiche, Università di Siena, Italy)

Abstract

In this paper we introduce the notion of $d$-dimensional permupolygons on $\mathbb{Z}^d$, with $d \geq 2$ 2-dimensional permupolygons, also called permutominides, where introduced by Incitti et al. By using an encoding of permupolygons inspired by the encoding given for convex polyominoes by Bousquet-Mélou and Guttmann, we easily recover enumerative results about 2-dimensional parallelogram, unimodal, column convex and convex permupolygons. Moreover, we extend these results for dimension $d = 3$. Finally, we study combinatorial characterizations of permutations defining 3-dimensional permupolygons. We show some necessary and sufficient conditions for a triple of 2-dimensional permutations $(\pi_1, \pi_2, \pi_3)$ to define a 3-dimensional permupolygon.

Full Text (PDF format)

Received 15 February 2014

Published 5 January 2018