A combinatorial proof for the enumeration of alternating permutations with given peak set (Q2866622)

A permutation \(\sigma=\sigma_1\sigma_2\dots\sigma_n\) on \([n]:=\{1,2,\dots,n\}\) is called alternating if \(\sigma_1>\sigma_2<\sigma_3>\sigma_4<\dots\) and is called reverse alternating or an up-down permutation if \(\sigma_1<\sigma_2>\sigma_3<\sigma_4>\dots\). The sets of alternating and reverse alternating permutations are denoted by \(\mathcal{E}_n\) and \(\mathcal{E}_n^c\). For a permutation \(\sigma\), the element \(\sigma_j\) (\(1\leqslant j\leqslant n\)) is called a peak if \(\sigma_{j-1}<\sigma_j>\sigma_{j+1}\), where \(\sigma_0\) and \(\sigma_{n+1}\) are assumed to be 0. The peak set of \(\sigma\) is then the set of all peaks of \(\sigma\). Let \(S_k(i_1,i_2,\dots,i_k)\) denote the set of all permutations in \(\mathcal{E}_{2k}\) with peak set \(\{i_1,i_2,\dots,i_k\}\), where \(2\leqslant i_1<i_2<\dots<i_k=n\). Moreover, suppose that \(T_k(i_1,i_2,\dots,i_{k+1})\) denotes the set of all permutations in \(\mathcal{E}_{2k+1}\) with peak set \(\{i_1,i_2,\dots,i_{k+1}\}\), where \(2\leqslant i_1<i_2<\dots<i_k<i_{k+1}=n\). Put \(s_k(i_1,i_2,\dots,i_k)=|S_k(i_1,i_2,\dots,i_k)|\) and \(t_k(i_1,i_2,\dots,i_{k+1})=|T_k(i_1,i_2,\dots,i_{k+1})|\).NEWLINENEWLINENEWLINEThe author gives a combinatorial proof for a known theorem which asserts that \(s_k(i_1,i_2,\dots,i_k)=\prod_{1\leqslant j\leqslant k}(i_j-2j+1)^2\) and \(t_k(i_1,i_2,\dots,i_{k+1})=\prod_{1\leqslant j\leqslant k}(i_j-2j+2)(i_j-2j+1)\) for \(k\geqslant1\). The author also shows that the number of alternating permutations in \(\mathcal{E}_{2k}\) with \(k\) left to right maxima equals the number of alternating permutations in \(\mathcal{E}_{2k}\) which avoid the patterns \(31-42\) and \(42-31\) (or \(32-41\) and \(41-32\)). An analogous statement for \(\mathcal{E}_{2k+1}\) is also given.