"Deco" polyominoes, permutations and random generation

In this paper, we introduce a class of polyominoes, called deco polyominoes, in bijection with the set of permutations of the first k integers. We evaluate some typical parameters for this class of polyominoes and define a linear algorithm for randomly generating them. Moreover, we define the polyominoes corresponding to the directed animals on the hexagonal and triangular lattices and examine these polyominoes’ deco class. As far as deco polyominoes corresponding to animals on the hexagonal lattice are concerned, we find a bijection with a class of permutations. Finally, we give linear algorithms for randomly generating both hexagonal and triangular deco polyominoes.