Fountains, histograms, and q–identities

Peter Paule^{1}^{†}and Helmut Prodinger^{2}^{‡}

1Research Institute for Symbolic Computation, Johannes Kepler University Linz, A-4040 Linz, Austria

e-mail: Peter.Paule@risc.uni-linz.ac.at
Url: http://www.risc.uni-linz.ac.at/research/combinat/

2 The John Knopfmacher Centre for Applicable Analysis and Number Theory, School of Mathematics, University of the Witwatersrand, P. O. Wits, 2050 Johannesburg, South Africa

e-mail: helmut@maths.wits.ac.za
Url: http://www.wits.ac.za/helmut/

received —, revised —, accepted —.

We solve the recursion S_{n} = S_{n−1} −q^{n}S_{n−p}, both, explicitly, and in the limit for n → ∞, proving in this way a formula due to Merlini and Sprugnoli. It is also discussed how computer algebra could be applied.

Keywords: q–identities, fountains, histograms, Schur polynomials

1 Fountains and histograms

Merlini and Sprugnoli [6] discuss fountains and histograms; for the reader’s convenience, we review a few key issues here.

A fountain with n coins is an arrangement of n coins in rows such that each coin in a higher row touches exactly two coins in the next lower row.

A p-histogram is a sequence of columns in which the height of the (j + 1)st column is at most k + p, if k is the height of column j; the first column has height r, with 1 ≤ r ≤ p.

It can be shown that the enumeration of coins in a fountain is equivalent with the enumeration of 1-histograms. The paper [6] addresses the enumeration of p-histograms with respect to area (=number of cells). Let f_{n}^{[p]}be the number p-histograms with area n and F^{[p]}(q) the corresponding generating function F^{[p]}(q) = ∑_{n}f_{n}^{[p]}q^{n}. The authors of [6] use two different approaches: one produces the answer in the form

F^{[p]}(q) = lim_{m→∞} \frac{D_{m}}{E_{m}},

†Partially supported by SFB grant F1305 of the Austrian FWF.

‡The research was started when this author visited the RISC in 2002. Partially supported by NRF grant 2053748.

1365–8050 \begin{matrix}c \\ ◯ \end{matrix} Maison de l’Informatique et des Mathématiques Discrètes (MIMD), Paris, France

with some polynomials D_{m}, E_{m} defined in the next section, and the other gives it as

F^{[p]}(q) = ∑_{k≥0} \frac{(−1)^{k}q^{p\binom{k+1}{2}}}{(1 − q)...(1 − q^{k})} / ∑_{k≥0} \frac{(−1)^{k}q^{k+p\binom{k}{2}}}{(1 − q)...(1 − q^{k})} .

According to [5], it would be nice to have a direct argument that these two answers coincide. This is the subject of the present note.

2 Generalized Schur polynomials

The polynomials mentioned in the introduction are for fixed p ≥ 1 defined as follows:

E_{n}= E_{n−1} − q^{n}E_{n−p} , n ≥ p,  E_{0} = ···= E_{p−1} = 1,
D_{n}= D_{n−1} − q^{n}D_{n−p} , n ≥ p,  D_{i} = 1 − ∑_{j=1}^{i} q^{j}, i = 0,...,p − 1.

They can be compared with the classical Schur polynomials [8], which occur for p = 2 and q = −1. Then Merlini and Sprugnoli want a direct proof of the formulæ

E_{∞} := lim_{n→∞} E_{n} = ∑_{k≥0} \frac{(−1)^{k}q^{p\binom{k+1}{2}}}{(1 − q)...(1 − q^{k})} ,

D_{∞} := lim_{n→∞} D_{n} = ∑_{k≥0} \frac{(−1)^{k}q^{k+p\binom{k}{2}}}{(1 − q)...(1 − q^{k})} .

We will not only achieve that but actually derive explicit expressions for these polynomials!

