Séminaire Lotharingien de Combinatoire, B16a (1987), 14 pp. [Formerly : Publ. I.R.M.A. Strasbourg, 1987, 341/S–16, p. 73–86.]

LINEARIZATION COEFFICIENTS FOR

THE JACOBI POLYNOMIALS

BY

Dominique FOATA AND Doron ZEILBERGER

R^{}ÉSUM^{}É. — Une formule explicite pour les coefficients de linéarisation des polynômes de Jacobi a été donnée par RAHMAN, d’où l’on tire, sans calcul, les propriétés de positivité. L’obtention de la formule de RAHMAN par des méthodes combinatoires semble malaisée. On peut cependant donner plusieurs interprétations combinatoires de l’intégrale du produit de polynômes de Jacobi ∏_{i} P_{n_{i}}^{(α,β)}(x) et en déduire une évaluation dans le cas particulier où n_{1} = n_{2} + ⋯ + n_{m}.

ABSTRACT. — The explicit non-negative representation of the linearization coefficients of the Jacobi polynomials obtained by RAHMAN seems to be difficult to be derived by combinatorial methods. However several combinatorial interpretations can be provided for the integral of the product of Jacobi polynomials ∏_{i} P_{n_{i}}^{(α,β)}(x) and furnish an evaluation of this integral in the particular case where n_{1} = n_{2} + ⋯ + n_{m}.

1. Introduction. — Standard definition for the Jacobi polynomials reads :

P_{n}^{(α,β)}(x) = ∑_{j=0}^{n} \binom{n + α}{n − j}\binom{n + β}{j} (\frac{x − 1}{2})^{j} (\frac{x + 1}{2})^{n−j}

= \frac{2^{−n}}{n!} ∑_{j=0}^{n} \binom{n}{j}(α + 1 + n − j)_{j} (β + 1 + j)_{n−j} (x − 1)^{n−j}(x + 1)^{j}.

(See, e.g., [Er], [Sz]). Let n = (n_{1}, …, n_{m}) and consider the integral

I_{n} = ∫_{−1}^{+1}(1 − x)^{α}(1 + x)^{β} ∏_{i=1}^{m} P_{n_{i}}^{(α,β)}(x) dx.

Using the classical evaluation

∫_{−1}^{+1}(1 − x)^{α}(1 + x)^{β} dx = \frac{Γ(α + 1)Γ(β + 1)}{Γ(α + β + 2)},

it is readily seen that

D. FOATA AND D. ZEILBERGER

(1.1) I_{n} = \frac{2^{α+β+1}}{∏_{i} n_{i}! (α + β + 2)_{Σn_{i}}} \frac{Γ(α + 1)Γ(β + 1)}{Γ(α + β + 2)}L_{n},

with

(1.2) L_{n} = ∑_{k}(−1)^{Σ(n_{i}−k_{i})} (α + 1)_{Σ(n_{i}−k_{i})} (β + 1)_{Σk_{i}}

× ∏_{i} \binom{n_{i}}{k_{i}}(α + 1 + n_{i} − k_{i})_{k_{i}} (β + 1 + k_{i})_{n_{i}−k_{i}}.

The linearization problem consists of finding an appropriate representation for I_{n} in such a way that non-negative properties of I_{n} are directly apparent from the representation itself. Along those lines RAHMAN [Ra] found the following fantastic formula involving the series_{9}F_{8} : let s+1 ≤ n, 0 ≤ j ≤ 2n − 2s and let

(1.3) I_{s+j,n−s,n} = \frac{(α + 1)_{s+j}(α + 1)_{n−s}(α + 1)_{n}}{(s + j)! (n − s)! n!} \frac{Γ(α + 1)Γ(β + 1)}{2^{−(α+β+1)}Γ(α + β + 1)}

× \frac{(s + j)! (β + 1)_{s+j}}{(α + β)_{s+j}(α + β + 1)_{s+j}(2s + 2j + α + β + 1)}g(s + j, n − s, n).

Then, for j even

g(s + j, n − s, n) = \frac{α + β + 1 + 2s + 2j}{α + β + 1} (α + β + 1 + n − s)_{n−s}

× \frac{(α + 1)_{s+j}(β + 1)_{n}(α + β + 1)_{2s+j}(α + β + 1)_{j}n!}{(α + 1)_{s}(α + 1)_{n−s}(β + 1)_{s+j}(α + β + 2)_{2n+j} s! j!}

× \frac{(s − n)_{j/2}(α + β + n + 1)_{j/2}}{(s − n − \frac{α + β}{2} )_{j/2} (s + 1)_{j/2}(α + 1)_{j/2}}

