The Eulerian Distribution on Involutions is Indeed Unimodal

Victor J. W. Guo 1 and Jiang Zeng 2

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 2 n , k   ), which implies that the sequence I n , k   (resp. J 2 n , k   ) is unimodal in k   , for all n   . We also propose some open problems related to I n , k   and J 2 n , k   .
AMS Subject Classifications (2000): Primary 05A15; Secondary 05A20.

1 Introduction

A sequence a 0 , a 1 , … , a n   of real numbers is said to be unimodal if for some 0 ≤ j ≤ n   we have a 0 ≤ a 1 ≤ ⋯ ≤ a j ≥ a j + 1 ≥ ⋯ ≥ a n   , and is said to be log-concave if a i 2 ≥ a i − 1 a i + 1   for all 1 ≤ i ≤ n − 1   . Clearly a log-concave sequence of positive terms is unimodal. The reader is referred to Stanley's survey [11] for 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 S n   be the set of permutations of [ n ] : = { 1 , … , n }   . A permutation π = a 1 a 2 ⋯ a n ∈ S n   has a descent at i   ( 1 ≤ i ≤ n − 1   ) if a i > a i + 1   . The number of descents of π   is called descent number and is denoted by d ( π )   . A statistic on 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 S n   is the Eulerian polynomial A n ( t ) = ∑ π ∈ S n t 1 + d ( π ) = ∑ k = 1 n A ( n , k ) t k .   It is well-known that the Eulerian numbers A ( n , k )   ( 0 ≤ k ≤ n   ) form a unimodal sequence, of which several proofs have been published: such as the analytical one by showing that the polynomial A n ( t )   has only real zeros [4,p.294] , by induction based on the recurrence relation of A ( n , k )   (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 ℑ n   be the set of involutions in S n   and J 2 n   the set of involutions without fixed points in S 2 n   . Define
I n ( t ) = ∑ π ∈ ℑ n t d ( π ) = ∑ k = 0 n − 1 I n , k t k ,
J 2 n ( t ) = ∑ π ∈ J 2 n t d ( π ) = ∑ k = 0 2 n − 1 J 2 n , k t k ,
The first values of these polynomials are given in Table 1.
Table 1 : The polynomials I n ( t )   and J n ( t )   for n ≤ 6   .
n   I n ( t )   J n ( t )  
1 1 0
2 1 + t   t  
3 1 + 2 t + t 2   0
4 1 + 4 t + 4 t 2 + t 3   t + t 2 + t 3  
5 1 + 6 t + 12 t 2 + 6 t 3 + t 4   0
6 1 + 9 t + 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 ( t )   and J n ( t )   are symmetric and unimodal for 1 ≤ n ≤ 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 ( t )   are log-concave and Dukes [6] has obtained some partial results on the unimodality of the coefficients of I n ( t )   and J 2 n ( t )   . Note that, in contrast to Eulerian polynomials A n ( t )   , the polynomials I n ( t )   and J 2 n ( t )   may have non-real zeros.
In this paper we will prove that for n ≥ 1   , the two sequences I n , 0 , I n , 1 , … , I n , n − 1   and J 2 n , 1 , J 2 n , 1 , … , J 2 n , 2 n − 1   are unimodal (cf. Theorems 3.2 and 3.3). Our starting point is the known generating functions of the polynomials I n ( t )   and J 2 n ( t )   :
∑ n = 0 ∞ I n ( t ) u n ( 1 − t ) n + 1 = ∑ r = 0 ∞ t r ( 1 − u ) r + 1 ( 1 − u 2 ) r ( r + 1 ) / 2 , (1.1)
∑ n = 0 ∞ J n ( t ) u n ( 1 − t ) n + 1 = ∑ r = 0 ∞ t r ( 1 − u 2 ) r ( r + 1 ) / 2 , (1.2)
which have been obtained by Désarménien and Foata [5] and Gessel and Reutenauer [9] using different methods. We first derive the linear recurrence formulas for I n , k   and J 2 n , 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 2 n , k  

