## The Eulerian Distribution on Involutions is Indeed Unimodal

### November 27, 2006

Institut Camille Jordan, Université Claude Bernard (Lyon I) F-69622, Villeurbanne Cedex, France ${}^{1}$  jwguo@eyou.com, ${}^{2}$  zeng@igd.univ-lyon1.fr
Abstract
Let ${I}_{n,k}$  (resp. ${J}_{n,k}$  ) be the number of involutions (resp. involutions without fixed points ) of length $n$  having $k$  descents. We establish a linear recurrence relations for ${I}_{n,k}$  (resp.
${J}_{2n,k}$  ), which implies that the sequence ${I}_{n,k}$  (resp. ${J}_{2n,k}$  ) is unimodal in $k$  , for all $n$  . We also propose some open problems related to ${I}_{n,k}$  and ${J}_{2n,k}$  .
AMS Subject Classifications (2000): Primary 05A15; Secondary 05A20.

1 Introduction

A sequence ${a}_{0},{a}_{1},\dots ,{a}_{n}$  of real numbers is said to be unimodal if for some $0\le j\le n$  we have ${a}_{0}\le {a}_{1}\le \cdots \le {a}_{j}\ge {a}_{j+1}\ge \cdots \ge {a}_{n}$  , and is said to be log-concave if ${a}_{i}^{2}\ge {a}_{i-1}{a}_{i+1}$  for all $1\le i\le n-1$  . Clearly a log-concave sequence of positive terms is unimodal. The reader is referred to Stanley's survey [11for the surprisingly rich variety of methods to show that a sequence is log-concave or unimodal. As noticed by Brenti [3, even though log-concave and unimodality have one-line definitions, to prove the unimodality or log-concavity of a sequence can sometimes be a very difficult task requiring the use of intricate combinatorial constructions or of refined mathematical tools.
Let ${\mathfrak{S}}_{n}$  be the set of permutations of $\left[n\right]:=\left\{1,\dots ,n\right\}$  . A permutation $\pi ={a}_{1}{a}_{2}\cdots {a}_{n}\in {\mathfrak{S}}_{n}$  has a descent at $i$  ( $1\le i\le n-1$  ) if ${a}_{i}>{a}_{i+1}$  . The number of descents of $\pi$  is called descent number and is denoted by $d\left(\pi \right)$  . A statistic on ${\mathfrak{S}}_{n}$  is said to be Eulerian, if it is equidistributed with the descent number statistic. Recall that the generating function of descent numbers on ${\mathfrak{S}}_{n}$  is the Eulerian polynomial ${A}_{n}\left(t\right)={\sum }_{\pi \in {\mathfrak{S}}_{n}}{t}^{1+d\left(\pi \right)}={\sum }_{k=1}^{n}A\left(n,k\right){t}^{k}.$  It is well-known that the Eulerian numbers $A\left(n,k\right)$  ( $0\le k\le n$  ) form a unimodal sequence, of which several proofs have been published: such as the analytical one by showing that the polynomial ${A}_{n}\left(t\right)$  has only real zeros [4,p.294, by induction based on the recurrence relation of $A\left(n,k\right)$  (see [10) or by combinatorial techniques (see [1, 8, 12).
The purpose of this paper is to prove similar results for two variants of Eulerian polynomials for involutions with or without fixed points. Let ${\Im }_{n}$  be the set of involutions in ${\mathfrak{S}}_{n}$  and ${\mathfrak{J}}_{2n}$  the set of involutions without fixed points in ${\mathfrak{S}}_{2n}$  . Define
 $\begin{array}{cc}{I}_{n}\left(t\right)& ={\sum }_{\pi \in {\Im }_{n}}{t}^{d\left(\pi \right)}={\sum }_{k=0}^{n-1}{I}_{n,k}{t}^{k},\end{array}$
 $\begin{array}{cc}{J}_{2n}\left(t\right)& ={\sum }_{\pi \in {\mathfrak{J}}_{2n}}{t}^{d\left(\pi \right)}={\sum }_{k=0}^{2n-1}{J}_{2n,k}{t}^{k},\end{array}$
 $\begin{array}{}\end{array}$
The first values of these polynomials are given in Table 1.
 $n$ ${I}_{n}\left(t\right)$ ${J}_{n}\left(t\right)$ 1 1 0 2 $1+t$ $t$ 3 $1+2t+{t}^{2}$ 0 4 $1+4t+4{t}^{2}+{t}^{3}$ $t+{t}^{2}+{t}^{3}$ 5 $1+6t+12{t}^{2}+6{t}^{3}+{t}^{4}$ 0 6 $1+9t+28{t}^{2}+28{t}^{3}+9{t}^{4}+{t}^{5}$ $t+3{t}^{2}+7{t}^{3}+3{t}^{4}+{t}^{5}$
As one can notice from the above table that the coefficients of ${I}_{n}\left(t\right)$  and ${J}_{n}\left(t\right)$  are symmetric and unimodal for $1\le n\le 6$  . Actually, the symmetries had been conjectured by Dumont and were first proved by Strehl [13. More recently, Brenti (see [6) conjectured that the coefficients of the polynomial ${I}_{n}\left(t\right)$  are log-concave and Dukes [6has obtained some partial results on the unimodality of the coefficients of ${I}_{n}\left(t\right)$  and ${J}_{2n}\left(t\right)$  . Note that, in contrast to Eulerian polynomials ${A}_{n}\left(t\right)$  , the polynomials ${I}_{n}\left(t\right)$  and ${J}_{2n}\left(t\right)$  may have non-real zeros.
In this paper we will prove that for $n\ge 1$  , the two sequences ${I}_{n,0},{I}_{n,1},\dots ,{I}_{n,n-1}$  and ${J}_{2n,1},{J}_{2n,1},\dots ,{J}_{2n,2n-1}$  are unimodal (cf. Theorems 3.2 and 3.3). Our starting point is the known generating functions of the polynomials ${I}_{n}\left(t\right)$  and ${J}_{2n}\left(t\right)$  :
 $\begin{array}{cc}{\sum }_{n=0}^{\infty }{I}_{n}\left(t\right)\frac{{u}^{n}}{\left(1-t{\right)}^{n+1}}& ={\sum }_{r=0}^{\infty }\frac{{t}^{r}}{\left(1-u{\right)}^{r+1}\left(1-{u}^{2}{\right)}^{r\left(r+1\right)/2}},\end{array}$ (1.1)
 $\begin{array}{cc}{\sum }_{n=0}^{\infty }{J}_{n}\left(t\right)\frac{{u}^{n}}{\left(1-t{\right)}^{n+1}}& ={\sum }_{r=0}^{\infty }\frac{{t}^{r}}{\left(1-{u}^{2}{\right)}^{r\left(r+1\right)/2}},\end{array}$ (1.2)
 $\begin{array}{}\end{array}$
which have been obtained by Désarménien and Foata [5and Gessel and Reutenauer [9using different methods. We first derive the linear recurrence formulas for ${I}_{n,k}$  and ${J}_{2n,k}$  in the next section and then prove the unimodality by induction. We end this paper with some open problems.

2 Linear recurrence formulas for ${I}_{n,k}$  and ${J}_{2n,k}$

Since the recurrence formula for the coefficients ${I}_{n,k}$  is a little more complicated than ${J}_{2n,k}$  , we shall first prove that for ${J}_{2n,k}$  .
Theorem 2.1 For $n\ge 2$  and $k\ge 0$  , the coefficients ${J}_{2n,k}$  satisfy the following recurrence formula:
 $\begin{array}{cc}2n{J}_{2n,k}& =\left[k\left(k+1\right)+2n-2\right]{J}_{2n-2,k}+2\left[\left(k-1\right)\left(2n-k-1\right)+1\right]{J}_{2n-2,k-1}\end{array}$
 $\begin{array}{cc}& +\left[\left(2n-k\right)\left(2n-k+1\right)+2n-2\right]{J}_{2n-2,k-2},\end{array}$ (2.1)
 $\begin{array}{}\end{array}$
where ${J}_{2n,k}=0$  if $k<0$  .
Proof. Equating the coefficients of ${u}^{2n}$  on both sides of  1.2 , we obtain
 $\begin{array}{c}{f}_{n}\left(t\right):=\frac{{J}_{2n}\left(t\right)}{\left(1-t{\right)}^{2n+1}}={\sum }_{r=0}^{\infty }\left(\genfrac{}{}{0}{}{r\left(r+1\right)/2+n-1}{n}\right){t}^{r}.\end{array}$ (2.2)
Since $\left(\genfrac{}{}{0}{}{r\left(r+1\right)/2+n-1}{n}\right)=\frac{r\left(r-1\right)/2+r+n-1}{n}\left(\genfrac{}{}{0}{}{r\left(r+1\right)/2+n-2}{n-1}\right),$  it follows from  2.2 that
 $\begin{array}{cc}{f}_{n}\left(t\right)=\frac{{t}^{2}}{2n}{f}_{n-1}^{\prime \prime }\left(t\right)+\frac{t}{n}{f}_{n-1}^{\prime }\left(t\right)+\frac{n-1}{n}{f}_{n-1}\left(t\right).& \end{array}$
 $\begin{array}{}\end{array}$
Namely, $\frac{{J}_{2n}\left(t\right)}{\left(1-t{\right)}^{2n+1}}=\frac{{t}^{2}}{2n}{\left(\frac{{J}_{2n-2}\left(t\right)}{\left(1-t{\right)}^{2n-1}}\right)}^{\prime \prime }+\frac{t}{n}{\left(\frac{{J}_{2n-2}\left(t\right)}{\left(1-t{\right)}^{2n-1}}\right)}^{\prime }+\frac{n-1}{n}\frac{{J}_{2n-2}\left(t\right)}{\left(1-t{\right)}^{2n-1}},$  or
 $\begin{array}{cc}{J}_{2n}\left(t\right)& =\frac{{t}^{2}\left(1-t{\right)}^{2}}{2n}\left({J}_{2n-2}\left(t\right){\right)}^{\prime \prime }+\left[\frac{\left(2n-1\right){t}^{2}\left(1-t\right)}{n}+\frac{t\left(1-t{\right)}^{2}}{n}\right]\left({J}_{2n-2}\left(t\right){\right)}^{\prime }\end{array}$
 $\begin{array}{cc}& +\left[\left(2n-1\right){t}^{2}+\frac{\left(2n-1\right)\left(1-t\right)t}{n}+\frac{\left(n-1\right)\left(1-t{\right)}^{2}}{n}\right]{J}_{2n-2}\left(t\right)\end{array}$
 $\begin{array}{cc}& =\frac{{t}^{4}-2{t}^{3}+{t}^{2}}{2n}\left({J}_{2n-2}\left(t\right){\right)}^{\prime \prime }+\left[\frac{\left(2-2n\right){t}^{3}}{n}+\frac{\left(2n-3\right){t}^{2}}{n}+\frac{t}{n}\right]\left({J}_{2n-2}\left(t\right){\right)}^{\prime }\end{array}$
 $\begin{array}{cc}& +\left[\left(2n-2\right){t}^{2}+\frac{t}{n}+\frac{n-1}{n}\right]{J}_{2n-2}\left(t\right).\end{array}$
 $\begin{array}{}\end{array}$
Therefore,
 $\begin{array}{cc}{J}_{2n,k}& =\frac{\left(k-2\right)\left(k-3\right)}{2n}{J}_{2n-2,k-2}-\frac{\left(k-1\right)\left(k-2\right)}{n}{J}_{2n-2,k-1}+\frac{k\left(k-1\right)}{2n}{J}_{2n-2,k}\end{array}$
 $\begin{array}{cc}& +\frac{\left(2-2n\right)\left(k-2\right)}{n}{J}_{2n-2,k-2}+\frac{\left(2n-3\right)\left(k-1\right)}{n}{J}_{2n-2,k-1}+\frac{k}{n}{J}_{2n-2,k}\end{array}$
 $\begin{array}{cc}& +\left(2n-2\right){J}_{2n-2,k-2}+\frac{1}{n}{J}_{2n-2,k-1}+\frac{n-1}{n}{J}_{2n-2,k}.\end{array}$
 $\begin{array}{}\end{array}$
After simplification, we obtain  2.1 .
Theorem 2.2 For $n\ge 3$  and $k\ge 0$  , the coefficients ${J}_{2n,k}$  satisfy the following recurrence formula:
 $\begin{array}{cc}n{I}_{n,k}& =\left(k+1\right){I}_{n-1,k}+\left(n-k\right){I}_{n-1,k-1}+\left[\left(k+1{\right)}^{2}+n-2\right]{I}_{n-2,k}\end{array}$
 $\begin{array}{cc}& +\left[2k\left(n-k-1\right)-n+3\right]{I}_{n-2,k-1}+\left[\left(n-k{\right)}^{2}+n-2\right]{I}_{n-2,k-2},\end{array}$ (2.3)
 $\begin{array}{}\end{array}$
where ${I}_{2n,k}=0$  if $k<0$  .
Proof. Extracting the coefficients of ${u}^{2n}$  in  1.1 , we obtain
 $\begin{array}{c}{g}_{n}\left(t\right):=\frac{{I}_{n}\left(t\right)}{\left(1-t{\right)}^{n+1}}={\sum }_{r=0}^{\infty }{t}^{r}{\sum }_{k=0}^{⌊n/2⌋}\left(\genfrac{}{}{0}{}{r\left(r+1\right)/2+k-1}{k}\right)\left(\genfrac{}{}{0}{}{r+n-2k}{n-2k}\right).\end{array}$ (2.4)
Let $T\left(n,k\right):=\left(\genfrac{}{}{0}{}{x+k-1}{k}\right)\left(\genfrac{}{}{0}{}{y-2k}{n-2k}\right),$  and $s\left(n\right):={\sum }_{k=0}^{⌊n/2⌋}T\left(n,k\right).$  Applying Zeilberger's algorithm, the Maple package ZeilbergerRecurrence(T,n,k,s,0..n) gives
 $\begin{array}{c}\left(2x+y+n+1\right)s\left(n\right)+\left(y+1\right)s\left(n+1\right)-\left(n+2\right)s\left(n+2\right)=0,\end{array}$ (2.5)
i.e., $s\left(n\right)=\frac{y+1}{n}s\left(n-1\right)+\frac{2x+y+n-1}{n}s\left(n-2\right).$  When $x=r\left(r+1\right)/2$  and $y=r$  , we get
 $\begin{array}{c}s\left(n\right)=\frac{r+1}{n}s\left(n-1\right)+\frac{r\left(r-1\right)+3r+n-1}{n}s\left(n-2\right).\end{array}$ (2.6)
Now, from  2.4 and  2.6 it follows that ${g}_{n}\left(t\right)=\frac{1}{n}\left[t{g}_{n-1}^{\prime }\left(t\right)+{g}_{n-1}\left(t\right)+{t}^{2}{g}_{n-2}^{\prime \prime }\left(t\right)+3t{g}_{n-2}^{\prime }\left(t\right)+\left(n-1\right){g}_{n-2}\left(t\right)\right].$  Namely,
 $\begin{array}{cc}\frac{n{I}_{n}\left(t\right)}{\left(1-t{\right)}^{n+1}}& =t{\left(\frac{{I}_{n-1}\left(t\right)}{\left(1-t{\right)}^{n}}\right)}^{\prime }+\frac{{I}_{n-1}\left(t\right)}{\left(1-t{\right)}^{n}}+{t}^{2}{\left(\frac{{I}_{n-2}\left(t\right)}{\left(1-t{\right)}^{n-1}}\right)}^{\prime \prime }+3t{\left(\frac{{I}_{n-2}\left(t\right)}{\left(1-t{\right)}^{n-1}}\right)}^{\prime }\end{array}$
 $\begin{array}{cc}& +\left(n-1\right)\frac{{I}_{n-2}\left(t\right)}{\left(1-t{\right)}^{n-1}},\end{array}$
 $\begin{array}{}\end{array}$
or
 $\begin{array}{cc}n{I}_{n}\left(t\right)& =\left(t-{t}^{2}\right){I}_{n-1}^{\prime }\left(t\right)+\left(1+\left(n-1\right)t\right){I}_{n-1}\left(t\right)+{t}^{2}\left(1-t{\right)}^{2}{I}_{n-2}^{\prime \prime }\left(t\right)\end{array}$
 $\begin{array}{cc}& +t\left(1-t\right)\left(3+\left(2n-5\right)t\right){I}_{n-2}^{\prime }\left(t\right)+\left(n-1\right)\left(1+t+\left(n-2\right){t}^{2}\right){I}_{n-2}\left(t\right).\end{array}$ (2.7)
 $\begin{array}{}\end{array}$
Comparing the coefficients of ${t}^{k}$  on both sides of  2.7 , we obtain
 $\begin{array}{cc}n{I}_{n,k}& =k{I}_{n-1,k}-\left(k-1\right){I}_{n-1,k-1}+{I}_{n-1,k}+\left(n-1\right){I}_{n-1,k-1}\end{array}$
 $\begin{array}{cc}& +k\left(k-1\right){I}_{n-2,k}-2\left(k-1\right)\left(k-2\right){I}_{n-2,k-1}+\left(k-2\right)\left(k-3\right){I}_{n-2,k-2}\end{array}$
 $\begin{array}{cc}& +3k{I}_{n-2,k}+\left(2n-8\right)\left(k-1\right){I}_{n-2,k-1}-\left(2n-5\right)\left(k-2\right){I}_{n-2,k-2}\end{array}$
 $\begin{array}{cc}& +\left(n-1\right){I}_{n-2,k}+\left(n-1\right){I}_{n-2,k-1}+\left(n-1\right)\left(n-2\right){I}_{n-2,k-2},\end{array}$
 $\begin{array}{}\end{array}$
which, after simplification, equals the right-hand side of  2.3 .
Remark. The recurrence formula  2.5 can also be proved by hand as follows. It is easy to see that the generating function for $s\left(n\right)$  is
 $\begin{array}{c}{\sum }_{n=0}^{\infty }s\left(n\right){u}^{n}=\left(1-{u}^{2}{\right)}^{-x}\left(1-u{\right)}^{-y-1}.\end{array}$ (2.8)
The derivation of $u$  on  2.8 implies that ${\sum }_{n=0}^{\infty }ns\left(n\right){u}^{n-1}=\left(\frac{2ux}{1-{u}^{2}}+\frac{y+1}{1-u}\right)\left(1-{u}^{2}{\right)}^{-x}\left(1-u{\right)}^{-y-1},$  namely,
 $\begin{array}{cc}\left(1-{u}^{2}\right){\sum }_{n=0}^{\infty }ns\left(n\right){u}^{n-1}& =\left(\left(2x+y+1\right)u+y+1\right)\left(1-{u}^{2}{\right)}^{-x}\left(1-u{\right)}^{-y-1}\end{array}$
 $\begin{array}{cc}& =\left(\left(2x+y+1\right)u+y+1\right){\sum }_{n=0}^{\infty }s\left(n\right){u}^{n}.\end{array}$ (2.9)
 $\begin{array}{}\end{array}$
Comparing the coefficients of ${u}^{n+1}$  on both sides of  2.9 , we obtain $\left(n+2\right)s\left(n+2\right)-ns\left(n\right)=\left(2x+y+1\right)s\left(n\right)+\left(y+1\right)s\left(n+1\right),$  which is formula  2.5 .
Since the right-hand side of  2.1 (resp.  2.3 ) is invariant under the substitution $k\to 2n-k$  (resp. $k\to n-1-k$  ), we derive straightforwardly from the recurrences  2.1 and  2.3 the known symmetry properties of ${J}_{2n,k}$  and ${I}_{n,k}$  (see [5, 9, 13).
Corollary 2.3 For $n,k\in \mathbb{N}$  , we have ${I}_{n,k}={I}_{n,n-1-k},{J}_{2n,k}={J}_{2n,2n-k}.$
It would be interesting to find a combinatorial proof of the recurrence formulas  2.1 and  2.3 , since such a proof could hopefully lead to a combinatorial proof of the unimodality of these two sequences.

3 Unimodality of the sequences ${I}_{n,k}$  and ${J}_{2n,k}$

The following observation is crucial in our inductive proof of the unimodality of ${I}_{n}\left(t\right)$  and ${J}_{2n}\left(t\right)$  .
Lemma 3.1 Let ${x}_{0},{x}_{1},\dots ,{x}_{n}$  and ${a}_{0},{a}_{1},\dots ,{a}_{n}$  be real numbers such that ${x}_{0}\ge {x}_{1}\ge \cdots \ge {x}_{n}\ge 0$  and ${a}_{0}+{a}_{1}+\cdots +{a}_{k}\ge 0$  for $k=0,1,\dots ,n.$  Then ${\sum }_{i=0}^{n}{a}_{i}{x}_{i}\ge 0.$
Indeed, the above inequality follows from the identity:
${\sum }_{i=0}^{n}{a}_{i}{x}_{i}={\sum }_{k=0}^{n}\left({x}_{k}-{x}_{k+1}\right)\left({a}_{0}+{a}_{1}+\cdots +{a}_{k}\right),$  where ${x}_{n+1}=0$  .
Theorem 3.2 The sequence ${J}_{2n,0},{J}_{2n,1},\dots ,{J}_{2n,2n-1}$  is unimodal.
Proof. By the symmetry of ${J}_{2n}\left(t\right)$  , it is enough to show that ${J}_{2n,k}\ge {J}_{2n,k-1}$  for all $1\le k\le n$  . We proceed by induction on $n$  . Clearly, ${J}_{2}\left(t\right)=t$  is trivial. Suppose the polynomial ${J}_{2n-2}\left(t\right)$  is unimodal. By Theorem  2.1 , one has
 $\begin{array}{cc}2n\left({J}_{2n,k}-{J}_{2n,k-1}\right)={A}_{0}{J}_{2n-2,k}+{A}_{1}{J}_{2n-2,k-1}+{A}_{2}{J}_{2n-2,k-2}+{A}_{3}{J}_{2n-2,k-3},& \end{array}$ (3.1)
 $\begin{array}{}\end{array}$
where
 $\begin{array}{cc}{A}_{0}& ={k}^{2}+k+2n-2,{A}_{1}=4nk-3{k}^{2}-6n+k+6,\end{array}$
 $\begin{array}{cc}{A}_{2}& =3{k}^{2}+4{n}^{2}-8nk-5k+12n-4,{A}_{3}=3k-{k}^{2}+4nk-4{n}^{2}-8n.\end{array}$
 $\begin{array}{}\end{array}$
We have the following two cases:
• If $1\le k\le n-1$  , then ${J}_{2n-2,k}\ge {J}_{2n-2,k-1}\ge {J}_{2n-2,k-2}\ge {J}_{2n-2,k-3}$  by the induction hypothesis, and clearly
 $\begin{array}{cc}& {A}_{0}\ge 0,{A}_{0}+{A}_{1}=\left(k-1\right)\left(2n-k\right)+2\ge 0,\end{array}$
 $\begin{array}{cc}& {A}_{0}+{A}_{1}+{A}_{2}=\left(2n-k{\right)}^{2}-3k+8n\ge 0,{A}_{0}+{A}_{1}+{A}_{2}+{A}_{3}=0.\end{array}$
 $\begin{array}{}\end{array}$
Therefore, by Theorem  3.1 , we have ${J}_{2n,k}-{J}_{2n,k-1}\ge 0.$
• If $k=n$  , then ${J}_{2n-2,n-1}\ge {J}_{2n-2,n}={J}_{2n-2,n-2}\ge {J}_{2n-2,n-3}$  by symmetry and the induction hypothesis, and clearly ${A}_{1}=\left(n-2\right)\left(n-3\right)\ge 0$  .
The corresponding condition of Theorem  3.1 is satisfied, and therefore ${J}_{2n,n}-{J}_{2n,n-1}\ge 0.$
This completes the proof.
Theorem 3.3 The sequence ${I}_{n,0},{I}_{n,1},\dots ,{I}_{n,n-1}$  is unimodal.
Proof. By the symmetry of ${I}_{n}\left(t\right)$  , it suffices to show that ${I}_{n,k}\ge {I}_{n,k-1}$  for all $1\le k\le \left(n-1\right)/2$  . From Table  1 , it is clear that the coefficients ${I}_{n,k}$  of the polynomials ${I}_{n}\left(x\right)$  are unimodal in $k$  for $1\le n\le 6$  .
Now suppose $n\ge 7$  and the polynomials ${I}_{n-1}\left(t\right)$  and ${I}_{n-2}\left(t\right)$  are unimodal. Replacing $k$  by $k-1$  in  2.3 , we obtain
 $\begin{array}{cc}n{I}_{n,k-1}& =k{I}_{n-1,k-1}+\left(n-k+1\right){I}_{n-1,k-2}+\left({k}^{2}+n-2\right){I}_{n-2,k-1}\end{array}$
 $\begin{array}{cc}& +\left[2\left(k-1\right)\left(n-k\right)-n+3\right]{I}_{n-2,k-2}+\left[\left(n-k+1{\right)}^{2}+n-2\right]{I}_{n-2,k-3}.\end{array}$ (3.2)
 $\begin{array}{}\end{array}$
Combining  2.3 and  3.2 yields
 $\begin{array}{cc}n\left({I}_{n,k}-{I}_{n,k-1}\right)& ={B}_{0}{I}_{n-1,k}+{B}_{1}{I}_{n-1,k-1}+{B}_{2}{I}_{n-1,k-2}\end{array}$
 $\begin{array}{cc}& +{C}_{0}{I}_{n-2,k}+{C}_{1}{I}_{n-2,k-1}+{C}_{2}{I}_{n-2,k-2}+{C}_{3}{I}_{n-2,k-3},\end{array}$ (3.3)
 $\begin{array}{}\end{array}$
where
 $\begin{array}{cc}{B}_{0}& =k+1,{B}_{1}=n-2k,{B}_{2}=-\left(n-k+1\right),\end{array}$
 $\begin{array}{cc}{C}_{0}& =\left(k+1{\right)}^{2}+n-2,{C}_{1}=2kn-3{k}^{2}-2k-2n+5,\end{array}$
 $\begin{array}{cc}{C}_{2}& ={n}^{2}-4kn+3{k}^{2}+4n-5-2k,{C}_{3}=-\left(n-k+1{\right)}^{2}-n+2.\end{array}$
 $\begin{array}{}\end{array}$
Notice that ${I}_{n-1,k}\ge {I}_{n-1,k-1}\ge {I}_{n-1,k-2}$  for $1\le k\le \left(n-1\right)/2$  . By Theorem  3.1 , we have
 $\begin{array}{c}{B}_{0}{I}_{n-1,k}+{B}_{1}{I}_{n-1,k-1}+{B}_{2}{I}_{n-1,k-2}\ge 0.\end{array}$ (3.4)
In what follows we will show that
 $\begin{array}{c}{C}_{0}{I}_{n-2,k}+{C}_{1}{I}_{n-2,k-1}+{C}_{2}{I}_{n-2,k-2}+{C}_{3}{I}_{n-2,k-3}\ge 0,\forall 1\le k\le \left(n-1\right)/2.\end{array}$ (3.5)
We have the following two cases:
• If $1\le k\le \left(n-2\right)/2$  , then ${I}_{n-2,k}\ge {I}_{n-2,k-1}\ge {I}_{n-2,k-2}\ge {I}_{n-2,k-3}$  by the induction hypothesis, and
 $\begin{array}{cc}& {C}_{0}=\left(k+1{\right)}^{2}+n-2\ge 0,{C}_{0}+{C}_{1}=\left(2k-1\right)\left(n-k-1\right)+k+3\ge 0,\end{array}$
 $\begin{array}{cc}& {C}_{0}+{C}_{1}+{C}_{2}=\left(n-k+1{\right)}^{2}+n-2\ge 0,{C}_{0}+{C}_{1}+{C}_{2}+{C}_{3}=0.\end{array}$
 $\begin{array}{}\end{array}$
• If $k=\left(n-1\right)/2$  , then by symmetry and the induction hypothesis, ${I}_{n-2,k-1}\ge {I}_{n-2,k}={I}_{n-2,k-2}\ge {I}_{n-2,k-3}.$  Notice that ${C}_{1}=\frac{\left(n-3\right)\left(n-7\right)}{4}\ge 0,\text{for}n\ge 7.$
Therefore, in any case, by Theorem  3.1 , the inequality  3.5 holds. It follows from  3.3 ,  3.4 and  3.5 that $n\left({I}_{n,k}-{I}_{n,k-1}\right)\ge 0,\forall 1\le k\le \left(n-1\right)/2.$  This completes the proof.

4 Further extensions and open problems

It is possible to combine the two recurrence formulae of ${I}_{n,k}$  and ${J}_{2n,k}$  by introducing one more parameter. Let $fix\left(\pi \right)$  be the number of fixed points of an involution $\pi \in {\Im }_{n}$  .
Then Désarménien and Foata [5derived the following generating function:
 $\begin{array}{cc}{\sum }_{n=0}^{\infty }{H}_{n}\left(z,t\right)\frac{{u}^{n}}{\left(1-t{\right)}^{n+1}}& ={\sum }_{r=0}^{\infty }\frac{{t}^{r}}{\left(1-zu{\right)}^{r+1}\left(1-{u}^{2}{\right)}^{r\left(r+1\right)/2}},\end{array}$ (4.1)
 $\begin{array}{}\end{array}$
where ${H}_{n}\left(z,t\right):={\sum }_{\pi \in {\Im }_{n}}{z}^{fix\left(\pi \right)}{t}^{d\left(\pi \right)}={\sum }_{k=0}^{n-1}{H}_{n,k}\left(z\right){t}^{k}.$  The first few values of ${H}_{n}:={H}_{n}\left(z,t\right)$  are given as follows:
 $\begin{array}{cc}{H}_{1}& =z,\end{array}$
 $\begin{array}{cc}{H}_{2}& ={z}^{2}+t,\end{array}$
 $\begin{array}{cc}{H}_{3}& ={z}^{3}+2zt+z{t}^{2},\end{array}$
 $\begin{array}{cc}{H}_{4}& ={z}^{4}+\left(1+3{z}^{2}\right)t+\left(1+3{z}^{2}\right){t}^{2}+{t}^{3},\end{array}$
 $\begin{array}{cc}{H}_{5}& ={z}^{5}+\left(2z+4{z}^{3}\right)t+\left(6z+6{z}^{3}\right){t}^{2}+6z{t}^{3}+z{t}^{4},\end{array}$
 $\begin{array}{cc}{H}_{6}& ={z}^{6}+\left(1+3{z}^{2}+5{z}^{4}\right)t+\left(3+15{z}^{2}+10{z}^{4}\right){t}^{2}+\left(7+21{z}^{2}\right){t}^{3}+\left(3+6{z}^{2}\right){t}^{4}+{t}^{5},\end{array}$
 $\begin{array}{cc}{H}_{7}& ={z}^{7}+\left(2z+4{z}^{3}+6{z}^{5}\right)t+\left(14z+28{z}^{3}+15{z}^{5}\right){t}^{2}+\left(40z+52{z}^{3}\right){t}^{3}+\left(36z+21{z}^{3}\right){t}^{4}+12z{t}^{5}+z{t}^{6}.\end{array}$
 $\begin{array}{}\end{array}$
Theorem 4.1 For $n\ge 4$  and $k\ge 0$  , there holds
 $\begin{array}{cc}& n{H}_{n,k}\left(z\right)\end{array}$
 $\begin{array}{cc}& =\left(n+k\right)z{H}_{n-1,k}\left(z\right)-\left(k-1\right)z{H}_{n-1,k-1}\left(z\right)+\left({k}^{2}+k+n-2\right){H}_{n-2,k}\left(z\right)\end{array}$
 $\begin{array}{cc}& +2\left(kn-{k}^{2}-n+2\right){H}_{n-2,k-1}\left(z\right)+\left({k}^{2}+{n}^{2}-2kn-k+2n-2\right){H}_{n-2,k-2}\left(z\right)\end{array}$
 $\begin{array}{cc}& -\left({k}^{2}+2k+n-2\right)z{H}_{n-3,k}\left(z\right)-\left(k-1\right)\left(2n-3k-7\right)z{H}_{n-3,k-1}\left(z\right)\end{array}$
 $\begin{array}{cc}& -\left(n-k-2\right)\left(n-3k+4\right)z{H}_{n-3,k-2}\left(z\right)-\left(2kn-{k}^{2}-{n}^{2}-n+3\right)z{H}_{n-3,k-3}\left(z\right),\end{array}$ (4.2)
 $\begin{array}{}\end{array}$
where ${H}_{n,k}\left(z\right)=0$  if $k<0$  .
Proof. Extracting the coefficients of ${u}^{2n}$  in  1.1 , we obtain
 $\begin{array}{c}{h}_{n}\left(z,t\right):=\frac{{H}_{n}\left(z,t\right)}{\left(1-t{\right)}^{n+1}}={\sum }_{r=0}^{\infty }{t}^{r}{\sum }_{k=0}^{⌊n/2⌋}\left(\genfrac{}{}{0}{}{r\left(r+1\right)/2+k-1}{k}\right)\left(\genfrac{}{}{0}{}{r+n-2k}{n-2k}\right){z}^{n-2k}.\end{array}$ (4.3)
Let $T\left(n,k\right):=\left(\genfrac{}{}{0}{}{x+k-1}{k}\right)\left(\genfrac{}{}{0}{}{y-2k}{n-2k}\right){z}^{n-2k},$  and $s\left(n\right):={\sum }_{k=0}^{⌊n/2⌋}T\left(n,k\right).$  Applying Zeilberger's algorithm, the Maple package ZeilbergerRecurrence(T,n,k,s,0..n) gives $-z\left(2x+y+n+1\right)s\left(n\right)+\left(n+2x+1\right)s\left(n+1\right)+z\left(n+y+3\right)s\left(n+2\right)-\left(n+3\right)s\left(n+3\right)=0,$  i.e., $ns\left(n\right)=z\left(n+y\right)s\left(n-1\right)+\left(n+2x-2\right)s\left(n-2\right)-z\left(2x+y+n-2\right)g\left(n-3\right).$  When $x=r\left(r+1\right)/2$  and $y=r$  , we get
 $\begin{array}{c}ns\left(n\right)=z\left(r+n\right)s\left(n-1\right)+\left[r\left(r-1\right)+2r+n-2\right]s\left(n-2\right)-z\left[r\left(r-1\right)+3r+n-2\right]s\left(n-3\right).\end{array}$ (4.4)
Now, from  4.3 and  4.4 it follows that
 $\begin{array}{cc}n{h}_{n}\left(z,t\right)& =zt\frac{\partial }{\partial t}{h}_{n-1}\left(t\right)+nz{h}_{n-1}\left(z,t\right)+{t}^{2}\frac{{\partial }^{2}}{\partial {t}^{2}}{h}_{n-2}\left(z,t\right)+2t\frac{\partial }{\partial t}{h}_{n-2}\left(z,t\right)\end{array}$
 $\begin{array}{cc}& +\left(n-2\right){h}_{n-2}\left(z,t\right)-z{t}^{2}\frac{{\partial }^{2}}{\partial {t}^{2}}{h}_{n-3}\left(z,t\right)-3zt\frac{\partial }{\partial t}{h}_{n-3}\left(z,t\right)-\left(n-2\right)z{h}_{n-3}\left(z,t\right).\end{array}$
 $\begin{array}{}\end{array}$
Namely,
 $\begin{array}{cc}n{H}_{n}\left(z,t\right)& =zt\left(1-t\right)\frac{\partial }{\partial t}{H}_{n-1}\left(z,t\right)+nz{H}_{n-1}\left(z,t\right)+{t}^{2}\left(1-t{\right)}^{2}\frac{{\partial }^{2}}{\partial {t}^{2}}{H}_{n-2}\left(z,t\right)\end{array}$
 $\begin{array}{cc}& +2t\left(1-t\right)\left[1+\left(n-2\right)t\right]\frac{\partial }{\partial t}{H}_{n-2}\left(z,t\right)+\left[n-2+2t+\left({n}^{2}-2n\right){t}^{2}\right]{H}_{n-2}\left(z,t\right)\end{array}$
 $\begin{array}{cc}& -z{t}^{2}\left(1-t{\right)}^{3}\frac{{\partial }^{2}}{\partial {t}^{2}}{H}_{n-3}\left(z,t\right)-zt\left(1-t{\right)}^{2}\left[3+\left(2n-7\right)t\right]\frac{\partial }{\partial t}{H}_{n-3}\left(z,t\right)\end{array}$
 $\begin{array}{cc}& -\left(n-2\right)z\left(1-t\right)\left[1+t+\left(n-3\right){t}^{2}\right]{H}_{n-3}\left(z,t\right).\end{array}$
 $\begin{array}{}\end{array}$
Comparing the coefficients of ${t}^{k}$  on both sides yields  4.2 .
Remark. When $z=0$  we recover directly the recurrence formula for ${I}_{n,k}$  , while for $z=1$  it gives a recurrence formula for ${J}_{2n,k}$  of third order.
Since ${I}_{n,k}={I}_{n,n-1-k}$  , we can write ${I}_{n}\left(t\right)$  as following
 $\begin{array}{cc}{I}_{n}\left(x\right)={\sum }_{k=0}^{n-1}{I}_{n,k}{x}^{k}=\left\{\begin{array}{cc}{\sum }_{k=0}^{n/2-1}{I}_{n,k}{x}^{k}\left(1+{x}^{n-2k-1}\right),& \text{if}n\text{is even,}\\ {\sum }_{k=0}^{\left(n-3\right)/2}{I}_{n,k}{x}^{k}\left(1+{x}^{n-2k-1}\right)+{I}_{n,\left(n-1\right)/2}{x}^{\left(n-1\right)/2},& \text{if}n\text{is odd.}\end{array}& \end{array}$
 $\begin{array}{}\end{array}$
Applying the well-known formula ${x}^{n}+{y}^{n}={\sum }_{j=0}^{⌊n/2⌋}\left(-1{\right)}^{j}\frac{n}{n-j}\left(\genfrac{}{}{0}{}{n-j}{j}\right)\left(xy{\right)}^{j}\left(x+y{\right)}^{n-2j},$  we obtain
 $\begin{array}{cc}{I}_{n}\left(t\right)={\sum }_{k=0}^{⌊\left(n-1\right)/2⌋}{a}_{n,k}{t}^{k}\left(1+t{\right)}^{n-2k-1},& \end{array}$ (4.5)
 $\begin{array}{}\end{array}$
where ${a}_{n,k}=\left\{\begin{array}{cc}{\sum }_{j=0}^{k}\left(-1{\right)}^{k-j}\frac{n-2j-1}{n-k-j-1}\left(\genfrac{}{}{0}{}{n-k-j-1}{k-j}\right){I}_{n,j},& \text{if}2k+1  The first values of ${a}_{n,k}$  are given in Table  2 , which seems to suggest the following
Conjecture 4.2 For $n\ge 1$  and $k\ge 0$  , the coefficients ${a}_{n,k}$  are nonnegative integers.
 $k\n$ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 2 4 6 9 12 16 20 25 30 36 42 49 2 2 6 18 39 79 141 239 379 579 849 1211 1680 3 0 18 78 272 722 1716 3626 7160 13206 23263 4 20 124 668 2560 8360 23536 59824 139457 5 32 700 4800 24160 95680 325572 6 440 5480 44632 257964 7 2176 44376
Since the coefficients of ${t}^{k}\left(1+t{\right)}^{n-2k-1}$  are symmetric and unimodal with center of symmetry at $\left(n-1\right)/2$  , the above conjecture, if true, is stronger than the fact that ${I}_{n}\left(t\right)$  is symmetric and unimodal. A more interesting question would be giving a combinatorial interpretation of ${a}_{n,k}$  . Note that the Eulerian polynomials can be written as ${A}_{n}\left(t\right)={\sum }_{k=1}^{⌊\left(n+1\right)/2⌋}{c}_{n,k}{t}^{k}\left(1+t{\right)}^{n-2k+1},$  where ${c}_{n,k}$  is the number of increasing binary trees on $\left[n\right]$  with $k$  leaves and no vertices having left children only (see [2, 7, 8).
We now proceed to derive a recurrence relation for ${a}_{n,k}$  . In  4.12 set $x=x\left(t\right)=t/\left(1+t{\right)}^{2}$  and ${P}_{n}\left(x\right)={\sum }_{k=0}^{⌊\left(n-1\right)/2⌋}{a}_{n,k}{x}^{k},$  then we can rewrite  4.12 as
 $\begin{array}{c}{I}_{n}\left(t\right)=\left(1+t{\right)}^{n-1}{P}_{n}\left(x\right).\end{array}$ (4.6)
Differentiating  4.6 with respect to $t$  we get
 $\begin{array}{cc}{I}_{n}^{\prime }\left(t\right)& =\left(n-1\right)\left(1+t{\right)}^{n-2}{P}_{n}\left(x\right)+\left(1+t{\right)}^{n-1}{P}_{n}^{\prime }\left(x\right){x}^{\prime }\left(t\right),\end{array}$ (4.7)
 $\begin{array}{cc}{I}_{n}^{\prime \prime }\left(t\right)& =\left(n-1\right)\left(n-2\right)\left(1+t{\right)}^{n-3}{P}_{n}\left(x\right)+2\left(n-1\right)\left(1+t{\right)}^{n-2}{P}_{n}^{\prime }\left(x\right){x}^{\prime }\left(t\right)\end{array}$
 $\begin{array}{cc}& +\left(1+t{\right)}^{n-1}{P}_{n}^{\prime \prime }\left(x\right)\left({x}^{\prime }\left(t\right){\right)}^{2}+\left(1+t{\right)}^{n-1}{P}_{n}^{\prime }\left(x\right){x}^{\prime \prime }\left(t\right),\end{array}$ (4.8)
 $\begin{array}{cc}{x}^{\prime }\left(t\right)& =\frac{1-t}{\left(1+t{\right)}^{3}},{x}^{\prime \prime }\left(t\right)=\frac{2t-4}{\left(1+t{\right)}^{4}}.\end{array}$ (4.9)
 $\begin{array}{}\end{array}$
Substituting  4.6  4.9 into  2.7 , we obtain
 $\begin{array}{cc}& n\left(1+t{\right)}^{n-1}{P}_{n}\left(x\right)\end{array}$
 $\begin{array}{cc}& =\left(1+\left(2n-2\right)t+{t}^{2}\right)\left(1+t{\right)}^{n-3}{P}_{n-1}\left(x\right)+t\left(1-t{\right)}^{2}\left(1+t{\right)}^{n-5}{P}_{n-1}^{\prime }\left(x\right)\end{array}$
 $\begin{array}{cc}& +\left[-\left({t}^{2}+14t+1\right)\left(1-t{\right)}^{2}+\left(1+6t-18{t}^{2}+6{t}^{3}+{t}^{4}\right)n+4{t}^{2}{n}^{2}\right]\left(1+t{\right)}^{n-5}{P}_{n-2}\left(x\right)\end{array}$
 $\begin{array}{cc}& +\left[3t\left({t}^{2}-4t+1\right)\left(1-t{\right)}^{2}+4{t}^{2}\left(1-t{\right)}^{2}n\right]\left(1+t{\right)}^{n-7}{P}_{n-2}^{\prime }\left(x\right)\end{array}$
 $\begin{array}{cc}& +{t}^{2}\left(1-t{\right)}^{4}\left(1+t{\right)}^{n-9}{P}_{n-2}^{\prime \prime }\left(x\right).\end{array}$ (4.10)
 $\begin{array}{}\end{array}$
Dividing the two sides of  4.10 by $\left(1+t{\right)}^{n-1}$  and noticing that $t/\left(1+t{\right)}^{2}=x$  , we get after a little manipulation
 $\begin{array}{cc}n{P}_{n}\left(x\right)& =\left[1+\left(2n-4\right)x\right]{P}_{n-1}\left(x\right)+\left(x-4{x}^{2}\right){P}_{n-1}^{\prime }\left(x\right)\end{array}$
 $\begin{array}{cc}& +\left[\left(n-1\right)+\left(2n-8\right)x+4\left(n-3\right)\left(n-4\right){x}^{2}\right]{P}_{n-2}\left(x\right)\end{array}$
 $\begin{array}{cc}& +\left[3x+\left(4n-30\right){x}^{2}+\left(72-16n\right){x}^{3}\right]{P}_{n-2}^{\prime }\left(x\right)+\left({x}^{2}-8{x}^{3}+16{x}^{4}\right){P}_{n-2}^{\prime \prime }\left(x\right).\end{array}$
 $\begin{array}{}\end{array}$
Extracting the coefficients of ${x}^{k}$  yields
 $\begin{array}{cc}n{a}_{n,k}& ={a}_{n-1,k}+\left(2n-4\right){a}_{n-1,k-1}+k{a}_{n-1,k}-4\left(k-1\right){a}_{n-1,k-1}\end{array}$
 $\begin{array}{cc}& +\left(n-1\right){a}_{n-2,k}+\left(2n-8\right){a}_{n-2,k-1}+4\left(n-3\right)\left(n-4\right){a}_{n-2,k-2}\end{array}$
 $\begin{array}{cc}& +3k{a}_{n-2,k}+\left(4n-30\right)\left(k-1\right){a}_{n-2,k-1}+\left(72-16n\right)\left(k-2\right){a}_{n-2,k-2}\end{array}$
 $\begin{array}{cc}& +k\left(k-1\right){a}_{n-2,k}-8\left(k-1\right)\left(k-2\right){a}_{n-2,k-1}+16\left(k-2\right)\left(k-3\right){a}_{n-2,k-2}.\end{array}$
 $\begin{array}{}\end{array}$
After simplification, we obtain the following recurrence formula for ${a}_{n,k}$  .
Theorem 4.3 For $n\ge 3$  and $k\ge 0$  , there holds
 $\begin{array}{cc}n{a}_{n,k}& =\left(k+1\right){a}_{n-1,k}+\left(2n-4k\right){a}_{n-1,k-1}+\left[k\left(k+2\right)+n-1\right]{a}_{n-2,k}\end{array}$
 $\begin{array}{cc}& +\left[\left(k-1\right)\left(4n-8k-14\right)+2n-8\right]{a}_{n-2,k-1}+4\left(n-2k\right)\left(n-2k+1\right){a}_{n-2,k-2},\end{array}$ (4.11)
 $\begin{array}{}\end{array}$
where ${a}_{n,k}=0$  if $k<0$  .
By  4.12 , ${a}_{n,k}=0$  if $n\le 2k$  . On the other hand, if $n\ge 2k+3$  , then $\left(k-1\right)\left(4n-8k-14\right)+2n-8>0\text{for any}k\ge 1\text{,}$  and so are the other coefficients in  4.11 . Therefore, by Theorem  4.3 , Conjecture  4.2 would be proved if one can show that ${a}_{2n+1,n},{a}_{2n+2,n}\ge 0$  .
Finally, from  4.12 it is easy to see that
 $\begin{array}{cc}{a}_{2n+1,n}& =\left(-1{\right)}^{n}{I}_{2n+1}\left(-1\right)={\sum }_{k=0}^{2n}\left(-1{\right)}^{n-k}{I}_{2n+1,k},\end{array}$
 $\begin{array}{cc}{a}_{2n+2,n}& =\left(-1{\right)}^{n}{I}_{2n+2}^{\prime }\left(-1\right)={\sum }_{k=1}^{2n+1}\left(-1{\right)}^{n+1-k}k{I}_{2n+2,k}.\end{array}$
 $\begin{array}{}\end{array}$
Thus, Conjecture  4.2 is equivalent to the nonnegativity of the above two alternating sums.
Since ${J}_{n,k}={J}_{n,n-k}$  , in the same manner, we obtain
 $\begin{array}{cc}{J}_{2n}\left(t\right)={\sum }_{k=1}^{n}{b}_{2n,k}{t}^{k}\left(1+t{\right)}^{n-2k},& \end{array}$ (4.12)
 $\begin{array}{}\end{array}$
where ${b}_{2n,k}=\left\{\begin{array}{cc}{\sum }_{j=0}^{k}\left(-1{\right)}^{k-j}\frac{2n-2j}{2n-k-j}\left(\genfrac{}{}{0}{}{2n-k-j}{k-j}\right){J}_{2n,j},& \text{if}k  Now, it follows from  2.2 that
 $\begin{array}{cc}{J}_{2n,k}={\sum }_{i=0}^{k}\left(-1{\right)}^{k-i}\left(\genfrac{}{}{0}{}{2n+1}{k-i}\right)\left(\genfrac{}{}{0}{}{i\left(i+1\right)/2+n-1}{i\left(i+1\right)/2-1}\right)& \end{array}$
 $\begin{array}{}\end{array}$
is a polynomial in $n$  of degree $d:=k\left(k+1\right)/2-1$  with leading coefficient $1/d!$  , and so is ${b}_{2n,k}$  . Thus, we have ${lim}_{n\to \infty }{b}_{2n,k}=\infty$  for any $k$  . The first values of ${b}_{2n,k}$  are given in Table  3 , which seems to suggest
Conjecture 4.4 For $n\ge 9$  and $k\ge 1$  , the coefficients ${b}_{2n,k}$  are nonnegative integers.
 $k\2n$ 2 4 6 8 10 12 14 16 18 20 22 24 1 1 1 1 1 1 1 1 1 1 1 1 1 2 -1 -1 0 2 5 9 14 20 27 35 44 3 3 12 36 91 201 399 728 1242 2007 3102 4 -7 -10 91 652 2593 7902 20401 46852 98494 5 25 219 1710 10532 50165 194139 639968 1861215 6 -65 249 11319 122571 841038 4377636 18747924 7 283 6586 135545 1737505 15219292 101116704 8 -583 33188 1372734 24412940 277963127 9 4417 379029 16488999 367507439 10 1791 3350211 203698690 11 133107 36903128 12 761785
Similarly to the proof of Theorem  4.3 , we can prove the following
Theorem 4.5 For $n\ge 2$  and $k\ge 1$  , there holds
 $\begin{array}{cc}2n{b}_{2n,k}& =\left[k\left(k+1\right)+2n-2\right]{b}_{2n-2,k}+\left[2+2\left(k-1\right)\left(4n-4k-3\right)\right]{b}_{2n-2,k-1}\end{array}$
 $\begin{array}{cc}& +8\left(n-k+1\right)\left(2n-2k+1\right){b}_{2n-2,k-2}.\end{array}$
 $\begin{array}{}\end{array}$
where ${b}_{2n,k}=0$  if $k<1$  .
Theorem  4.5 allows us to reduce the verification of Conjecture  4.4 to the boundary case ${b}_{2n,n}\ge 0$  for $n\ge 9$  .
Acknowledgment. The second author was supported by EC's IHRP Programme, within Research Training Network “Algebraic Combinatorics in Europe,” grant HPRN-CT-2001-00272. References

1. M. Bóna and R. Ehrenborg, A combinatorial proof of the log-concavity of the numbers of permutations with $k$  runs, J. Combin. Theory Ser. A 90 (2000), 293–303.
2. P. Brändén, Sign-graded posets, unimodality of $W$  -polynomials and the Charney-Davis conjecture, Electron. J. Combin. 11 (2) (2004/05), #R9.
3. F. Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, Jerusalem combinatorics'93, pp. 71–89, Contemp. Math., 178, Amer. Math. Soc., Providence, RI, 1994.
4. L. Comtet, Advanced Combinatorics, Reidel, Dordrecht/Boston, 1974.
5. J. Désarménien and D. Foata, Fonctions symétriques et séries hypergéométriques basiques multivariées, Bull. Soc. Math. France 113 (1985), 3–22.
6. W. M. B. Dukes, Permutation statistics on involutions, preprint, arXiv: math.CO/0412222.
7. D. Foata and V. Strehl, Euler numbers and variations of permutations, Atti dei Convegni Lincei, 17 Tomo I, 1976, pp. 119–131.
8. V. Gasharov, On the Neggers-Stanley conjecture and the Eulerian polynomials, J. Combin. Theory Ser. A 82 (1998), 134–146.
9. I. M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A 64 (1993), 189–215.
10. D. C. Kurtz, A note on concavity properties of triangular arrays of numbers, J. Combin. Theory Ser. A 13 (1972), 135–139.
11. R. P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Ann. New York Acad. Sci. 576 (1989), 500–535.
12. J. R. Stembridge, Eulerian numbers, tableaux, and the Betti numbers of a toric variety, Discrete Math. 99 (1992), 307–320.
13. V. Strehl, Symmetric Eulerian distributions for involutions, Séminair Lotharingien Combinatoire 1, Strasbourg 1980, Publications de l'I.R.M.A. 140/S-02, Strasbourg, 1981.