× \frac{(s − n − α)_{j/2}(β + n + 1)_{j/2}(1/2)_{j/2}}{(\frac{1}{2} + s − n − \frac{α + β}{2} )_{j/2} (s + 1)_{j/2}(α + 1)_{j/2}}

×_{9}F_{8}[{α, 1 + \frac{α}{2}, α + \frac{1}{2}, \frac{α − β}{2} \frac{α − β + 1}{2}, \atop \frac{α}{2}, \frac{1}{2}, \frac{α + β}{2} + 1, \frac{α + β + 1}{2},}

{α + β + n + 1 + \frac{j}{2}, s − n + \frac{j}{2}, −s − \frac{j}{2}, −\frac{j}{2} \atop −β − n − \frac{j}{2}, α + n + 1 − s − \frac{j}{2}, α + s + 1 + \frac{j}{2}, α + 1 + \frac{j}{2}} ]

JACOBI POLYNOMIALS

and a corresponding formula for j odd. Note that in RAHMAN’s paper [Ra, p. 917, formula (1.7)] the factor (α + β + 1 + n − s)_{n−s} occurring after the first fraction above is missing. As proved by RAHMAN [Ra], the foregoing formula shows that if j, s, n are non-negative integers with s + 1 ≤ n, 0 ≤ j ≤ 2n − 2s, then g(s + j, n − s, n) ≥ 0 whenever α ≥ β > −1 and α + β + 1 ≥ 0.

Putting back the value of g(s + j, n − s, n) into (1.3) we deduce the following formula

L_{s+j,n−s,n} = \frac{(α + 1)_{n}(s + j)! (α + 1)_{s+j}(β + 1)_{n}(α + β + 1)_{2s+j}}{(α + β + 1)_{s+j}(α + 1)_{s}}

× \frac{(α + β + 1 + n − s)_{n−s}(α + β + 1)_{j} n!}{s! j!}

× \frac{(s − n)_{j/2}(α + β + n + 1)_{j/2}}{(s − n − \frac{α + β}{2} )_{j/2} (α + s + 1)_{j/2}}

× \frac{(s − n − α)_{j/2}(β + n + 1)_{j/2}(1/2)_{j/2}}{(\frac{1}{2} + s − n − \frac{α + β}{2} )_{j/2} (s + 1)_{j/2}(α + 1)_{j/2}}

×_{9}F_{8}[{α, 1 + \frac{α}{2}, α + \frac{1}{2}, \frac{α − β}{2} \frac{α − β + 1}{2}, α + β + n + 1 + \frac{j}{2}, \atop \frac{α}{2}, \frac{1}{2}, \frac{α + β}{2} + 1, \frac{α + β + 1}{2}, −β − n − \frac{j}{2},}

{s − n + \frac{j}{2}, −s − \frac{j}{2}, −\frac{j}{2} \atop α + n + 1 − s − \frac{j}{2}, α + s + 1 + \frac{j}{2}, α + 1 + \frac{j}{2}} ],

when j is even. When j is odd, formula (1.8) of RAHMAN [Ra] leads to :

L_{s+j,n−s,n} = \frac{(α + 1)_{n}(s + j)! (α + 1)_{s+j}(β + 1)_{n}}{(α + β + 1)_{s+j}(α + 1)_{s}}

× \frac{(α + β + 1)_{2s+j}(α + β + 1 + n − s)_{n−s}(α + β + 1)_{j}n!}{s! j!}

× \frac{(s − n)_{(j+1)/2}(α + β + n + 1)_{(j+1)/2}}{(s − n − \frac{α + β}{2} )_{(j+1)/2} (α + s + 1)_{(j+1)/2}}

× \frac{(s − n − α)_{(j−1)/2}(β + n + 1)_{(j−1)/2}(3/2)_{(j−1)/2}}{(\frac{1}{2} + s − n − \frac{α + β}{2} )_{(j−1)/2} (s + 1)_{(j−1)j/2}(α + 2)_{(j−1)/2}}

× \frac{α − β}{α + β + 1}_{9}F_{8}[{α + 1, \frac{α + 3}{2}, α + \frac{1}{2}, \frac{α − β}{2} + 1, \frac{α − β + 1}{2}, \atop \frac{α + 1}{2}, \frac{3}{2}, \frac{α + β}{2} + 1, \frac{α + β + 3}{2},}

{α + β + n + \frac{3}{2} + \frac{j}{2}, s − n + \frac{1}{2} + \frac{j}{2}, \frac{1}{2} − s − \frac{j}{2}, \frac{1 − j}{2} \atop \frac{1 − j}{2} − β − n, α + n + \frac{3}{2} − s − \frac{j}{2}, α + s + \frac{3}{2} + \frac{j}{2}, α + \frac{3}{2} + \frac{j}{2}} ].