Since the recurrence formula for the coefficients I n , k   is a little more complicated than J 2 n , k   , we shall first prove that for J 2 n , k   .
Theorem 2.1 For n ≥ 2   and k ≥ 0   , the coefficients J 2 n , k   satisfy the following recurrence formula:
2 n J 2 n , k = [ k ( k + 1 ) + 2 n − 2 ] J 2 n − 2 , k + 2 [ ( k − 1 ) ( 2 n − k − 1 ) + 1 ] J 2 n − 2 , k − 1
+ [ ( 2 n − k ) ( 2 n − k + 1 ) + 2 n − 2 ] J 2 n − 2 , k − 2 , (2.1)
where J 2 n , k = 0   if k < 0   .
Proof. Equating the coefficients of u 2 n   on both sides of  1.2 , we obtain
f n ( t ) : = J 2 n ( t ) ( 1 − t ) 2 n + 1 = ∑ r = 0 ∞ ( r ( r + 1 ) / 2 + n − 1 n ) t r . (2.2)
Since ( r ( r + 1 ) / 2 + n − 1 n ) = r ( r − 1 ) / 2 + r + n − 1 n ( r ( r + 1 ) / 2 + n − 2 n − 1 ) ,   it follows from  2.2 that
f n ( t ) = t 2 2 n f n − 1 ′ ′ ( t ) + t n f n − 1 ′ ( t ) + n − 1 n f n − 1 ( t ) .
Namely, J 2 n ( t ) ( 1 − t ) 2 n + 1 = t 2 2 n ( J 2 n − 2 ( t ) ( 1 − t ) 2 n − 1 ) ′ ′ + t n ( J 2 n − 2 ( t ) ( 1 − t ) 2 n − 1 ) ′ + n − 1 n J 2 n − 2 ( t ) ( 1 − t ) 2 n − 1 ,   or
J 2 n ( t ) = t 2 ( 1 − t ) 2 2 n ( J 2 n − 2 ( t ) ) ′ ′ + [ ( 2 n − 1 ) t 2 ( 1 − t ) n + t ( 1 − t ) 2 n ] ( J 2 n − 2 ( t ) ) ′
+ [ ( 2 n − 1 ) t 2 + ( 2 n − 1 ) ( 1 − t ) t n + ( n − 1 ) ( 1 − t ) 2 n ] J 2 n − 2 ( t )
= t 4 − 2 t 3 + t 2 2 n ( J 2 n − 2 ( t ) ) ′ ′ + [ ( 2 − 2 n ) t 3 n + ( 2 n − 3 ) t 2 n + t n ] ( J 2 n − 2 ( t ) ) ′
+ [ ( 2 n − 2 ) t 2 + t n + n − 1 n ] J 2 n − 2 ( t ) .
Therefore,
J 2 n , k = ( k − 2 ) ( k − 3 ) 2 n J 2 n − 2 , k − 2 − ( k − 1 ) ( k − 2 ) n J 2 n − 2 , k − 1 + k ( k − 1 ) 2 n J 2 n − 2 , k
+ ( 2 − 2 n ) ( k − 2 ) n J 2 n − 2 , k − 2 + ( 2 n − 3 ) ( k − 1 ) n J 2 n − 2 , k − 1 + k n J 2 n − 2 , k
+ ( 2 n − 2 ) J 2 n − 2 , k − 2 + 1 n J 2 n − 2 , k − 1 + n − 1 n J 2 n − 2 , k .
After simplification, we obtain  2.1 .
Theorem 2.2 For n ≥ 3   and k ≥ 0   , the coefficients J 2 n , k   satisfy the following recurrence formula:
n I n , k = ( k + 1 ) I n − 1 , k + ( n − k ) I n − 1 , k − 1 + [ ( k + 1 ) 2 + n − 2 ] I n − 2 , k
+ [ 2 k ( n − k − 1 ) − n + 3 ] I n − 2 , k − 1 + [ ( n − k ) 2 + n − 2 ] I n − 2 , k − 2 , (2.3)
where I 2 n , k = 0   if k < 0   .
Proof. Extracting the coefficients of u 2 n   in  1.1 , we obtain
g n ( t ) : = I n ( t ) ( 1 − t ) n + 1 = ∑ r = 0 ∞ t r ∑ k = 0 ⌊ n / 2 ⌋ ( r ( r + 1 ) / 2 + k − 1 k ) ( r + n − 2 k n − 2 k ) . (2.4)
Let T ( n , k ) : = ( x + k − 1 k ) ( y − 2 k n − 2 k ) ,   and s ( n ) : = ∑ k = 0 ⌊ n / 2 ⌋ T ( n , k ) .   Applying Zeilberger's algorithm, the Maple package ZeilbergerRecurrence(T,n,k,s,0..n) gives
( 2 x + y + n + 1 ) s ( n ) + ( y + 1 ) s ( n + 1 ) − ( n + 2 ) s ( n + 2 ) = 0 , (2.5)
i.e., s ( n ) = y + 1 n s ( n − 1 ) + 2 x + y + n − 1 n s ( n − 2 ) .   When x = r ( r + 1 ) / 2   and y = r   , we get
s ( n ) = r + 1 n s ( n − 1 ) + r ( r − 1 ) + 3 r + n − 1 n s ( n − 2 ) . (2.6)
Now, from  2.4 and  2.6 it follows that g n ( t ) = 1 n [ t g n − 1 ′ ( t ) + g n − 1 ( t ) + t 2 g n − 2 ′ ′ ( t ) + 3 t g n − 2 ′ ( t ) + ( n − 1 ) g n − 2 ( t ) ] .   Namely,
n I n ( t ) ( 1 − t ) n + 1 = t ( I n − 1 ( t ) ( 1 − t ) n ) ′ + I n − 1 ( t ) ( 1 − t ) n + t 2 ( I n − 2 ( t ) ( 1 − t ) n − 1 ) ′ ′ + 3 t ( I n − 2 ( t ) ( 1 − t ) n − 1 ) ′
+ ( n − 1 ) I n − 2 ( t ) ( 1 − t ) n − 1 ,
or
n I n ( t ) = ( t − t 2 ) I n − 1 ′ ( t ) + ( 1 + ( n − 1 ) t ) I n − 1 ( t ) + t 2 ( 1 − t ) 2 I n − 2 ′ ′ ( t )
+ t ( 1 − t ) ( 3 + ( 2 n − 5 ) t ) I n − 2 ′ ( t ) + ( n − 1 ) ( 1 + t + ( n − 2 ) t 2 ) I n − 2 ( t ) . (2.7)
Comparing the coefficients of t k   on both sides of  2.7 , we obtain
n I n , k = k I n − 1 , k − ( k − 1 ) I n − 1 , k − 1 + I n − 1 , k + ( n − 1 ) I n − 1 , k − 1
+ k ( k − 1 ) I n − 2 , k − 2 ( k − 1 ) ( k − 2 ) I n − 2 , k − 1 + ( k − 2 ) ( k − 3 ) I n − 2 , k − 2
+ 3 k I n − 2 , k + ( 2 n − 8 ) ( k − 1 ) I n − 2 , k − 1 − ( 2 n − 5 ) ( k − 2 ) I n − 2 , k − 2
+ ( n − 1 ) I n − 2 , k + ( n − 1 ) I n − 2 , k − 1 + ( n − 1 ) ( n − 2 ) I n − 2 , k − 2 ,
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 ( n )   is
∑ n = 0 ∞ s ( n ) u n = ( 1 − u 2 ) − x ( 1 − u ) − y − 1 . (2.8)
The derivation of u   on  2.8 implies that ∑ n = 0 ∞ n s ( n ) u n − 1 = ( 2 u x 1 − u 2 + y + 1 1 − u ) ( 1 − u 2 ) − x ( 1 − u ) − y − 1 ,   namely,
( 1 − u 2 ) ∑ n = 0 ∞ n s ( n ) u n − 1 = ( ( 2 x + y + 1 ) u + y + 1 ) ( 1 − u 2 ) − x ( 1 − u ) − y − 1
= ( ( 2 x + y + 1 ) u + y + 1 ) ∑ n = 0 ∞ s ( n ) u n . (2.9)
Comparing the coefficients of u n + 1   on both sides of  2.9 , we obtain ( n + 2 ) s ( n + 2 ) − n s ( n ) = ( 2 x + y + 1 ) s ( n ) + ( y + 1 ) s ( n + 1 ) ,   which is formula  2.5 .
Since the right-hand side of  2.1 (resp.  2.3 ) is invariant under the substitution k → 2 n − k   (resp. k → n − 1 − k   ), we derive straightforwardly from the recurrences  2.1 and  2.3 the known symmetry properties of J 2 n , k   and I n , k   (see [5, 9, 13] ).
Corollary 2.3 For n , k ∈ N   , we have I n , k = I n , n − 1 − k , J 2 n , k = J 2 n , 2 n − 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 2 n , k  

