Patterns in multi-dimensional permutations
In this paper, a \(d\)-dimensional permutation of length \(n\) is a \((d-1)\)-tuple \((\pi^2,\ldots,\pi^d)\) of permutations in \(S_n\), represented as a \(d \times n\) matrix whose first row \(\pi^1\) is the identity \(0,1,\ldots,n-1\); columns are called elements, and ordinary permutations correspond to \(d=2\). Other notions of higher-dimensional permutations exist in the literature; here, each column is assigned a level, and patterns are defined via order relations on level sequences, where equal levels create plateaux. Two level functions are studied: \(\operatorname{levMax}\) returns the maximum entry in a column, \(\operatorname{levSum}\) the sum.\N\NUnder \(\operatorname{levMax}\), the number \(R_{n,k}\) of canonical 3-dimensional permutations with exactly \(k\) repeated levels satisfies \(R_{n,k}=(2k+1)R_{n-1,k}+(n-2k+1)R_{n-1,k-1}\), matching the count of ordinary permutations with \(k\) increasing runs of length at least 2 (OEIS A008971). The bivariate EGF \(\mathcal{R}(x,y)=\sqrt{y-1}/(\sqrt{y-1}\cos(x\sqrt{y-1})-\sin(x\sqrt{y-1}))\) is obtained by translating the recurrence to a first-order PDE. The polynomial \(\mathcal{R}_{n,\ast}(y)=\sum_k R_{n,k}y^k\) forms a generalized Sturm sequence via the Liu-Wang criterion, hence is real-rooted. Weakly increasing 3-dimensional permutations (avoiding pattern \(21\), equivalently \(\underline{21}\) in the level word) have EGF \((\cos x - \sin x)^{-1}\), giving a combinatorial interpretation of the Springer numbers. Hoe permutations (unimodal with exactly one descent at position \(n-1\)) satisfy \(H_{n,d}=\sum_{k=0}^{n-2}(2^{d-1}-1)^k\), yielding interpretations for OEIS A023000, OEIS A135518, and OEIS A218734 (for \(d=4,5,6\); reported there as lacking one).\N\NUnder \(\operatorname{levSum}\), the minimum achievable maximum level is \(\lceil(d-1)(n-1)/2\rceil\), achieved via cyclic-shift constructions. The count of \(c\)-bounded 3-dimensional permutations is \(c!(c+1)^{n-c}n!\), unifying OEIS A008776, OEIS A002023, and OEIS A235702. The total number of plateaux among all \((3,n)\)-permutations equals \((2n-1)n!(n-1)!/3\) under both level definitions.
- A combinatorial theory of higher-dimensional permutation arrays
- A unified approach to polynomial sequences with only real zeros
- An Ising model having permutation spin motivated by a permutation complexity measure
- An upper bound on the number of high-dimensional permutations
- Combinatorics of Compositions and Words
- Context-free grammars, differential operators and formal power series
- Counting permutations by runs
- Derivative polynomials and enumeration of permutations by number of interior and left peaks
- Distribution of maxima and minima statistics on alternating permutations, Springer numbers, and avoidance of flat POPs
- Enumeration of (0.1)-matrices avoiding some 2 2 matrices
- Enumeration of factorizable multi-dimensional permutations
- Enumeration of snakes and cycle-alternating permutations
- scientific article; zbMATH DE number 2186901 (Why is no real title available?)
- scientific article; zbMATH DE number 568836 (Why is no real title available?)
- scientific article; zbMATH DE number 718851 (Why is no real title available?)
- scientific article; zbMATH DE number 7640030 (Why is no real title available?)
- scientific article; zbMATH DE number 3355039 (Why is no real title available?)
- Introduction to partially ordered patterns
- Labeled ballot paths and the Springer numbers
- Monotone subsequences in high-dimensional permutations
- On the Bernoullian function.
- On the coefficients in the expansions of \(\frac{\cos x}{\cos 2x}\) and \(\frac{\sin x}{\cos 2x}\).
- On the communication complexity of high-dimensional permutations
- Patterns in permutations and words.
- Separable \(d\)-permutations and guillotine partitions
- Singleton mesh patterns in multidimensional permutations
- The calculus of snakes and the combinatorics of Bernoulli, Euler and Springer numbers of Coxeter groups
- The Euler and Springer numbers as moment sequences
- The on-line encyclopedia of integer sequences
- The total number of descents and levels in tensor words and cyclic tensor words
- Total occurrence statistics on restricted permutations
- Unimodality, log-concavity, real-rootedness and beyond
This page was built for publication: Patterns in multi-dimensional permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6930162)
