Wilf-equivalence for singleton classes
Given \(n\) and a permutation matrix \(M\) of rank less than \(n\), how many \(n \times n\) permutation matrices do \textit{not} have \(M\) as a submatrix? Letting \(S_n(M)\) be the set of \(n \times n\) permutation matrices not admitting \(M\) as a submatrix, we want \(| S_n(M)| \). This curiously complex problem has a prehistory extending back several decades (see [\textit{D. E. Knuth}, The art of computer programming. Vol. 3: sorting and searching. 2nd ed. (Addison-Wesley, Bonn) (1997; Zbl 0883.68015)] although the formal history seems to have started with [\textit{R. Simion} and \textit{F. W. Schmidt}, Eur. J. Comb. 6, 383--406 (1985; Zbl 0615.05002)]. According to this paper, H. Wilf raised the question of which pairs of \(n \times n\) matrices \(M_1\) and \(M_2\) satisfy \(| S_n(M_1)| = | S_n(M)| \). Following [\textit{E. Babson} and \textit{D. West}, Graphs Comb. 16, No.~4, 373-380 (2000; Zbl 0988.05008)], this paper concerns the ``Wilf equivalence relation: \(M \overset {W}{\sim} M'\) if \(| S_n(M)| = | S_n(M')| \) for all \(n > 0\). The primary result in this paper is the following. Let \(I_t\) be the \(t \times t\) identity matrix, and let \(J_t\) be the matrix of entries \(\delta_{i, t+1-i}\). Then for any \(A\), \[ \left[ \begin{matrix} I_t & 0 \\ 0 & A \end{matrix} \right] \, \overset {W}{\sim} \, \left[ \begin{matrix} J_t & 0 \\ 0 & A \end{matrix} \right]. \] This is a generalization of previous results. The proof (which is actually composed in terms of Young diagrams, which uses an equivalence relation \(\overset{sW}{\sim}\)) rests on two lemmas: (1) If \(C\) and \(D\) are \(t \times t\) matrices and \(C \, \overset{sW}{\sim} \, D\), then \[ \left[ \begin{matrix} C & 0 \\ 0 & A \end{matrix} \right] \, \overset{sW}{\sim} \, \left[ \begin{matrix} D & 0 \\ 0 & A \end{matrix} \right]. \] (2) If \(t > 0\), then \(I_t \, \overset{sW}{\sim} \, J_t\). Much of the article is devoted to two proofs of (2), each presenting a bijection from \(S_{\lambda}(I_t)\) onto \(S_{\lambda}(J_t)\) for appropriate Young diagrams \(\lambda\).
- The permutations 123p₄ p_m and 321p₄ p_m are Wilf-equivalent
- scientific article; zbMATH DE number 125616
- Matrices permutation equivalent to primitive matrices
- scientific article; zbMATH DE number 4057527
- Permutative nonnegative matrices with prescribed spectrum
- A note on the rank inequality for diagonally magic matrices
- On \(\kappa\)-real and \(\kappa\)-Hermitian matrices
- Bijective matrix algebra
- Ranks of permutative matrices
- scientific article; zbMATH DE number 774598
- On bijections for pattern-avoiding permutations
- The solution of a conjecture of Stanley and Wilf for all layered patterns
- Permutations avoiding certain patterns: The case of length 4 and some generalizations
- Finite transition matrices for permutations avoiding pairs of length four patterns
- A new class of Wilf-equivalent permutations
- Wilf equivalence relations for consecutive patterns
- On (shape-)Wilf-equivalence for words
- Explicit enumeration of 321, hexagon-avoiding permutations
- Pattern avoidance in matchings and partitions
- Classical and consecutive pattern avoidance in rooted forests
- Classical length-5 pattern-avoiding permutations
- Hecke insertion and maximal increasing and decreasing sequences in fillings of stack polyominoes
- Pattern-avoiding \(( 0 , 1 )\)-matrices and bases of permutation matrices
- On a refinement of Wilf-equivalence for permutations
- Maximal increasing sequences in fillings of almost-moon polyominoes
- A new class of multiset Wilf equivalent pairs
- Decreasing subsequences in permutations and Wilf equivalence for involutions
- Avoiding a pair of patterns in multisets and compositions
- k-noncrossing and k-nonnesting graphs and fillings of Ferrers diagrams
- New equivalences for pattern avoiding involutions
- Partial permutations avoiding pairs of patterns
- Shape-Wilf-equivalences for vincular patterns
- Beyond alternating permutations: pattern avoidance in Young diagrams and tableaux
- On pattern avoiding alternating permutations
- Ascent-descent Young diagrams and pattern avoidance in alternating permutations
- Modified growth diagrams, permutation pivots, and the BWX map \(\phi ^{\ast}\)
- Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns
- Fast algorithms for finding pattern avoiders and counting pattern occurrences in permutations
- An infinite family of inv-Wilf-equivalent permutation pairs
- Large deviations for permutations avoiding monotone patterns
- Fillings of skew shapes avoiding diagonal patterns
- Uniquely-Wilf classes
- Counting permutations with no long monotone subsequence via generating trees and the kernel method
- Increasing and decreasing sequences in fillings of moon polyominoes
- The limit of a Stanley-Wilf sequence is not always rational, and layered patterns beat monotone patterns
- The permutations 123p₄ p_m and 321p₄ p_m are Wilf-equivalent
- On refinements of Wilf-equivalence for involutions
- Wilf equivalences for patterns in rooted labeled forests
- Equidistribution of set-valued statistics on standard Young tableaux and transversals
- Long increasing subsequences and non-algebraicity
- Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
- Combinatorics of exterior peaks on pattern-avoiding symmetric transversals
- Enumeration of pattern-avoiding alternating sign matrices: an asymptotic dichotomy
- Distribution of sets of descent tops and descent bottoms on restricted permutations
- Enumerating 1324-avoiders with few inversions
- Proof of a conjecture on the shape-Wilf-equivalence for partially ordered patterns
- On (shape-)Wilf-equivalence of certain sets of (partially ordered) patterns
- Ordinal and disjoint sums of partially ordered patterns
- Stack-sorting, set partitions, and Lassalle's sequence
- New records in Stanley-Wilf limits
- Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes
- A general theory of Wilf-equivalence for Catalan structures
- \(k\)-noncrossing and \(k\)-nonnesting graphs and fillings of Ferrers diagrams
- Another look at bijections for pattern-avoiding permutations
This page was built for publication: Wilf-equivalence for singleton classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2643864)
