Institut für Statistik und Decision Support martin.rubey@univie.ac.at http://www.mat.univie.ac.at/~rubey .
<ph f="cmbx">A combinatorial interpretation of Guo and Zeng's </ph> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi>q</mi> </math> <ph f="cmbx">-Faulhaber coefficients</ph>

1 Introduction

In the early seventeenth century, Johann Faulhaber considered the sums of powers S m , n = ∑ k = 1 n k m   and provided formulas for the coefficients f m , k   in S 2 m + 1 , n = ∑ k = 1 m f m , k ( n ( n + 1 ) 2 ) k + 1 .   A combinatorial interpretation of these coefficients was given by Gessel and Viennot[3] . Recently, Guo and Zeng[4] , continuing work of Schlosser[6] , Warnaar[8] and Garrett and Hummel[2] were able to find q   -analogues of Faulhaber's formulas.
More precisely, setting [ k ] = 1 − q k 1 − q   and [ k ] ! = ∏ i = 1 k 1 − q i 1 − q   , they proved the following result:
Theorem 1.1. Let m , n ∈ N   and set
S m , n ( q ) = ∑ k = 1 n [ 2 k ] [ 2 ] [ k ] m − 1 q m + 1 2 ( n − k ) . (1)
Then there exist polynomials P m , k ∈ Z [ q ]   such that
S 2 m + 1 , n ( q ) = ∑ k = 0 m ( − 1 ) m − k [ k ] ! [ m + 1 ] ! P m , m − k q ( m − k ) n ( [ n ] [ n + 1 ] ) k + 1 [ 2 ] . (2)
They also gave an explicit formula for the polynomials P m , k ( q )   , and asked for a combinatorial interpretation of the coefficients of these polynomials. It is the purpose of this paper to answer this question.

2 A combinatorial interpretation of the q   -Faulhaber coefficients

In this Section we will exhibit a surprisingly simple combinatorial interpretation of the polynomials P m , k   which also yields some interesting properties as easy consequences. We follow exactly the arguments given by Gessel and Viennot[3,Theorem 29] :
Theorem 2.1. Let h 2 m − k ( { 1 , q } k − m + 1 )   denote the ( 2 m − k )   th   complete homogeneous function in 2 ( k − m + 1 )   variables, half of which are specialised to q   , the others to 1   . Thus, for m ≤ k   we have h 2 m − k ( { 1 , q } k − m + 1 ) = ∑ i = 0 2 m − k ( k − m + i k − m ) ( m − i k − m ) q i   , for m > k   it vanishes.
Then the inverse of the matrix ( h 2 m − k ( { 1 , q } k − m + 1 ) ) k , m ∈ { 0 . . . n }   is the matrix ( ( − 1 ) k − m [ m ] ! [ k + 1 ] ! P k , k − m ) k , m ∈ { 0 . . . n } .   Note that both matrices are lower triangular.
The proof rests on the following Lemma, which might be interesting per se.
When q = 1   it reduces to a simple application of the binomial theorem. In the general case however, it turns out to be considerably more difficult.
Lemma 2.2. For any m   and l   we have
(3) ( [ l ] [ l + 1 ] q l ) m + 1 − ( [ l − 1 ] [ l ] q l − 1 ) m + 1 = [ 2 ] ∑ k h m − 2 k ( { 1 , q } k + 1 ) [ 2 l ] [ 2 ] [ l ] 2 ( m − k ) q − l ( m − k + 1 ) .
  • Proof. Multiplying both sides with ( q l ( 1 − q ) [ l ] ) m + 1   , and replacing q l   with x   , we arrive at the following equivalent identity:
    (4) ( 1 − q x ) m + 1 − ( q − x ) m + 1 = ∑ k h m − 2 k ( { 1 , q } k + 1 ) ( 1 − q ) 2 k + 1 ( 1 − x ) m − 2 k ( 1 + x ) x k .
    We will show that the coefficients of q r x s   are the same on both sides. To this end, we first extract the coefficient of q r   in h m − 2 k ( { 1 , q } k + 1 ) ( 1 − q ) 2 k + 1   which for k ≤ ⌊ m 2 ⌋   turns out to be ∑ i = 0 m − 2 k ( − 1 ) r − i ( k + i k ) ( m − k − i k ) ( 2 k + 1 r − i ) .   Transforming this sum into hypergeometric notation – using for example Christian Krattenthaler's package hyp.m[5] – we find that it equals ( − 1 ) r ( m − k k ) ( 2 k + 1 r ) 3 F 2 [ − r , 1 + k , 2 k − m k − m , 2 + 2 k − r ; 1 ] ,   which is summable by [7,(2.3.1.3);Appendix(III.2)] . After some simplification we obtain ( − 1 ) r + m ( m + 1 r ) ( r − k − 1 m − 2 k )   as closed form for the sum. Since the sign and the first binomial coefficient does not involve the summation index k   , it remains to evaluate the coefficient of x s   in ∑ k = 0 ⌊ m 2 ⌋ ( r − k − 1 m − 2 k ) ( 1 − x ) m − 2 k ( 1 + x ) x k .   Obviously it is sufficient to find a closed form for 〈 x s 〉 ∑ k = 0 ⌊ m 2 ⌋ ( r − k − 1 m − 2 k ) ( 1 − x ) m − 2 k x k = ∑ k = 0 ⌊ m 2 ⌋ ( − 1 ) s − k ( r − k − 1 m − 2 k ) ( m − 2 k s − k ) .   Now we have to distinguish several cases. For 2 k ≤ m   we observe that the product of binomial coefficients ( r − k − 1 m − 2 k ) ( m − 2 k s − k )   does not vanish only if min ( r , m − r + 1 ) ≤ k ≤ min ( s , m − s ) .   Therefore, the sum above must be zero for
    s < r or s > m − r , if r ≤ ⌊ m 2 ⌋ and s ≥ r or s ≤ m − r , if r > ⌊ m 2 ⌋ .  
    If the pair r   and s   happens to be outside of this region, the bounds of summation are natural, so we can write the sum as a hypergeometric series. This time, it equals ( − 1 ) s ( r − 1 m ) ( m s ) 3 F 2 [ − s , − m + s , 1 1 − r , − m + r ; 1 ] ,   which is not directly summable. However, the terminating form of the transformation in [1,Ex.7,p.98] is applicable. Unfortunately, the parameter that causes the sum to terminate cancels, so we have to evaluate 3 F 2 [ − s , − m + s , 1 + ɛ 1 − r , − m + r ; 1 ]   instead. Again, we have to distinguish between s ≥ r   and s > m − r   , however, the only change in the computation amounts to exchanging the two lower parameters of the hypergeometric expression above. Applying the above mentioned transformation twice and then sending ɛ   to zero, we arrive at an expression involving
    2 F 1 [ r − s , r − m + s r − m ; 1 ] , or, for s > m − r 2 F 1 [ 1 − r + m − s , 1 − r + s 1 − r ; 1 ]  
    to which we can apply [7,Appendix(III.4)] . After some simplification we see that the sum evaluates to
    ( − 1 ) m + r + s if r ≤ s ≤ m − r and r ≤ ⌊ m 2 ⌋
    and ( − 1 ) m + r + s + 1 if m − r < s < r and r > ⌊ m 2 ⌋ .
    Putting all the pieces together we obtain
    ( − 1 ) r ( m + 1 r ) if s = r ≠ m − r + 1 ,
    ( − 1 ) r + m ( m + 1 r ) if s = m − r + 1 ≠ r and
    0 otherwise
    for the coefficient of q r x s   in the right hand side of  3 . This is easily seen to be equal to the coefficient of q r x s   in the left hand side of  3 . □
