Severini and Mansour introduced $\textit{square polygons}$, as graphical representations of $\textit{square permutations}$, that is, permutations such that all entries are records (left or right, minimum or maximum), and they obtained a nice formula for their number. In this paper we give a recursive construction for this class of permutations, that allows to simplify the derivation of their formula and to enumerate the subclass of square permutations with a simple record polygon. We also show that the generating function of these permutations with respect to the number of records of each type is algebraic, answering a question of Wilf in a particular case.
Discrete Mathematics & Theoretical Computer Science
