About half permutations (Q405123)

Summary: \textit{N. Beaton} et al. [``On the enumeration of columnconvex permutominoes'', in: Proceedings of the 23rd international conference on formal power series and algebraic combinatorics, FPSAC 2011. 111--122 (2011)] 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.