About half permutations

Simone Rinaldi¹ ; Samanta Socci¹

¹University of Sienna

The electronic journal of combinatorics, Tome 21 (2014) no. 1

Résumé

In 2011, Beaton et al. analytically proved that the number of directed column-convex permutominoes of size $n$ is given by $(n+1)!/2$. In this paper, we provide a different proof of this statement using a bijective method. More precisely, we present a bijective correspondence between the class $D_n$ of directed column-convex permutominoes of size $n$ and a set of permutations (called $dcc$-permutations) of length $n+1$, which we prove to be counted by $(n+1)!/2$. The class of $dcc$-permutations is a new class of permutations counted by half factorial numbers, and here we show some combinatorial characterizations of this class, using the concept of logical formulas determined by a permutation and the notion of mesh pattern.

Détail

DOI : 10.37236/3490

Classification : 05A05, 05A15, 05B50
Mots-clés : permutations, polyominoes, pattern avoiding permutations