A closed formula for the number of convex permutominoes

The volume and the number of lattice points of the permutohedron P_n are given by certain multivariate polynomials that have remarkable combinatorial properties. We give several different formulas for these polynomials. We also study a more general class of polytopes that includes the permutohedron, the associahedron, the cyclohedron, the Pitman-Stanley polytope, and various generalized associahedra related to wonderful compactifications of De Concini-Procesi. These polytopes...

Ehrhart theory measures a polytope P discretely by counting the lattice points inside its dilates P, 2P, 3P, .... We compute the Ehrhart quasipolynomials of the standard Coxeter permutahedra for the classical Coxeter groups, expressing them in terms of the Lambert W function. A central tool is a description of the Ehrhart theory of a rational translate of an integer zonotope.

H. N. V. Temperley's method for counting vertically convex polyominoes is modified, generalized, and most importantly, programmed (in Maple).

The goal of this paper is to study the family of snake polyominoes. More precisely, we focus our attention on the class of partially directed snakes. We establish functional equations and length generating functions of two dimensional, three dimensional and then $N$ dimensional partially directed snake polyominoes. We then turn our attention to partially directed snakes inscribed in a $b\times k$ rectangle and we establish two-variable generating functions, with respect to he...

This article introduces an analogue of permutation classes in the context of polyominoes. For both permutation classes and polyomino classes, we present an original way of characterizing them by avoidance constraints (namely, with excluded submatrices) and we discuss how canonical such a description by submatrix-avoidance can be. We provide numerous examples of permutation and polyomino classes which may be defined and studied from the submatrix-avoidance point of view, and c...

In this paper we establish six bijections between a particular class of polyominoes, called deco polyominoes, enumerated according to their directed height by n!, and permutations. Each of these bijections allows us to establish different correspondences between classical statistics on deco polyominoes and on permutations.

We investigate the combinatorics and geometry of permutation polytopes associated to cyclic permutation groups, i.e., the convex hulls of cyclic groups of permutation matrices. We give formulas for their dimension and vertex degree. In the situation that the generator of the group consists of at most two orbits, we can give a complete combinatorial description of the associated permutation polytope. In the case of three orbits the facet structure is already quite complex. For...

Enumeration of various types of lattice polygons and in particular polyominoes is of primary importance in many machine learning, pattern recognition, and geometric analysis problems. In this work, we develop a large deviation principle for convex polyominoes under different restrictions, such as fixed area and/or perimeter.

In this note we investigate the convex hull of those $n \times n$-permutation matrices that correspond to symmetries of a regular $n$-gon. We give the complete facet description. As an application, we show that this yields a Gorenstein polytope, and we determine the Ehrhart $h^*$-vector.

In this paper, we enumerate two families of polycubes, the directed plateau polycubes and the plateau polycubes, with respect to the width and a new parameter, the Lateral Area. We give an explicit formula and the generating function for each of the two families of polycubes. Moreover, some asymptotic results about plateau polycubes are provided. We also establish results concerning the enumeration of column-convex polyominoes that are useful to get asymptotic results of poly...