It should be mentioned that Cigler [4] developed independently a combinatorial method to deal with recursions as ours, but also more general ones.

Let us study the generic recursion

S_{n} = S_{n−1} + tq^{n−p} S_{n−p} ,

with unspecified initial values S_{0},...,S_{p−1} . For p = 2, these polynomials were studied by Andrews (and others) in the context of Schur polynomials, see [2].

We will use standard notation from q–calculus, see [1]:

(x)_{n} = (1 − x)(1 − xq)...(1 − xq^{n−1} ), \left[{n \atop k}\right] = \frac{(q)_{n}}{(q)_{k}(q)_{n−k}} .

It will be convenient to define \left[{n \atop k}\right] = 0 for n < 0 or k > n.

Now we will proceed as in [1] and consider noncommutative variables x, η, such that xη = qηx; all other variables commute. Lemma 1.

(x + x^{p}η)^{n} = ∑_{k=0}^{n} \left[{n \atop k}\right]q^{p\binom{n}{2}−pnk+p\binom{k+1}{2}} x^{k+p(n−k)} η^{n−k}.

Proof. We write

(x + x^{p}η)^{n} = ∑_{k=0}^{n} a_{n,k}x^{k+p(n−k)} η^{n−k},

and (x + x^{p}η)^{n+1} = (x + x^{p}η)^{n}(x + x^{p}η) resp. as (x + x^{p}η)^{n+1} = (x + x^{p}η)(x + x^{p}η)^{n}, compare coefficients, and get the recursions

a_{n+1,k} = a_{n,k−1} + a_{n,k}q^{k+p(n−k)} ,
a_{n+1,k} = a_{n,k−1}q^{n+1−k} + a_{n,k}q^{p(n−k)}.

From this we derive, taking differences,

a_{n,k}= \frac{1 − q^{n+1−k}}{1 − q^{k}} q^{−p(n−k)} a_{n,k−1}.

The result follows from iteration by noting that a_{n,0} = q^{p\binom{n}{2}}.

Of course we also have

(x + tx^{p}η)^{n} = ∑_{k=0}^{n} \left[{n \atop k}\right]q^{p\binom{n}{2}−pnk+p\binom{k+1}{2}} x^{k+p(n−k)} t^{n−k}η^{n−k}.

Now we derive the generating function for

F (x) = ∑_{n≥0} S_{n}x^{n};

the following procedure is inspired by [2]. Note that we can alternatively view η as an operator, defined by ηf(x) = f(qx). Cigler worked also much with this technique [3, 4]. We find

∑_{n≥p} S_{n}x^{n} = ∑_{n≥p} S_{n−1} x^{n}+ ∑_{n≥p} tq^{n−p} S_{n−p} x^{n} = x ∑_{n≥p−1} S_{n}x^{n}+ tx^{p} ∑_{n≥0} ηS_{n}x^{n}

or

F (x) − ∑_{n<p} S_{n}x^{n} = xF (x) − x ∑_{n<p−1} S_{n}x^{n}+ tx^{p}ηF (x),

and

F (x) = \frac{1}{1 − x − tx^{p}η} ( ∑_{i<p} S_{i}x^{i}− ∑_{i<p−1} S_{i}x^{i+1} ) .

Now we can apply our lemma and write

F (x)= ∑_{n≥0} (x + tx^{p}η)^{n}( ∑_{i<p} S_{i}x^{i}− ∑_{i<p−1} S_{i}x^{i+1} )

= ∑_{n≥0} ∑_{k=0}^{n} \left[{n \atop k}\right]q^{p\binom{n}{2}−pnk+p\binom{k+1}{2}} x^{k+p(n−k)} t^{n−k}η^{n−k}( ∑_{i<p} S_{i}x^{i}− ∑_{i<p−1} S_{i}x^{i+1} )