It seems that a derivation of RAHMAN’s formula by means of combinatorial methods is out of scope. It would first require an interpretation of the factor (α)_{k}(1 + α/2)_{k}(α + 1/2)_{k}/(α/2)_{k}(1/2)_{k} occurring in the series _{9}F_{8}. But such a factor already occurs in each classical hypergeometric series identity involving _{p}F_{p+1} for p ≥ 3, for instance in the Dougall, Whipple and Bailey identities (see [Bai, Chap. 4]).

When α = β (the case of ultraspheric polynomials), the factor _{9}F_{8} vanishes and RAHMAN’s formula greatly simplifies. For instance, for j even we get :

if 0 ≤ j ≤ n − s

L_{s+j,n−s,n} = \binom{s + j}{s, j/2, j/2}s! (\frac{j}{2})! \binom{n}{s + j/2}(n − s)!
× (α + 1 + j/2)_{n−j/2}(α + 1 + s + j/2)_{j/2}
× (α + 1 + n − s − j/2)_{j/2}(β + 1)_{n+j/2}
× (α + β + 1 + s + j)_{s}(α + β + 1 + n − s)_{n−s−j}
× (α + β + 1)_{j}(α + β + n + 1)_{j/2} ;

if n − s ≤ j ≤ 2n − 2s

L_{s+j,n−s,n} = \binom{s + j}{s, j/2, j/2}s! (\frac{j}{2})! \binom{n}{s + j/2}(n − s)!
× (α + 1 + j/2)_{n−j/2}(α + 1 + s + j/2)_{j/2}
× (α + 1 + n − s − j/2)_{j/2}(β + 1)_{n+j/2}
× (α + β + 1 + s + j)_{s}(α + β + 1 + n − s)_{n−s}
× (α + β + 1)_{2n−2s−j}(α + β + n + 1)_{j/2}.

In particular, with j = 0 we get

(1.5) L_{s,n−s,n} = (α+β +s+1)_{s}(α+β +1+n−s)_{n−s}n! (α+1)_{n}(β +1)_{n},

a formula that will be extended further in the paper.

The purpose of this article is to give a combinatorial interpretation to L_{n} and to deduce from it several analytic consequences (sections 2 and 3). As mentioned previously, we cannot derive RAHMAN’s formula, but we can, at least, evaluate an extension of (1.5), that is,

(1.6) L_{n} = (α+β +n_{2} +1)_{n_{2}} ⋯ (α+β +n_{m} +1)_{n_{m}}n_{1}! (α+1)_{n_{1}}(β +1)_{n_{1}},

when m is arbitrary and n_{1} = n_{2} +⋯+n_{m}. This is presented in section 4.

2. Weighted bipermutations. — Consider formulas (1.1) and (1.2). The expression L_{n} will first be proved to be the generating function for certain combinatorial objects, called weighted bipermutations, as follows. Let N = N_{1} + ⋯ + N_{m} be an ordered partition of a set N with |N_{i}| = n_{i} (i = 1, 2, …, m). If K is a subset of N, let k_{i} = K ∩ N_{i} and |K_{i}| = k_{i} (i = 1, 2, …, m). Next consider a permutation π of the set N. An element x of N is said to be π-incestuous, if both x and π(x) belong to the same component N_{i}. Denote by Inc π the set of all π-incestuous elements of N. Finally, define a weighted bipermutation of N = N_{1} + ⋯ + N_{m} as being a triple (π_{1}, π_{2}, K), where π_{1} and π_{2} are permutations of N and K is a subset of N that satisfies the properties :

K ⊂ Inc π_{1}  and  N \ K ⊂ Inc π_{2}.

Define the weights of a weighted bipermutation (π_{1}, π_{2}, K) to be :

w(α, β; π_{1}, π_{2}, K) = (α + 1)^{cyc π_{1}}(β + 1)^{cyc π_{2}} ;
w′(α, β; π_{1}, π_{2}, K) = (−1)^{|N\K|}(α + 1)^{cyc π_{1}}(β + 1)^{cyc π_{2}} ;

where cyc π designates the number of cycles of the permutation π.

Theorem 1. — The polynomial L_{n} defined in (1.2) is the generating function for the weighted bipermutations by the weight w′. In other words,

L_{n}(α, β) := L_{n} = ∑ w′(α, β; π_{1}, π_{2}, K)
= ∑(−1)^{|N\K|}(α + 1)^{cyc π_{1}}(β + 1)^{cyc π_{2}}.

