Permutations with forbidden patterns and polyominoes on a twisted cylinder of width 3

In a cubical lattice on a “twisted cylinder,” connectivity of cells form a spiral rather than a cylindrical shape. It was recently proven that for any fixed w , the enumerating sequence for the number of polyominoes on the twisted cylinder of perimeter w satisfies a linear recursion. This recursion is determined by the minimal polynomial of the transfer matrix that models the growth of polyominoes on the cylinder. In this paper we present a direct construction of the recursion for the case w = 3 . In addition, we make a connection between enumeration of polyominoes and of permutations: We find bijections between three classes of permutations, each defined in terms of eight forbidden patterns, and the set of polyominoes on a twisted cylinder of width 3. In particular, it follows that all three classes of permutations belong to the same Wilf class, obeying the same recurrence formula (with respect to size) as that of the considered polyominoes, that is, a n = 2 a n − 1 + a n − 2 + 2 a n − 3 , with a 1 = 1 , a 2 = 2 , and a 3 = 6 .