Up-down coefficients for permutations (Q376532)

Let \(\mathcal S_n\) be the set of permutations of the numbers \(1,2,\ldots,n\). In the paper of \textit{I. Niven} [Nieuw Arch. Wiskd., III. Ser. 16, 116--123 (1968; Zbl 0164.33102)] for every permutation \(\pi=(\pi_1,\pi_2,\ldots,\pi_n)\in \mathcal S_n\) the signature \(Q=(q_1,q_2,\ldots,q_{n-1})\) was defined by \(q_i:=1\) if \(\pi_i<\pi_{i+1}\), and \(q_i:=-1\) if \(\pi_i>\pi_{i+1}\). Niven proved by a determinant a formula for the number \([Q]\) of all \(\pi\in \mathcal S_n\) with given signature \(Q\). In the mentioned paper, Niven wrote that he was unable to formulate general equalities and inequalities for the numbers of permutations having different signatures. Recently, \textit{V. Shevelev} [Integers 12, No. 4, 529--569, A1 (2012; Zbl 1248.05006)] introduced a new symbol \(n\brace k\) by the following way. For \(\pi\in \mathcal S_n\) with Niven's signature \(Q=(q_1,q_2,\ldots,q_{n-1})\), the integer \(k=k(Q):=\sum_{1\leq i\leq n-1:\, q_i=1}2^{n-1-i}\) is said to be the index of \(\pi\). Then, \(n\brace k\) denotes the number of all permutations of \(\mathcal S_n\) with index \(k\) and \(n\brace k\) is called the up-down coefficient of \(\pi\). By using a bijective argument, it is easy to see that \({n\brace k}=[Q]\), where \([Q]\) is the number of permutations of \(\mathcal S_n\) with Niven's signature \(Q\). The authors noticed that the following four identities for up-down coefficients \(n\brace k\), which are similar to those for binomial coefficients \(n\choose k\), are satisfied: \({n\brace k}={n\brace 2^{n-1}-1-k}\), \(\sum_{0\leq k<2^{n-1}}{n\brace k}=n!\), \(\sum_{0\leq k<2^{n-1}}(-1)^k{n\brace k}=0\) (\(n>1\)) and \({n\brace 2^{k-1}-1}+{n\brace 2^k-1}={n+1\brace 2^k-1}\). Further, by using the technique of enumeration, several identities and inequalities involving up-down coefficients are proved. The main of these identities are as follows (Theorems 1 and 2): \[ {n+m\brace 2^mk+l}+ {n+m\brace 2^mk+l+2^{m-1}}= {n+m\choose m}{m\brace l} {n\brace k}, \] \[ {n+m\brace (2^{n-1}-1)2^m+l-2^mk}+ {n+m\brace (2^n-1)2^{m-1}+l-2^mk}= {n+m\choose m}{m\brace l} {n\brace k} \] (with \(n\geq 1, 0\leq k<2^{n-1},m\geq 1, 0\leq l<2^{m-1}\)), and \[ \sum_{k=0}^{2^r-1}{n\brace k}=n(n-1)\cdots (n-r+1)\quad (1\leq r\leq n-1). \] Finally, the authors give a short proof of the following equalities established by \textit{R. C. Entringer} [Nieuw Arch. Wiskd., III. Ser. 14, 241--246 (1966; Zbl 0145.01402)]: \({2n\brace k_{2n-1}}=|E_{2n}|\) and \({2n-1\brace k_{2n-2}}=|b_{2n}|\), where \(E_{2n}\) and \(b_{2n}\) are \((2n)\)th Euler and Bernoulli numbers, respectively.