The following observation is crucial in our inductive proof of the unimodality of I n ( t )   and J 2 n ( t )   .
Lemma 3.1 Let x 0 , x 1 , … , x n   and a 0 , a 1 , … , a n   be real numbers such that x 0 ≥ x 1 ≥ ⋯ ≥ x n ≥ 0   and a 0 + a 1 + ⋯ + a k ≥ 0   for k = 0 , 1 , … , n .   Then ∑ i = 0 n a i x i ≥ 0 .  
Indeed, the above inequality follows from the identity:
∑ i = 0 n a i x i = ∑ k = 0 n ( x k − x k + 1 ) ( a 0 + a 1 + ⋯ + a k ) ,   where x n + 1 = 0   .
Theorem 3.2 The sequence J 2 n , 0 , J 2 n , 1 , … , J 2 n , 2 n − 1   is unimodal.
Proof. By the symmetry of J 2 n ( t )   , it is enough to show that J 2 n , k ≥ J 2 n , k − 1   for all 1 ≤ k ≤ n   . We proceed by induction on n   . Clearly, J 2 ( t ) = t   is trivial. Suppose the polynomial J 2 n − 2 ( t )   is unimodal. By Theorem  2.1 , one has
2 n ( J 2 n , k − J 2 n , k − 1 ) = A 0 J 2 n − 2 , k + A 1 J 2 n − 2 , k − 1 + A 2 J 2 n − 2 , k − 2 + A 3 J 2 n − 2 , k − 3 , (3.1)
where
A 0 = k 2 + k + 2 n − 2 , A 1 = 4 n k − 3 k 2 − 6 n + k + 6 ,
A 2 = 3 k 2 + 4 n 2 − 8 n k − 5 k + 12 n − 4 , A 3 = 3 k − k 2 + 4 n k − 4 n 2 − 8 n .
We have the following two cases:
  • ∙ If 1 ≤ k ≤ n − 1   , then J 2 n − 2 , k ≥ J 2 n − 2 , k − 1 ≥ J 2 n − 2 , k − 2 ≥ J 2 n − 2 , k − 3   by the induction hypothesis, and clearly
    A 0 ≥ 0 , A 0 + A 1 = ( k − 1 ) ( 2 n − k ) + 2 ≥ 0 ,
    A 0 + A 1 + A 2 = ( 2 n − k ) 2 − 3 k + 8 n ≥ 0 , A 0 + A 1 + A 2 + A 3 = 0 .
    Therefore, by Theorem  3.1 , we have J 2 n , k − J 2 n , k − 1 ≥ 0 .  
  • ∙ If k = n   , then J 2 n − 2 , n − 1 ≥ J 2 n − 2 , n = J 2 n − 2 , n − 2 ≥ J 2 n − 2 , n − 3   by symmetry and the induction hypothesis, and clearly A 1 = ( n − 2 ) ( n − 3 ) ≥ 0   .
    The corresponding condition of Theorem  3.1 is satisfied, and therefore J 2 n , n − J 2 n , n − 1 ≥ 0 .  
