A polyominoes-permutations injection and tree-like convex polyominoes |
| |
Authors: | Gadi Aleksandrowicz |
| |
Institution: | a Center for Graphics and Geometric Computing, Dept. of Computer Science, The Technion—Israel Inst. of Technology, Haifa 32000, Israel b Dept. of Mathematics, The Technion—Israel Inst. of Technology, Haifa 32000, Israel |
| |
Abstract: | Plane polyominoes are edge-connected sets of cells on the orthogonal lattice Z2, 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 an=6an−1−14an−2+16an−3−9an−4+2an−5, and compute the closed-form formula an=2n+2−(n3−n2+10n+4)/2. |
| |
Keywords: | Permutation patterns Generating function Recurrence formula |
本文献已被 ScienceDirect 等数据库收录! |
|