= ∑_{n≥0} ∑_{k=0}^{n} \left[{n \atop k}\right]q^{p\binom{n}{2}−pnk+p\binom{k+1}{2}} x^{k+p(n−k)} t^{n−k}( ∑_{i<p} S_{i}q^{i(n−k)}x^{i}− ∑_{i<p−1} S_{i}q^{(i+1)(n−k)} x^{i+1} )

= ∑_{n≥0} ∑_{k=0}^{n} \left[{n \atop k}\right]q^{p\binom{k}{2}}x^{n−k+pk} t^{k}( ∑_{i<p} S_{i}q^{ik}x^{i}− ∑_{i<p−1} S_{i}q^{(i+1)k} x^{i+1} )

= ∑_{k,n≥0} \left[{n + k \atop k}\right]q^{p\binom{k}{2}}x^{n+pk}t^{k}( ∑_{i<p} S_{i}q^{ik}x^{i}− ∑_{i<p−1} S_{i}q^{(i+1)k} x^{i+1} )

= ∑_{k≥0} q^{p\binom{k}{2}}x^{pk}t^{k} \frac{1}{(x)_{k+1}} ( ∑_{i<p} S_{i}q^{ik}x^{i}− ∑_{i<p−1} S_{i}q^{(i+1)k} x^{i+1} ) .

From this we find an explicit formula for S_{n} (the quantity S_{−1} has to be interpreted as 0):

S_{n} = ∑_{0≤i<p} (S_{i}− S_{i−1} ) ∑_{k≥0} \left[{n − (p − 1)k − i \atop k}\right]q^{p\binom{k}{2}+ik} t^{k}.

Now we specialize this to our instance. Here, t = −q^{p}, and thus

S_{n} = ∑_{0≤i<p} (S_{i}− S_{i−1} ) ∑_{k≥0} \left[{n − (p − 1)k − i \atop k}\right]q^{p\binom{k+1}{2}+ik} (−1)^{k}.

Therefore

E_{n} = ∑_{k≥0} \left[{n − (p − 1)k \atop k}\right]q^{p\binom{k+1}{2}}(−1)^{k}.

From this, the limit of E_{n} is immediate. For D_{n} we eventually get the following form

D_{n} = ∑_{k≥0} \left[{n − (p − 1)(k − 1) \atop k}\right]q^{k+p\binom{k}{2}} (−1)^{k},

from which the formula for D_{∞} is immediate. To prove it, we need a simple lemma whose proof is just a routine calculation. Lemma 2.

\left[{m − i \atop k}\right]q^{i(k+1)} = g(i) − g(i − 1) where g(i) = −\left[{m − i \atop k + 1}\right]q^{(i+1)(k+1)} .

Now we can plug into the general formula above and compute

D_{n}= E_{n}− ∑_{i=1}^{p−1} ∑_{k≥0} \left[{n − (p − 1)k − i \atop k}\right]q^{p\binom{k+1}{2}+i(k+1)} (−1)^{k}

= E_{n}− ∑_{k≥0}(−1)^{k}q^{p\binom{k+1}{2}} ∑_{i=1}^{p−1} \left[{n − (p − 1)k − i \atop k}\right]q^{i(k+1)}

= E_{n}− ∑_{k≥0}(−1)^{k}q^{p\binom{k+1}{2}}\{ q^{k+1} \left[{n − (p − 1)k \atop k + 1}\right] − q^{p(k+1)} \left[{n − (p − 1)(k + 1) \atop k + 1}\right]\}

= 1 − ∑_{k≥0}(−1)^{k}q^{p\binom{k+1}{2}}q^{k+1} \left[{n − (p − 1)k \atop k + 1}\right],

which is the announced formula after a simple change of variable. Note that in the penultimate step the telescoping property of the lemma has been used.

3 Computer algebra proofs

The polynomial families (E_{n}) and (D_{n}) give rise to the following study with respect to possible computer proofs. Let us take as input our sum representations of E_{n} and D_{n}:

