A polyominoes-permutations injection and tree-like convex polyominoes

作者：Aleksandrowicz Gadi^*; Asinowski Andrei; Barequet Gill

来源：Journal of Combinatorial Theory - Series A, 2012, 119(3): 503-520.

DOI：10.1016/j.jcta.2011.10.008

• Permutation patterns
• Generating function
• Recurrence formula

Plane polyominoes are edge-connected sets of cells on the orthogonal lattice Z(2), considered identical if their cell sets are equal up to an integral translation. We introduce a novel injection from the set of polyominoes with n cells to the set of permutations of [n], and classify the families of convex polyominoes and tree-like convex polyominoes as classes of permutations that avoid some sets of forbidden patterns. By analyzing the structure of the respective permutations of the family of tree-like convex polyominoes, we are able to find the generating function of the sequence that enumerates this family, conclude that this sequence satisfies the linear recurrence a(n) = 6a(n-1) - 14a(n-2) + 16a(n-3) - 9a(n-4) + 2a(n-5) and compute the closed-form formula a(n) = 2(n+2) - (n(3) - n(2) + 10n + 4)/2.

• 出版日期2012-4