Journal of Integer Sequences, Vol. 25 (2022), Article 22.8.3

Baxter d-Permutations and Other Pattern-Avoiding Classes

Nicolas Bonichon and Pierre-Jean Morel
Univ. Bordeaux
CNRS, Bordeaux INP
UMR 5800
F-33400 Talence


A permutation of size n can be identified with its diagram in which there is exactly one point in each row and column in the grid [n]2. In this paper we consider multidimensional permutations (or d-permutations), which are identified with their diagrams on the grid [n]d in which there is exactly one point per hyperplane xi = j for i ∈ [d] and j ∈ [n]. We first exhaustively investigate all small pattern-avoiding classes for d = 3. We provide several bijections to enumerate some of these classes and we propose conjectures for others. We then give a generalization of the well-studied Baxter permutations to higher dimensions. In addition, we provide a vincular pattern-avoidance characterization of Baxter d-permutations.

Full version:  pdf,    ps,    latex    

(Concerned with sequences A000108 A000272 A001003 A001181 A001764 A001787 A003946 A006318 A007767 A026150 A026671 A047732 A071684 A071688 A072863 A086810 A090181 A103211 A107841 A131763 A131765 A133308 A190291 A217216 A281593 A295928 A356197.)

Received February 25 2022; revised versions received March 3 2022; July 29 2022; October 11 2022. Published in Journal of Integer Sequences, October 11 2022.

Return to Journal of Integer Sequences home page