Remark. It seems that an alternative proof could be given based on the Wilf-Zeilberger method. In any case, it would be interesting to see the given identity as a special case of a more general one. In particular, is there a q   -binomial theorem that could be applied to [ l + 1 ] m + 1   ?
A second question poses itself by looking at the corresponding section in the paper of Gessel and Viennot: In the standard case, a very similar identity can be derived for the Salié numbers, i.e., the coefficients of ( n ( n + 1 ) ) k   in ∑ k = 1 n ( − 1 ) n − k k m   .
However, extending the ideas of this paper in a straightforward fashion does not seem to work.
Schlosser[6] considered various q   analogues of these alternating sums and derived formulas for m ≤ 4   , the most plausible being
T m , n ( q ) = ∑ k = 1 n [ 2 k ] [ 2 ] [ k ] m − 1 ( − q m + 1 2 ) n − k  
Standard computer algebra packages are able to find formulas for greater values of m   . It turns out that the coefficient of ( [ n ] [ n + 1 ] ) k   in T 2 m , n   is of the form ( 1 + q n + 1 2 ) ( 1 + q 1 2 ) m − k ( 1 + q 2 m + 1 2 ) . . . ( 1 + q 2 k + 1 2 ) ( − q n ) m − k g k , m ( q ) ,   where g k , m ( q )   is a polynomial in q   . For small m   these polynomials are listed in Table  1 . Unfortunately, they do not have nonnegative coefficients, which indicates that this is not the `right' q   -analogue of the Salié numbers. It would be particularly nice to have a common q   -analogue of Faulhaber and Salié numbers. Note that Guo and Zeng[4] proposed a more general q   analogue of Faulhaber's numbers, but these also fail to have nonnegative coefficients.
k \ m 1 2 3 4
1 1 1 2 q − q 1 2 + 2 ( 5 q 2 − q 3 2 + 9 q − q 1 2 + 5 ) ( q − q 1 2 + 1 )
2 1 2 q − q 1 2 + 2 ( 5 q 2 − q 3 2 + 9 q − q 1 2 + 5 ) ( q − q 1 2 + 1 )
3 1 3 q 2 − 2 q 3 2 + 4 q − 2 q 1 2 + 3
4 1
Table 1 . g k , m ( q )   for m ≤ 3  
Finally, although the appearance of the complete homogeneous symmetric functions is natural, the specialisation involved seems to be interesting and might deserve more attention.
  • Proof of Theorem  2.1 . Summing Equation  3 on l   from 1   to n   , observing that its left hand telescopes and using Equation  1 on its right hand side we obtain
    ( [ n ] [ n + 1 ] q n ) m + 1 = [ 2 ] ∑ k h m − 2 k ( { 1 , q } k + 1 ) S 2 ( m − k ) + 1 , n q − n ( m − k + 1 ) .
    Plugging in Equation  2 and exchanging the order of summation, the right hand side becomes ∑ l ∑ k ≥ l h m − 2 k ( { 1 , q } k + 1 ) ( − 1 ) m − k − l [ l ] ! [ m − k + 1 ] ! P m − k , m − k − l ( [ n ] [ n + 1 ] q n ) l + 1 .   Comparing coefficients of ( [ n ] [ n + 1 ] q n ) l + 1   we see that the two matrices in question are indeed inverses. □
We also copy a simple lemma from Gessel and Viennot[3] , that follows easily from the formula for the entries of the inverse of a matrix:
Lemma 2.3. Let ( A i , j ) i , j ∈ { 1 , 2 , . . . , m }   be an invertible lower triangular matrix and let B   be its inverse. Then for 0 ≤ k ≤ n ≤ m   we have B n , k = ( − 1 ) n − k A k , k , A k + 1 , k + 1 , . . . , A n , n det ( A k + i + 1 , k + j ) i , j ∈ { 0 , 1 , . . . , n − k − 1 } .  
Finally we can announce our main theorem:
Theorem 2.4.
P m , k = det ( h m − k − i + 2 j − 1 ( { 1 , q } i − j + 2 ) ) i , j ∈ { 0 , 1 , . . . , k − 1 } (5)
is the number of weighted families of non-intersecting lattice paths from ( 0 , 0 ) , ( 2 , − 2 ) , . . . , ( 2 ( k − 1 ) , − 2 ( k − 1 ) )   to ( 3 , m − k − 1 ) , ( 5 , m − k − 2 ) , . . . , ( 2 ( k − 1 ) + 3 , m − 2 k ) ,   where a vertical step with an even x   -coordinate has weight q   and all other steps have weight 1   .
  • Proof. The determinantal formula follows from the preceding lemma. The combinatorial interpretation is a standard application of the main theorem of nonintersecting lattice paths, and completely analogous to the applications given in Gessel and Viennot[3] . □
Corollary 2.5. The coefficients of P m , k   are nonnegative and symmetric.
  • Proof. A combinatorial way to see the symmetry is as follows: Modifying the weights such that vertical steps with an odd x   -coordinate have weight q   and all the others weight 1   does not change the entries of the determinant.
    However, consider any given family of paths with weight q w   , when vertical steps with even x   -coordinate have weight q   . After the modification of the weights it will have weight q m a x − w   , where m a x   is the total number of vertical steps in such a family of paths, which implies the claim. □
Remark. It appears that the polynomials P m , k   are log-concave, however, we did not pursue this question further.

3 Acknowledgements

Many thanks are due to Michael Schlosser and Christian Krattenthaler for their patience and help with Lemma  2.2 and for pointing out some bad typos in the manuscript. References

  1. Wilfrid Norman Bailey, Generalized hypergeometric series, Cambridge Tracts in Mathematics and Mathematical Physics, No. 32, Stechert-Hafner, Inc., New York, 1964.
  2. Kristina C. Garrett and Kristen Hummel, A combinatorial proof of the sum of q   -cubes, Electronic Journal of Combinatorics 11 (2004), no. 1, Research Paper 9, 6 pp. (electronic).
  3. Ira Martin Gessel and Xavier Gérard Viennot, Determinants, paths, and plane partitions, (1989), 36 pages. ☻ open access ✓
  4. Victor J. W. Guo and Jiang Zeng, A q   -analogue of faulhaber's formula for sums of powers, Preprint (2005), 18 pages.
  5. Christian Krattenthaler, HYP and HYPQ: Mathematica packages for the manipulation of binomial sums and hypergeometric series, respectively q   -binomial sums and basic hypergeometric series, Journal of Symbolic Computation 20 (1995), no. 5-6, 737–744.
  6. Michael Schlosser, q   -analogues of the sums of consecutive integers, squares, cubes, quarts and quints, Electronic Journal of Combinatorics 11 (2004), no. 1, Research Paper 71, 11 pp. (electronic).
  7. Lucy Joan Slater, Generalized hypergeometric functions, Cambridge University Press, Cambridge, 1966.
  8. Sven Ole Warnaar, On the q   -analogue of the sum of cubes, Electronic Journal of Combinatorics 11 (2004), no. 1, Research Paper 13, 2 pp. (electronic).