Proof. — Let (π_{1}, π_{2}, K) be a weighted bipermutation of N = N_{1}+⋯+ N_{m}. To the pair (π_{1}, K) we can associate a sequence (π_{11}, …, π_{1m}, σ_{1}), where each π_{1i} is an injection of K_{i} into N_{i} (i = 1, 2, …, m) and σ_{1} is a permutation of the set N \ K = ∑_{i}(N_{i} \ K_{i}). Moreover, cyc π_{1} = ∑_{i} cyc π_{1i} + cyc σ_{1} and the mapping (π_{1}, K) ↦ (π_{i1}, …, π_{im}, σ_{1}) is bijective. Such a mapping has been described in [Fo-Ze]. Fig. 1 indicates the construction of such a bijection In the same manner, we associate a

[figure: K  N \ K; •  •  •; K_{1}  •  • N_{1} \ K_{1}; •  •; •  •  •; K_{2} •  •  N_{2} \ K_{2}; • •  •  •; K_{3}  •  •  N_{3} \ K_{3}; π_{1}; K  N \ K; •  •  •; •  •; •  •; •  •  •; •  •; • •  •  •; •  •; π_{11}, π_{12}, π_{13}  σ_{1}] Fig. 1

sequence (π_{21}, …, π_{2m}, σ_{2}) to π_{2}, where each π_{2i} is an injection of N_{i} \ K_{i} into N_{i} (i = 1, 2, …, m) and σ_{2} is a permutation of K.

Therefore, (α+1)_{Σ(n_{i}−k_{i})} ∏_{i}(α+1+n_{i}−k_{i})_{k_{i}} is the generating function for permutations π_{1} by number of cycles satisfying K ⊂ Inc π_{1}. In the same manner, (β + 1)_{Σk_{i}} ∏_{i}(β + 1 + k_{i})_{n_{i}−k_{i}} is the generating function for permutations π_{2} by number of cycles satisfying N \ K ⊂ Inc π_{2}. Thus, to calculate L_{n} we can first fix k, then a sequence K = (K_{1}, …, K_{m}) with |K_{i}| = k_{i} (i = 1, 2, …, m) and finally sum over all weighted bipermutations (π_{1}, π_{2}, K).

As an application of this combinatorial interpretation we can state the following corollary and also obtain another combinatorial interpretation in terms of pairs of permutations with prescribed incestuous element sets.

Corollary 1. — If |N| = n, then L_{n}(β, α) = (−1)^{|N|}L_{n}(α, β). In particular, when n is odd, L_{n}(α, α) = 0.

Proof. — Consider the transformation (π_{1}, π_{2}, K) ↦ (π_{2}, π_{1}, N \ K). Then

w′(β, α; π_{2}, π_{1}, N \ K) = (−1)^{|K|}(β + 1)^{cyc π_{2}}(α + 1)^{cyc π_{1}}
= (−1)^{|N|}(−1)^{|N\K|}(α + 1)^{cyc π_{1}}(β + 1)^{cyc π_{2}}
= (−1)^{|N|}w′(α, β; π_{1}, π_{2}, K).

Thus L_{n}(β, α) = (−1)^{|N|}L_{n}(α, β).

Corollary 2 (Second combinatorial interpretation). — One has :

L_{n} = ∑(−1)^{|N\K|}(α + 1)^{cyc π_{1}}(β + 1)^{cyc π_{2}},

where the summation is over all triples (π_{1}, π_{2}, K) with π_{1} and π_{2} permutations of N, and K a subset of N with the property that K = Inc π_{1} and N \ K = Inc π_{2}.

Proof. — Let (π_{1}, π_{2}, K) be a weighted bipermutation. If Inc π_{1} ∩Inc π_{2} is non-empty, look at the smallest element ξ in that set. Then define ϕ(π_{1}, π_{2}, K) = (π_{1}, π_{2}, K \{ξ}) or (π_{1}, π_{2}, K +{ξ}), depending on whether ξ is in K or not. In both cases ϕ(π_{1}, π_{2}, K) is a weighted bipermutation and

w′ϕ(α, β; π_{1}, π_{2}, K) = −w′(α, β; π_{1}, π_{2}, K).

Therefore the summation ∑ w′(α, β; π_{1}, π_{2}, K) over all pairs (π_{1}, π_{2}) such that Inc π_{1} ∩ Inc π_{2} = ∅ equals 0. Now as K ⊂ Inc π_{1} and N \ K ⊂ Inc π_{2}, the condition Inc π_{1} ∩ Inc π_{2} = ∅ means that K = Inc π_{1} and N \ K = Inc π_{2}.

