Enrica Duchi - A code for square permutations and convex permutominoes

dmtcs:5354 - Discrete Mathematics & Theoretical Computer Science, December 30, 2019, Vol. 21 no. 2, Permutation Patters 2018 - https://doi.org/10.23638/DMTCS-21-2-2
A code for square permutations and convex permutominoesArticle

Authors: Enrica Duchi

    In this article we consider square permutations, a natural subclass of permutations defined in terms of geometric conditions, that can also be described in terms of pattern avoiding permutations, and convex permutoninoes, a related subclass of polyominoes. While these two classes of objects arised independently in various contexts, they play a natural role in the description of certain random horizontally and vertically convex grid configurations. We propose a common approach to the enumeration of these two classes of objets that allows us to explain the known common form of their generating functions, and to derive new refined formulas and linear time random generation algorithms for these objects and the associated grid configurations.


    Volume: Vol. 21 no. 2, Permutation Patters 2018
    Published on: December 30, 2019
    Accepted on: September 10, 2019
    Submitted on: April 7, 2019
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 1081 times.
    This article's PDF has been downloaded 164 times.