This completes the proof.
Theorem 3.3 The sequence I n , 0 , I n , 1 , … , I n , n − 1   is unimodal.
Proof. By the symmetry of I n ( t )   , it suffices to show that I n , k ≥ I n , k − 1   for all 1 ≤ k ≤ ( n − 1 ) / 2   . From Table  1 , it is clear that the coefficients I n , k   of the polynomials I n ( x )   are unimodal in k   for 1 ≤ n ≤ 6   .
Now suppose n ≥ 7   and the polynomials I n − 1 ( t )   and I n − 2 ( t )   are unimodal. Replacing k   by k − 1   in  2.3 , we obtain
n I n , k − 1 = k I n − 1 , k − 1 + ( n − k + 1 ) I n − 1 , k − 2 + ( k 2 + n − 2 ) I n − 2 , k − 1
+ [ 2 ( k − 1 ) ( n − k ) − n + 3 ] I n − 2 , k − 2 + [ ( n − k + 1 ) 2 + n − 2 ] I n − 2 , k − 3 . (3.2)
Combining  2.3 and  3.2 yields
n ( I n , k − I n , k − 1 ) = B 0 I n − 1 , k + B 1 I n − 1 , k − 1 + B 2 I n − 1 , k − 2
+ 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 , (3.3)
where
B 0 = k + 1 , B 1 = n − 2 k , B 2 = − ( n − k + 1 ) ,
C 0 = ( k + 1 ) 2 + n − 2 , C 1 = 2 k n − 3 k 2 − 2 k − 2 n + 5 ,
C 2 = n 2 − 4 k n + 3 k 2 + 4 n − 5 − 2 k , C 3 = − ( n − k + 1 ) 2 − n + 2 .
Notice that I n − 1 , k ≥ I n − 1 , k − 1 ≥ I n − 1 , k − 2   for 1 ≤ k ≤ ( n − 1 ) / 2   . By Theorem  3.1 , we have
B 0 I n − 1 , k + B 1 I n − 1 , k − 1 + B 2 I n − 1 , k − 2 ≥ 0 . (3.4)
In what follows we will show that
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 ≥ 0 , ∀ 1 ≤ k ≤ ( n − 1 ) / 2 . (3.5)
We have the following two cases:
  • ∙ If 1 ≤ k ≤ ( n − 2 ) / 2   , then I n − 2 , k ≥ I n − 2 , k − 1 ≥ I n − 2 , k − 2 ≥ I n − 2 , k − 3   by the induction hypothesis, and
    C 0 = ( k + 1 ) 2 + n − 2 ≥ 0 , C 0 + C 1 = ( 2 k − 1 ) ( n − k − 1 ) + k + 3 ≥ 0 ,
    C 0 + C 1 + C 2 = ( n − k + 1 ) 2 + n − 2 ≥ 0 , C 0 + C 1 + C 2 + C 3 = 0 .
  • ∙ If k = ( n − 1 ) / 2   , then by symmetry and the induction hypothesis, I n − 2 , k − 1 ≥ I n − 2 , k = I n − 2 , k − 2 ≥ I n − 2 , k − 3 .   Notice that C 1 = ( n − 3 ) ( n − 7 ) 4 ≥ 0 , for n ≥ 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 ( I n , k − I n , k − 1 ) ≥ 0 , ∀ 1 ≤ k ≤ ( n − 1 ) / 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 2 n , k   by introducing one more parameter. Let f i x ( π )   be the number of fixed points of an involution π ∈ ℑ n   .