3. Weighted derangements. — The polynomial L_{n} can also be expressed in terms of derangement polynomials as follows. Keep the same notations as in the beginning of section 2 for N, K, N_{i}, K_{i} and define a K-derangement to be a permutation σ of K such that for every x in K the elements x and σ(x) belong to different components K_{i} and K_{j} (i ≠ j). Set

D(k; α) = ∑(α + 1)^{cyc σ},

where σ ranges over all K-derangements.

Theorem 3 (third combinatorial interpretation). — One has :

(3.1) L_{n} = ∑_{K⊂N}(−1)^{|K\N|}D(n − k; α)D(k; β)

× ∏_{i}(α + 1 + n_{i} − k_{i})_{k_{i}}(β + 1 + k_{i})_{n_{i}−k_{i}}.

Proof. — Consider a weighted bipermutation (π_{1}, π_{2}, K) with K = Inc π_{1} and N \ K = Inc π_{2}. If we use the bijection described in the proof of THEOREM 1, the pair (π_{1}, K) is transformed into a sequence

\overline{}\overline{}[figure] [figure] [figure][figure] [figure] [figure] [figure] [figure] [figure: K; N \ K]^{•  •}^{K_{1}  •  •  N_{1} \ K_{1}} • •  •^{K_{2}  •  •  N_{2} \ K_{2}} [figure] •  •^{•  •}^{K_{3}  •  N_{3} \ K_{3}}^{•  •} π_{1}  \overline{}\overline{}[figure] [figure][figure] [figure] [figure] [figure] [figure] ^{K  N \ K}^{•  •}^{•  •} • •  •^{•  •} [figure] •  •^{•  •} •^{•  •} π_{11}, π_{12}, π_{13}  σ_{1} Fig. 2

(π_{11}, …, π_{1m}, σ_{1}), but this time σ_{1} is an (N \ K)-derangement, as shown in Fig. 2.

In the same way, (π_{2}, N \K) is transformed into (π_{21}, …, π_{2m}, σ_{2}) with σ_{2} being a K-derangement. Therefore

L_{n} = ∑_{K⊂N}(−1)^{|N\K|} ∑ (∏_{i}(α + 1)^{cyc π_{1i}}(β + 1)^{cyc π_{2i}})

× (α + 1)^{cyc σ_{1}}(β + 1)^{cyc σ_{2}}.

As π_{1i} (resp. π_{2i}) is an injection of K_{i} (resp. N_{i} \K_{i}) into N_{i} and σ_{1} (resp. σ_{2}) is an (N \ K)-derangement (resp. a K-derangement), the summation over the π_{1i}’s, the π_{2i}’s and the derangements σ_{1} and σ_{2} yields (3.1).

There are several consequences of this interpretation when n_{1} ≥ n_{2} + ⋯ + n_{m}. First, study the case of the strict inequality.

Lemma 1. — If k_{1} > k_{2} + ⋯ + k_{m}, then D(k, α) = 0.

Proof. — If π is a K-derangement, then π(K_{1}) ⊂ K_{2} + ⋯ + K_{m}. But |K_{i}| = k_{1} > k_{2} + ⋯ + k_{m} and there do not exist any K-derangements under this hypothesis.

Lemma 2. — Suppose n_{1} > n_{2} + ⋯ + n_{m} and let 0 ≤ k_{i} ≤ n_{i} for i = 1, …, m. Then

either k_{1} > k_{2} + ⋯ + k_{m}, or (n_{1} − k_{1}) > (n_{2} − k_{2}) + ⋯ + (n_{m} − k_{m}).

Proof. — If k_{1} ≤ k_{2} + ⋯ + k_{m}, then n_{1} − k_{1} > n_{2} + ⋯ + n_{m} − k_{1} > n_{2} − k_{2} + ⋯ + n_{m} − k_{m}.

Proposition 1. — If n_{1} > n_{2} + ⋯ + n_{m}, then L_{n} = 0.

Proof. — With the foregoing hypothesis, either k_{1} > k_{2} + ⋯ + k_{m} or (n_{1} − k_{1}) > (n_{2} − k_{2}) + ⋯ + (n_{m} − k_{m}). Then, either D(k; β) = 0, or D(n − k; α) = 0. Therefore, (3.1) shows that L_{n} = 0.

Corollary. — If n_{1} ≠ n_{2}, then L_{n_{1},n_{2}} = 0.

This is precisely the orthogonality relation.