\begin{aligned}E_{n} & = ∑_{k≥0} \left[{n − (p − 1)k \atop k}\right]q^{p\binom{k+1}{2}}(−1)^{k}, \\ D_{n} & = ∑_{k≥0} \left[{n − (p − 1)(k − 1) \atop k}\right]q^{k+p\binom{k}{2}} (−1)^{k}. \end{aligned}  (3.1)

Then, if p is chosen as a specific positive integer, Riese’s package qZeil [7] returns the recurrences S_{n} = S_{n−1} − q^{n}S_{n−p} (n ≥ p) together with a certificate function Cert for independent verification. Despite the fact that for general “generic” integer parameter p there is no algorithm available, a general pattern can be easily guessed from running the algorithm for p = 1, p = 2, and p = 3, say.

For example, let F (n,k) be the kth summand in our sum representation (3.1) of E_{n}, then the recurrence for E_{n} can be refined to the following statement.

Theorem 3.1. For n ≥ p and δ_{k}f(n,k) = f(n,k) − f(n,k − 1), we have

F (n,k) − F (n − 1,k) + q^{n}F (n − p,k) = δ_{k}Cert(n,k)F (n,k),  (3.2)

where

Cert(n,k) = q^{n} \frac{(q^{n−p(k+1)+1} )_{p}}{(q^{n−(p−1)(k+1)} )_{p}}.

Proof. After dividing both sides of (3.2) by F (n,k) the proof reduces to checking equality of rational functions. Namely, note that

\frac{F (n − 1,k)}{F (n,k)} = \frac{1 − q^{n−pk}}{1 − q^{n−(p−1)k}} ,
\frac{F (n,k − 1)}{F (n,k)} = −\frac{q^{pk}}{1 − q^{k}} \frac{(q^{n−pk+1} )_{p}}{(q^{n−(p−1)k+1} )_{p−1}} ,

and

\frac{F (n − p,k)}{F (n,k)} = q^{−n} Cert(n,k).

Analogously, there is a refined version of the recurrence for D_{n}. The certificate in this case is

Cert(n,k) = q^{n} \frac{(q^{n−pk})_{p}}{(q^{n−(p−1)k} )_{p}}.

Summarizing, with the sum representation for E_{n} and D_{n} in hand, the corresponding recurrences follow immediately by summing both sides of the computer recurrences (3.2) over all k ≥ 0.

References

[1] G. E. Andrews, R. Askey, and R. Roy, Special functions, Encyclopedia of Mathematics and its Applications, vol. 71, Cambridge University Press, 1999.

[2] G. E. Andrews, Fibonacci numbers and Rogers–Ramanujan identities, The Fibonacci Quarterly, to appear (2003), 15 pp.

[3] J. Cigler, Elementare q–Identitäten, Séminaire Lotharingien de Combinatoire B05a (1981), 29 pp.

[4] J. Cigler, Some algebraic aspects of Morse code sequences, Discrete Mathematics and Theoretical Computer Science 6 (2003), 55–68.

[5] D. Merlini, Private communication, (2002).

[6] D. Merlini and R. Sprugnoli, Fountains and histograms, J. Algorithms 44 (2002), no. 1, 159–176.

[7] P. Paule and A. Riese, A Mathematica q–analogue of Zeilberger’s algorithm based on an algebraically motivated approach to q–hypergeometric telescoping, Special functions, q–series and related topics (Toronto, ON, 1995), Fields Inst. Commun., vol. 14, Amer. Math. Soc., Providence, RI, 1997, pp. 179–210.

[8] I. Schur, Ein Beitrag zur additiven Zahlentheorie und zur Theorie der Kettenbrüche, S.-B. Preuss. Akad. Wiss. Phys.-Math. Kl., 1917, 302–321, reprinted in I. Schur, Gesammelte Abhandlungen, vol. 2, pp. 117–136, Springer, 1973.