Then Désarménien and Foata [5] derived the following generating function:
∑ n = 0 ∞ H n ( z , t ) u n ( 1 − t ) n + 1 = ∑ r = 0 ∞ t r ( 1 − z u ) r + 1 ( 1 − u 2 ) r ( r + 1 ) / 2 , (4.1)
where H n ( z , t ) : = ∑ π ∈ ℑ n z f i x ( π ) t d ( π ) = ∑ k = 0 n − 1 H n , k ( z ) t k .   The first few values of H n : = H n ( z , t )   are given as follows:
H 1 = z ,
H 2 = z 2 + t ,
H 3 = z 3 + 2 z t + z t 2 ,
H 4 = z 4 + ( 1 + 3 z 2 ) t + ( 1 + 3 z 2 ) t 2 + t 3 ,
H 5 = z 5 + ( 2 z + 4 z 3 ) t + ( 6 z + 6 z 3 ) t 2 + 6 z t 3 + z t 4 ,
H 6 = z 6 + ( 1 + 3 z 2 + 5 z 4 ) t + ( 3 + 15 z 2 + 10 z 4 ) t 2 + ( 7 + 21 z 2 ) t 3 + ( 3 + 6 z 2 ) t 4 + t 5 ,
H 7 = z 7 + ( 2 z + 4 z 3 + 6 z 5 ) t + ( 14 z + 28 z 3 + 15 z 5 ) t 2 + ( 40 z + 52 z 3 ) t 3 + ( 36 z + 21 z 3 ) t 4 + 12 z t 5 + z t 6 .
Theorem 4.1 For n ≥ 4   and k ≥ 0   , there holds
n H n , k ( z )
= ( n + k ) z H n − 1 , k ( z ) − ( k − 1 ) z H n − 1 , k − 1 ( z ) + ( k 2 + k + n − 2 ) H n − 2 , k ( z )
+ 2 ( k n − k 2 − n + 2 ) H n − 2 , k − 1 ( z ) + ( k 2 + n 2 − 2 k n − k + 2 n − 2 ) H n − 2 , k − 2 ( z )
− ( k 2 + 2 k + n − 2 ) z H n − 3 , k ( z ) − ( k − 1 ) ( 2 n − 3 k − 7 ) z H n − 3 , k − 1 ( z )
− ( n − k − 2 ) ( n − 3 k + 4 ) z H n − 3 , k − 2 ( z ) − ( 2 k n − k 2 − n 2 − n + 3 ) z H n − 3 , k − 3 ( z ) , (4.2)
where H n , k ( z ) = 0   if k < 0   .
Proof. Extracting the coefficients of u 2 n   in  1.1 , we obtain
h n ( z , t ) : = H n ( z , t ) ( 1 − t ) n + 1 = ∑ r = 0 ∞ t r ∑ k = 0 ⌊ n / 2 ⌋ ( r ( r + 1 ) / 2 + k − 1 k ) ( r + n − 2 k n − 2 k ) z n − 2 k . (4.3)
Let T ( n , k ) : = ( x + k − 1 k ) ( y − 2 k n − 2 k ) z n − 2 k ,   and s ( n ) : = ∑ k = 0 ⌊ n / 2 ⌋ T ( n , k ) .   Applying Zeilberger's algorithm, the Maple package ZeilbergerRecurrence(T,n,k,s,0..n) gives − z ( 2 x + y + n + 1 ) s ( n ) + ( n + 2 x + 1 ) s ( n + 1 ) + z ( n + y + 3 ) s ( n + 2 ) − ( n + 3 ) s ( n + 3 ) = 0 ,   i.e., n s ( n ) = z ( n + y ) s ( n − 1 ) + ( n + 2 x − 2 ) s ( n − 2 ) − z ( 2 x + y + n − 2 ) g ( n − 3 ) .   When x = r ( r + 1 ) / 2   and y = r   , we get
n s ( n ) = z ( r + n ) s ( n − 1 ) + [ r ( r − 1 ) + 2 r + n − 2 ] s ( n − 2 ) − z [ r ( r − 1 ) + 3 r + n − 2 ] s ( n − 3 ) . (4.4)
Now, from  4.3 and  4.4 it follows that
n h n ( z , t ) = z t ∂ ∂ t h n − 1 ( t ) + n z h n − 1 ( z , t ) + t 2 ∂ 2 ∂ t 2 h n − 2 ( z , t ) + 2 t ∂ ∂ t h n − 2 ( z , t )
+ ( n − 2 ) h n − 2 ( z , t ) − z t 2 ∂ 2 ∂ t 2 h n − 3 ( z , t ) − 3 z t ∂ ∂ t h n − 3 ( z , t ) − ( n − 2 ) z h n − 3 ( z , t ) .
Namely,
n H n ( z , t ) = z t ( 1 − t ) ∂ ∂ t H n − 1 ( z , t ) + n z H n − 1 ( z , t ) + t 2 ( 1 − t ) 2 ∂ 2 ∂ t 2 H n − 2 ( z , t )
+ 2 t ( 1 − t ) [ 1 + ( n − 2 ) t ] ∂ ∂ t H n − 2 ( z , t ) + [ n − 2 + 2 t + ( n 2 − 2 n ) t 2 ] H n − 2 ( z , t )
− z t 2 ( 1 − t ) 3 ∂ 2 ∂ t 2 H n − 3 ( z , t ) − z t ( 1 − t ) 2 [ 3 + ( 2 n − 7 ) t ] ∂ ∂ t H n − 3 ( z , t )
− ( n − 2 ) z ( 1 − t ) [ 1 + t + ( n − 3 ) t 2 ] H n − 3 ( z , t ) .
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 2 n , k   of third order.
Since I n , k = I n , n − 1 − k   , we can write I n ( t )   as following
I n ( x ) = ∑ k = 0 n − 1 I n , k x k = { ∑ k = 0 n / 2 − 1 I n , k x k ( 1 + x n − 2 k − 1 ) , if n is even, ∑ k = 0 ( n − 3 ) / 2 I n , k x k ( 1 + x n − 2 k − 1 ) + I n , ( n − 1 ) / 2 x ( n − 1 ) / 2 , if n is odd.
Applying the well-known formula x n + y n = ∑ j = 0 ⌊ n / 2 ⌋ ( − 1 ) j n n − j ( n − j j ) ( x y ) j ( x + y ) n − 2 j ,   we obtain
I n ( t ) = ∑ k = 0 ⌊ ( n − 1 ) / 2 ⌋ a n , k t k ( 1 + t ) n − 2 k − 1 , (4.5)
where a n , k = { ∑ j = 0 k ( − 1 ) k − j n − 2 j − 1 n − k − j − 1 ( n − k − j − 1 k − j ) I n , j , if 2 k + 1 < n , ∑ j = 0 k − 1 ( − 1 ) k − j n − 2 j − 1 n − k − j − 1 ( n − k − j − 1 k − j ) I n , j + I n , k , if 2 k + 1 = n .   The first values of a n , k   are given in Table  2 , which seems to suggest the following
Conjecture 4.2 For n ≥ 1   and k ≥ 0   , the coefficients a n , k   are nonnegative integers.
Table 2 : Values of a n , k   for n ≤ 16   and 0 ≤ k ≤ ⌊ ( n − 1 ) / 2 ⌋   .
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 ( 1 + t ) n − 2 k − 1   are symmetric and unimodal with center of symmetry at ( n − 1 ) / 2   , the above conjecture, if true, is stronger than the fact that I n ( t )   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 ( t ) = ∑ k = 1 ⌊ ( n + 1 ) / 2 ⌋ c n , k t k ( 1 + t ) n − 2 k + 1 ,   where c n , k   is the number of increasing binary trees on [ n ]   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 ( t ) = t / ( 1 + t ) 2   and P n ( x ) = ∑ k = 0 ⌊ ( n − 1 ) / 2 ⌋ a n , k x k ,   then we can rewrite  4.12 as
I n ( t ) = ( 1 + t ) n − 1 P n ( x ) . (4.6)
Differentiating  4.6 with respect to t   we get
I n ′ ( t ) = ( n − 1 ) ( 1 + t ) n − 2 P n ( x ) + ( 1 + t ) n − 1 P n ′ ( x ) x ′ ( t ) , (4.7)
I n ′ ′ ( t ) = ( n − 1 ) ( n − 2 ) ( 1 + t ) n − 3 P n ( x ) + 2 ( n − 1 ) ( 1 + t ) n − 2 P n ′ ( x ) x ′ ( t )
+ ( 1 + t ) n − 1 P n ′ ′ ( x ) ( x ′ ( t ) ) 2 + ( 1 + t ) n − 1 P n ′ ( x ) x ′ ′ ( t ) , (4.8)
x ′ ( t ) = 1 − t ( 1 + t ) 3 , x ′ ′ ( t ) = 2 t − 4 ( 1 + t ) 4 . (4.9)
Substituting  4.6 – 4.9 into  2.7 , we obtain
n ( 1 + t ) n − 1 P n ( x )
= ( 1 + ( 2 n − 2 ) t + t 2 ) ( 1 + t ) n − 3 P n − 1 ( x ) + t ( 1 − t ) 2 ( 1 + t ) n − 5 P n − 1 ′ ( x )
+ [ − ( t 2 + 14 t + 1 ) ( 1 − t ) 2 + ( 1 + 6 t − 18 t 2 + 6 t 3 + t 4 ) n + 4 t 2 n 2 ] ( 1 + t ) n − 5 P n − 2 ( x )
+ [ 3 t ( t 2 − 4 t + 1 ) ( 1 − t ) 2 + 4 t 2 ( 1 − t ) 2 n ] ( 1 + t ) n − 7 P n − 2 ′ ( x )
+ t 2 ( 1 − t ) 4 ( 1 + t ) n − 9 P n − 2 ′ ′ ( x ) . (4.10)
Dividing the two sides of  4.10 by ( 1 + t ) n − 1   and noticing that t / ( 1 + t ) 2 = x   , we get after a little manipulation
n P n ( x ) = [ 1 + ( 2 n − 4 ) x ] P n − 1 ( x ) + ( x − 4 x 2 ) P n − 1 ′ ( x )
+ [ ( n − 1 ) + ( 2 n − 8 ) x + 4 ( n − 3 ) ( n − 4 ) x 2 ] P n − 2 ( x )
+ [ 3 x + ( 4 n − 30 ) x 2 + ( 72 − 16 n ) x 3 ] P n − 2 ′ ( x ) + ( x 2 − 8 x 3 + 16 x 4 ) P n − 2 ′ ′ ( x ) .
Extracting the coefficients of x k   yields
n a n , k = a n − 1 , k + ( 2 n − 4 ) a n − 1 , k − 1 + k a n − 1 , k − 4 ( k − 1 ) a n − 1 , k − 1
+ ( n − 1 ) a n − 2 , k + ( 2 n − 8 ) a n − 2 , k − 1 + 4 ( n − 3 ) ( n − 4 ) a n − 2 , k − 2
+ 3 k a n − 2 , k + ( 4 n − 30 ) ( k − 1 ) a n − 2 , k − 1 + ( 72 − 16 n ) ( k − 2 ) a n − 2 , k − 2
+ k ( k − 1 ) a n − 2 , k − 8 ( k − 1 ) ( k − 2 ) a n − 2 , k − 1 + 16 ( k − 2 ) ( k − 3 ) a n − 2 , k − 2 .
After simplification, we obtain the following recurrence formula for a n , k   .
Theorem 4.3 For n ≥ 3   and k ≥ 0   , there holds
n a n , k = ( k + 1 ) a n − 1 , k + ( 2 n − 4 k ) a n − 1 , k − 1 + [ k ( k + 2 ) + n − 1 ] a n − 2 , k
+ [ ( k − 1 ) ( 4 n − 8 k − 14 ) + 2 n − 8 ] a n − 2 , k − 1 + 4 ( n − 2 k ) ( n − 2 k + 1 ) a n − 2 , k − 2 , (4.11)
where a n , k = 0   if k < 0   .
By  4.12 , a n , k = 0   if n ≤ 2 k   . On the other hand, if n ≥ 2 k + 3   , then ( k − 1 ) ( 4 n − 8 k − 14 ) + 2 n − 8 > 0 for any k ≥ 1 ,   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 2 n + 1 , n , a 2 n + 2 , n ≥ 0   .
Finally, from  4.12 it is easy to see that
a 2 n + 1 , n = ( − 1 ) n I 2 n + 1 ( − 1 ) = ∑ k = 0 2 n ( − 1 ) n − k I 2 n + 1 , k ,
a 2 n + 2 , n = ( − 1 ) n I 2 n + 2 ′ ( − 1 ) = ∑ k = 1 2 n + 1 ( − 1 ) n + 1 − k k I 2 n + 2 , k .
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
J 2 n ( t ) = ∑ k = 1 n b 2 n , k t k ( 1 + t ) n − 2 k , (4.12)
where b 2 n , k = { ∑ j = 0 k ( − 1 ) k − j 2 n − 2 j 2 n − k − j ( 2 n − k − j k − j ) J 2 n , j , if k < n , ∑ j = 0 k − 1 ( − 1 ) k − j 2 n − 2 j 2 n − k − j ( 2 n − k − j k − j ) J 2 n , j + J 2 n , k , if k = n .   Now, it follows from  2.2 that
J 2 n , k = ∑ i = 0 k ( − 1 ) k − i ( 2 n + 1 k − i ) ( i ( i + 1 ) / 2 + n − 1 i ( i + 1 ) / 2 − 1 )
is a polynomial in n   of degree d : = k ( k + 1 ) / 2 − 1   with leading coefficient 1 / d !   , and so is b 2 n , k   . Thus, we have lim n → ∞ b 2 n , k = ∞   for any k   . The first values of b 2 n , k   are given in Table  3 , which seems to suggest
Conjecture 4.4 For n ≥ 9   and k ≥ 1   , the coefficients b 2 n , k   are nonnegative integers.
Table 3 : Values of b 2 n , k   for 2 n ≤ 24   and 1 ≤ k ≤ n   .
k \ 2 n   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 ≥ 2   and k ≥ 1   , there holds
2 n b 2 n , k = [ k ( k + 1 ) + 2 n − 2 ] b 2 n − 2 , k + [ 2 + 2 ( k − 1 ) ( 4 n − 4 k − 3 ) ] b 2 n − 2 , k − 1
+ 8 ( n − k + 1 ) ( 2 n − 2 k + 1 ) b 2 n − 2 , k − 2 .
where b 2 n , k = 0   if k < 1   .
Theorem  4.5 allows us to reduce the verification of Conjecture  4.4 to the boundary case b 2 n , n ≥ 0   for n ≥ 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.