About Half Permutations

Abstract

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.