4. The evaluation of L_{n} for n_{1} = n_{2} + ⋯ + n_{m}. — Consider again the summation (3.1). When n_{1} = n_{2} + ⋯ + n_{m}, the inequality k_{1} < k_{2} + ⋯ + k_{m} implies n_{1} − k_{1} > (n_{2} − k_{2}) + ⋯ + (n_{m} − k_{m}). Therefore, the factor D(n − k; α) vanishes for such a sequence k. In the same manner, if k_{1} > k_{2} + ⋯ + k_{m}, then D(k; β) = 0. The summation (3.1) can then be restricted to those sequences k satisfying

(4.1)  0 ≤ k_{1} = k_{2} + ⋯ + k_{m} ≤ n_{1} = n_{2} + ⋯ + n_{m}.

In particular, for m = 2 and n_{1} = n_{2} = n we obtain :

(4.2) L_{n,n} = ∑_{k=0}^{n}D(n − k, n − k, α)D(k, k, β)

× (\binom{n}{k}(α + 1 + n − k)_{k}(β + 1 + k)_{n−k})^{2} .

We will have a more precise evaluation further in the paper. For the time being, let us compare (4.2) with the classical evaluation of the integral :

\begin{aligned}I_{n,n} & = ∫_{−1}^{+1}(1 − x)^{α}(1 + x)^{β}(P_{n}^{(α,β)}(x))^{2}dx \\ & = \frac{2^{1+α+β}Γ(1 + α + n)Γ(1 + β + n)}{n! (1 + α + β + 2n)Γ(1 + α + β + n)}. \end{aligned}

(See, e.g., [Rai, p. 260 (11)].) By comparison with the definition of L_{n,n} (formula (1.2)),

I_{n,n} = \frac{2^{1+α+β}}{n! n! (α + β + 2)_{2n}} \frac{Γ(α + 1)Γ(β + 1)}{Γ(α + β + 2)}L_{n,n},

so that

(4.3)  L_{n,n} = (α + β + n + 1)_{n}n! (α + 1)_{n}(β + 1)_{n}.

This formula will be a consequence of the next theorem.

Theorem 4. — When n_{1} = n_{2} + ⋯ + n_{m}, then

L_{n} = (α + β + n_{2} + 1)_{n_{2}} ⋯ (α + β + n_{m} + 1)_{n_{m}}n_{1}! (α + 1)_{n_{1}}(β + 1)_{n_{1}}.

Proof. — As just noticed, the summation (3.1) can be restricted to the sequences k satisfying (4.1). But if (π_{1}, π_{2}, K) is a triple with |K_{1}| = |K_{2} +⋯+K_{m}|, then |N \K| = |N_{1} +⋯+N_{m} \(K_{1} +⋯+K_{m})| = |N_{1} \ K_{1}| + ⋯ + |N_{m} \ K_{m}| = 2|N_{1} \ K_{1}|, so that the sign (−1)^{|N\K|} is always equal to 1. Therefore,

L_{n} = ∑(α + 1)^{cyc π_{1}}(β + 1)^{cyc π_{2}},

where π_{1} and π_{2} are permutations of N and π_{1}(K_{i}) ⊂ N_{i}, π_{1}(N_{i} \ K_{i}) ⊂ N \ N_{i}, π_{2}(N_{i} \ K_{i}) ⊂ N_{i}, π_{2}(K_{i}) ⊂ N \ N_{i} for i = 1, 2, …, m.

Let M_{1} = K_{1} + ∑_{j≥2}(N_{j} \ K_{j}) and M_{2} = N_{1} \ K_{1} + ∑_{j≥2} K_{j}. Note that |M_{1}| = |M_{2}| = |N_{1}|. Our purpose is now to construct a bijection that will explain the occurrence of each factor in the right-hand side of the THEOREM 4 formula. The reader is advised to follow the construction by looking at the geometric representations of the mappings in Fig. 3

(i) For each i = 2, …, m let f_{i} be the mapping of N_{i} into itself defined by :

f_{i} |_{K_{i}}= π_{1} |_{K_{i}}  and  f_{i} |_{N_{i}\K_{i}}= π_{2} |_{N_{i}\K_{i}} .

