Enumeration of permutations of (1, , n) by number of maxima

From MaRDI portal
Publication:2536617





A permutation \((a_1, \ldots, a_n\) of \((1, \ldots, n)\) will be called a circle (line) \(n\)-permutation iff \(a_1\) and \(a_n\) are (are not) considered adjacent. \(a_1\) is said to be a maximum of such a permutation iff \(a_1\) is greater than the member(s) adjacent to it. For example the permutation 41325 has \(2\) \((3)\) maxima as a circle (line) permutation. If we define \(M(n, k)\) \((M^*(n, k)\), \(n \geq 1\) to be the number of circle (line) \(n\)-permutations having exactly \(k\) maxima and further set \(M(1,0)=1\), \(M(n, 0)=0\) for \(n \geq 2\); \(M^*(0,0)=1\), \(M^*(n, 0)=0\) for \(n \geq 1\) we have the recurrence relation \[ M(n+1, k)=\frac{n+1}{n} [2k M(n, k)+(n-2k+2) M(n, k-1)] \text { for } n \geq 1, k \geq 1. \] A generating function \[ \sum_{n=1}^{\infty} \sum_{k=0}^{\infty} M(n, k) \frac{x^n}{n!} y^k = x \frac{1-\sqrt{1-y} \operatorname{Tan} h x \sqrt{1-y}}{1-(\operatorname{Tanh} x \sqrt{1-y}) / \sqrt{1-y}} \] and the explicit formula \[ M(n, k)=(-1)^{n+k} n 2^{n-1} \sum_{r=k-1}^{[n/2]-1} \sum_{t=n-2 r-1}^{n-1} \frac{(-1)^{t} t!}{2^t}\binom{r}{k-1}\binom{t-1}{n-2r-2}S(n-1, t) \] for \( n \geq 2\), \(k \geq 0 \), where \[ S(n-1, t)=\frac{(-1)^t}{t!} \sum_{s=1}^t (-1)^s\binom{t}{s} s^{n-1} \] is a Stirling number of the second kind are also obtained. The author has also shown (unpublished) that \( M(n+1, k)=(n+1) M ^*(n, k)\), \(n \geq 0\), \(k \geq 0 \).












This page was built for publication: Enumeration of permutations of \((1, \ldots, n)\) by number of maxima

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2536617)