Wilf-equivalence for singleton classes (Q2643864)

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\).