As π_{1}(K_{i}) ⊂ N_{i} and π_{2}(N_{i} \ K_{i}) ⊂ N_{i}, the pair (K_{i}, f_{i}) is a so-called Jacobi endofunction (see [Fo-Le]). Denote by a(f_{i}) (resp. b(f_{i})) the number of cycles of f_{i} all vertices of which are in K_{i} (resp. (N_{i} \ K_{i}) and let the weight of (K_{i}, f_{i}) be defined by

w(K_{i}, f_{i}) = (α + 1)^{a(f_{i})}(β + 1)^{b(f_{i})}.

As shown in [Fo-Le, théorème 1]

(4.4)  ∑ w(K_{i}, f_{i}) = (α + β + n_{i} + 1)_{n_{i}},

the summation being over all Jacobi endofunctions on N_{i}.

(ii) Consider x ∈ N_{1} \ K_{1}. As π_{1}(N_{1} \ K_{1}) ⊂ N_{2} + ⋯ + N_{m} and π_{1}(K_{i}) ⊂ N_{i} (i = 2, …, m), sooner or later the iterates π_{1}^{k}(x) will hit the set ∑_{j≥2}(N_{j} \ K_{j}). Let k(x) be the smallest integer satisfying

π_{1}^{k(x)}(x) ∈ ∑_{j≥2}(N_{j} \ K_{j}) and define γ(x) = π_{1}^{k(x)}(x). Clearly

γ : N_{1} \ K_{1} → ∑_{j≥2}(N_{j} \ K_{j})

[figure: K; N \ K; •; N_{1}  •  •  •; •; •; N_{2}  •  •; N_{3}  •  •; π_{1}]  [figure] [figure] [figure]  [figure] [figure] [figure] \overline{}\overline{}[figure: K; N \ K] • ^{•  •  •} • • ^{•  •}^{•  [figure] •} π_{2}

[figure]  \overline{}\overline{}\overline{}^{K  N \ K} •^{N_{1}  •  •  •} • •^{N_{2}  •  •}^{N_{3}  •  [figure] •} f_{2} and f_{3}  [figure: K  N \ K; •; •  •  •; •; •; •  •; •  •; δ and γ]

[figure] [figure] [figure] [figure]^{K  N \ K} •^{N_{1}  •  •  •} • •^{N_{2}  •  •}^{N_{3}  •  [figure] •} σ_{1}  [figure: K  N \ K; •; •  •  •; •; •; •  •; •  •; σ_{2}]

Fig. 3 is a bijection. In the same manner, define a bijection δ : K_{1} → ∑_{j≥2} K_{j} by means of π_{2}.

(iii) With the pair (γ, δ) we can then make up a bijection of N_{1} onto the union ∑_{j≥2} N_{j}.

(iv) Consider the cycles of π_{1}. All the cycles that intersect M_{1} but sometimes leave M_{1} will be made purely M_{1} by cancelling all the portions that leave M_{1}. This gives a permutation σ_{1} : M_{1} → M_{1}.

(v) In the same manner, obtain a permutation σ_{2} : M_{2} → M_{2}.

Remembering the definitions of a(f_{i}) and b(f_{i}) given in (i) we see that to each triple (π_{1}, π_{2}, K) there corresponds a sequence

(K_{2}, f_{2}, …, K_{m}, f_{m}, γ, δ, σ_{1}, σ_{2})

with

cyc π_{1} = a(f_{2}) + ⋯ + a(f_{m}) + cyc σ_{1} ;
cyc π_{2} = b(f_{2}) + ⋯ + b(f_{m}) + cyc σ_{2}.

Accordingly, w(α, β; π_{1}, π_{2}, K) = w(K_{2}, f_{2}) ⋯ w(K_{m}, f_{m})(α + 1)^{cyc σ_{1}}(β + 1)^{cyc σ_{2}}.

It can be verified that the correspondence between triples and sequences defined by (i)–(v) is one-to-one. Hence

∑ w(α, β; π_{1}, π_{2}, K)

= ∑ w(K_{2}, f_{2}) ⋯ ∑ w(K_{m}, f_{m}) ∑_{γ,δ} 1 ∑_{σ_{1}}(α + 1)^{cyc σ_{1}} ∑_{σ_{2}}(β + 1)^{cyc σ_{2}}

= (α + β + n_{2} + 1)_{n_{2}} ⋯ (α + β + n_{m} + 1)_{n_{m}} n_{1}! (α + 1)_{n_{1}}(β + 1)_{n_{1}}.

Remark. — Note that for m = 2 and n_{1} = n_{2} = n THEOREM 4 yields identity (4.3).

5. Concluding remarks. — The problem of the linearization of the classical orthogonal polynomials has been studied again recently by means of combinatorial methods. ASKEY and his coauthors [As-Is, As-Is-Ko] have already obtained several significant results concerning the Hermite, Laguerre and Meixner polynomials. AZOR, GILLIS and VICTOR [Az-Gi-Vi] found an elegant set-up for the Hermite polynomials. The two authors of the present paper [Fo-Ze] have completed the work of ASKEY and his coauthors as far as the (generalized) Laguerre polynomials are concerned by exploiting a β-extension of the MacMahon Master Theorem. ZENG [Ze] has further extended the works of ASKEY and the two authors and proved new positivity results concerning the Meixner, Krawtchouk and Charlier polynomials. GILLIS and his coauthors [Gi-Je-Ze] reproved several positivity results on the Legendre polynomials. Some of their arguments have been implicitly used in the present paper. RAHMAN’s formula, as said in the introduction, should discourage several researchers. Formula (3.1) seems to indicate that a new algebraic tool has to be found to handle the product of two derangement polynomials. There is also a linearization coefficient formula for the ultraspheric polynomials found by HS^{}Ü [Hs], more compact than RAHMAN’s formula for α = β, but not so easy to be tackled by combinatorial methods. The only hope for the time being seems to be the symmetric function approach due to ZENG. He has already got an explicit formula for a single derangement polynomial that led to the positivity result for the Krawtchouk polynomials.

Note added in 1994. — The article [Ze] has been updated in the reference list. Notice that the linearization coefficients for the class of Sheffer polynomials has been thoroughly studied by Zeng [Ze92]. An interesting connection between linearization coefficeints for Jacobi polynomials and permutation pair counting has been derived in [Ze91]. The Rahman formula remains untamed in the combinatorial environment.

[Ze91] ZENG (Jiang). — Counting a pair of permutations and the linearization coefficients for Jacobi polynomials, Actes de l’Atelier de Combinatoire francoquébecois, Publ. LACIM, no. 10, Université du Québec à Montréal, 1991.

[Ze92] ZENG (Jiang). — Weighted derangements and Sheffer polynomials, Proc. London Math. Soc., t. 65, 1992, p. 1–22.

REFERENCES

[As-Is] ASKEY (Richard) and ISMAIL (Mourad E.H.). — Permutation problems and

special functions, Canad. J. Math., t. 28, 1976, p. 853–874.

[As-Is-Ko] ASKEY (Richard), ISMAIL (Mourad E.H.) and KOORNWINDER (T.). — Weighted permutation problems and Laguerre polynomials, J. Combinatorial Theory, Ser. A, t. 25, 1978, p. 277–287.

[Az-Gi-Vi] AZOR (R.), GILLIS (J.) and VICTOR (J.D.). — Combinatorial application of

Hermite polynomials, SIAM J. Math. Anal., t. 13, 1982, p. 879–890.

[Bai] BAILEY (W.N.). — Generalized Hypergeometric Series. — Cambridge Univ. Press, 1936.

[Er] ERD^{}ÉLYI (A.) et al. — Higher Transcendental Functions (Bateman Manuscript

Project), 3 vol. — New York, McGraw-Hill, 1953.

[Fo-Le] FOATA (Dominique) et LEROUX (Pierre). — Polynômes de Jacobi, interprétation combinatoire et fonction génératrice, Proc. Amer. Math. Soc., t. 87, 1983, p. 47– 53.

[Fo-Ze] FOATA (Dominique) and ZEILBERGER (Doron). — Weighted derangements and Laguerre polynomials, in Séminaire Lotharingien de combinatoire (Bayreuth, Erlangen, Strasbourg), 8^{e} session [D. Foata, éd. ; Sainte-Croix-aux-Mines. 23–28 mai 1983], p. 17–25. — Publ. IRMA Strasbourg, 229/S–08, 1984.

[Gi-Je-Ze] GILLIS (J.), JEDWAB (J.) and ZEILBERGER (D.). — A combinatorial interpretation of the integral of the product of Legendre polynomials, manuscrit, Weizmann Inst., 1987.

[Hs] HS^{}Ü (Hsien-Yü). — Certain integrals and infinite series involving ultraspheric polynomials and Bessel functions, Duke Math. J., t. 4, 1938, p. 374–383.

[Ra] RAHMAN (Mizan). — A non-negative representation of the linearization coefficients of the product of Jacobi polynomials, Canad. J. Math., t. 33, 1981, p. 915–928.

[Rai] RAINVILLE (E.D.). — Special Functions. — New York, Chelsea, 1960.

[Sz] SZEG^{}Ö (Gabor). — Orthogonal Polynomials. — Providence, R.I., Amer. Math. Soc., 1939 (Amer. Math. Soc. Colloq. Publ., 23) [second printing of the fourth edition : 1978].

[Ze] ZENG (Jiang). — Linéarisation de produits de polynômes de Meixner, Krawtchouk et Charlier, S.I.A.M. J. Math. Anal., t. 21, 1989, p. 1349–1368.

Dominique Foata, Département de mathématique, Université Louis-Pasteur, 7, rue René-Descartes, F-67084 Strasbourg, France.

Doron Zeilberger,

Department of Mathematics,

Drexel University,

Philadelphia, Pennsylvania 19104, U.S.A. now at Temple University, Philadelphia, Pennsylvania 19122, U.S.A.