A Combinatorial Interpretation of Lommel Polynomials and Their Derivatives

P. FEINSILVER, J. MCSORLEY

Department of Mathematics, Southern Illinois University, Carbondale, IL 62901 USA

R. SCHOTT

CRIN, INRIA-Lorraine, Université Henri Poincaré, 54506 Vandoeuvre-lès-Nancy, France

Abstract. In this paper we present interpretations of Lommel polynomials and their derivatives. A combinatorial interpretation uses matchings in graphs. This gives an interpretation for the derivatives as well. Then Lommel polynomials are considered from the point of view of operator calculus. A step-3 nilpotent Lie algebra and finite-difference operators arise in the analysis.

I. Introduction

Interpretations of orthogonal polynomials in terms of combinatorial models has received a lot of attention over the last decade. S. Dulucq and L. Favreau [3] recently presented a combinatorial model for Bessel polynomials. A general combinatorial theory for orthogonal polynomials has been developed in the work of X.G. Viennot [12], de Médicis and Viennot [2], and in the theory of species, formalized by F. Bergeron [1], A. Joyal [6][7], G. Labelle [8] and P. Leroux [9] . An analytical study of the zeros of Lommel polynomials may be found in [5]. The basics of the operator calculus approach are in [4].

Lommel polynomials arise in the study of Bessel functions as the linearization coefficients expressing J_{ν+n} in terms of J_{ν} and J_{ν−1}, cf. Watson [13]. They may be given explicitly in the form

R_{n}(ξ, ν) = ∑_{k=0}^{[n/2]} \binom{n − k}{k}(−1)^{k} \frac{Γ(ν + n − k)}{Γ(ν + k)} (2/ξ)^{n−2k}

Changing variables to ϕ_{n}(x, ε) = R_{n}(−2/ε, −x/ε), with ε understood as a parameter, we have the recurrence

xϕ_{n} = ϕ_{n+1} + εnϕ_{n} + ϕ_{n−1}  (1.1)

with initial conditions ϕ_{−1} = 0, ϕ_{0} = 1. Thus, these are a family of orthogonal polynomials. They have the form

ϕ_{n}(x, ε) = ∑_{k} \binom{n − k}{k} (−1)^{k} (x − kε) ⋯ (x − (n − k − 1)ε)  (1.2)

In this paper we present some interpretations of Lommel polynomials. We proceed from a general approach and then specialize to the case of Lommel polynomials. For example, note that with ε = 0 in equation (1.1), we have the recurrence for Chebyshev polynomials. In fact, with ε = 0, the polynomials ϕ_{n} become the Chebyshev polynomials of the second kind.

II. Basic construction: matchings

Let G be a simple graph on n vertices with vertex labels 1 to n and weight w_{i} on vertex i, 1 ≤ i ≤ n. A matching, M, of G is a set of disjoint edges, a set of edges pairwise having no vertex in common. If a vertex i is incident to an edge of M, we write i ∈ M, otherwise i ∉ M. We define the weight of M, W_{G}(M), to be

W_{G}(M) = ∏_{i∉M} w_{i}

If G has an even number of vertices and M is a perfect matching of G, in other words, if all vertices of G lie in M, then W_{G}(M) is defined to equal 1. Note that every graph has the empty matching, containing no edges.

For the rest of this work, we will take G to be P_{n}, the path on n vertices, running from left to right. We denote W_{G}(M), then, by W_{n}(M), the weight of the matching M of P_{n}.

Define

P_{n} = ∑_{M} (−1)^{|M|} W_{n}(M)

with |M| the number of edges in M, summing over all matchings M of P_{n}.

2.1 Proposition. P_{n} satisfies the recurrence

P_{n+1} = w_{n+1}P_{n} − P_{n−1}

Proof: Let M be a matching of P_{n+1}. Either M does not contain the edge (n, n + 1) or it does. Every case where the edge (n, n + 1) is not in M corresponds to some matching on n vertices with the additional factor of w_{n+1} since n + 1 is in none of them. On the other hand, in all matchings including the edge (n, n + 1), removing it leaves a matching on n − 1 vertices with the removal of the edge contributing a minus sign.

We define P_{−1} = 0, P_{0} = 1. From the Proposition, this gives P_{1} = w_{1}, which agrees with the scheme, since the only matching of P_{1}, a single vertex, is the empty matching, with weight w_{1}. Similarly, we have from the Proposition that P_{2} = w_{1}w_{2} − 1. The graph P_{2} has two matchings — the empty matching with weight w_{1}w_{2} and the matching which contains the single edge (1, 2) of weight 1.

Now recall that a three-term recurrence of the form

xϕ_{n} = ϕ_{n+1} + b_{n}ϕ_{n} + c_{n}ϕ_{n−1}

with c_{n} ≥ 0 yields a sequence of orthogonal polynomials. In Proposition 2.1, we can introduce a variable x either additively or multiplicatively into the weights. I.e., consider

(x − u_{n+1})P_{n} = P_{n+1} + P_{n−1}

which means that x as the eigenvalues of the corresponding tridiagonal matrices are the zeros of the polynomials P_{n}. Or we can write w_{n+1} = xu_{n+1} with the recurrence taking the form

xu_{n+1}P_{n} = P_{n+1} + P_{n−1}

for example, with constant u_{n+1} = 2, we have the recurrence for the Chebyshev polynomials.

2.1 Lommel polynomials and their derivatives

The recurrence (1.1) corresponds to the weights w_{i} = x − (i − 1)ε. For fixed ε, we treat ϕ_{n} as a function of one variable, x, and denote it by R_{n}. Here are some explicit expressions:

\begin{aligned}R_{1} & = x \\ R_{2} & = x^{2} − εx − 1 \end{aligned}  \begin{aligned}R_{3} & = x^{3} − 3εx^{2} + 2ε^{2}x − 2x + 2ε \\ R_{4} & = x^{4} − 6εx^{3} + 11ε^{2}x^{2} − 6ε^{3}x − 3x^{2} + 9εx − 6ε^{2} + 1 \end{aligned}

Now, let G be a simple graph with n vertices labelled 1 to n having weight x−(i−1)ε on vertex i. Define a k-extended matching of G as a set { v_{1}, …, v_{k}, M } of k vertices of G together with a matching M such that v_{j} ∉ M for 1 ≤ j ≤ k. I.e., no vertex v_{j} is incident to any edge in M.

Denoting the k-extended matching { v_{1}, …, v_{k}, M } by E_{M}, M is called the matching of E_{M}. For a vertex v ∈ G, we write v ∈ E_{M} if either v = v_{j} for some j, 1 ≤ j ≤ k, or v ∈ M. Let |E_{M}| = |M| denote the number of edges in the matching of E_{M}.

The weight of E_{M}, W_{G}(E_{M}) is given by:

W_{G}(E_{M}) = ∏_{i∉E_{M}}(x − (i − 1)ε)

As above, if every vertex of G lies in E_{M}, then W_{G}(E_{M}) = 1. We take G = P_{n}, the path, and denote W_{G}(E_{M}) by W_{n}(E_{M}).

2.1.1 Derivatives of Lommel polynomials

For a combinatorial interpretation of the kth derivative R_{n}^{(k)}, start from the contribution of the matching M, W_{n}(M) = ∏_{i∉M}(x − (i − 1)ε). Consider W_{n}(M) as a function of x. Since the derivative of each factor in W_{n}(M) is 1, for the kth derivative we have, the summation taken over all k-subsets of vertices { v_{i_{1}}, …, v_{i_{k}} } of G such that no vertex v_{i_{j}} is in M,

W_{n}^{(k)}(M) = ∑_{\{i_{1},...,i_{k}\}} \frac{k! W_{n}(M)}{∏_{j}(x − (i_{j} − 1)ε)}

= k! ∑ ; {\{i_{1}, …, i_{k}\} \atop v_{i_{j}} ∉ M} W_{n}(\{i_{1}, …, i_{k}, M\})

= k! ∑_{E_{M}} W_{n}(E_{M})

this last summation taken over all k-extended matchings E_{M} with matching M. Hence

2.1.1.1 Proposition. The kth derivative of the Lommel polynomial R_{n} is given by

R_{n}^{(k)} = k! ∑_{E}(−1)^{|E|} W_{n}(E)

where the summation is over all k-extended matchings of P_{n}, with |E| denoting the number of edges in the matching of E.

Note that with k = 0 we recover the original case of R_{n}, considering a matching as a 0-extended matching.

Example. Consider the second derivative of R_{4}. We have

\begin{aligned}R_{4} & = x^{4} − 6εx^{3} + 11ε^{2}x^{2} − 6ε^{3}x − 3x^{2} + 9εx − 6ε^{2} + 1 \\ \frac{1}{2} R′′_{4} & = 6x^{2} − 18εx + 11ε^{2} − 3 \end{aligned}

The 2-extended matchings with corresponding weights are given in the following table:

2 − ext. match.  weight
{1, 2, ∅}  (x − 2ε)(x − 3ε)
{1, 3, ∅}  (x − ε)(x − 3ε)
{1, 4, ∅}  (x − ε)(x − 2ε)
{2, 3, ∅}  x (x − 3ε)
{2, 4, ∅}  x (x − 2ε)
{3, 4, ∅}  x (x − ε)
{3, 4, (1, 2)}  1
{1, 4, (2, 3)}  1
{1, 2, (3, 4)}  1

III. Lommel polynomials and finite-difference calculus

Here we show how to write Lommel polynomials in terms of a recurrence with operator coefficients. Recall that the solution to the recurrence

f_{n+1} = af_{n} + bf_{n−1}

with initial conditions f_{−1} = 0, f_{0} = 1, is given by

f_{n} = ∑_{k} \binom{n − k}{k}a^{n−2k}b^{k}

(In other terms, we can express the solution to

f_{n+1} = af_{n} − bf_{n−1}

with the same initial conditions, in terms of Chebyshev polynomials of the second kind: f_{n} = b^{n/2}U_{n}(a/(2\sqrt{b})).) This formula holds for a and b operators, e.g., matrices, with f_{0} = I, the identity, as long as a and b commute. If they do not commute, we apply them on different sides:

3.1 Proposition. For operators a and b, the solution to the recurrence

f_{n+1} = f_{n}a + bf_{n−1}

with initial conditions f_{−1} = 0, f_{0} = I, is given by

f_{n} = ∑_{k} \binom{n − k}{k}b^{k}a^{n−2k}

And similarly with a acting on the left and b on the right.

For Lommel polynomials, introduce the shift operator T_{ε} acting on functions f by

T_{ε}f(x) = f(x − ε)

We denote the operator of multiplication by x by X. Using the relation

(XT_{ε})^{n}1 = x(x − ε)(x − 2ε) ⋯ (x − (n − 1)ε)

where 1 denotes the constant function 1, we have from equation (1.2),

R_{n}(x) = ∑_{k} \binom{n − k}{k}(−T_{ε})^{k}(XT_{ε})^{n−2k} 1  (3.1)

Comparing with Proposition 3.1, we see 3.2 Proposition. Define operators F_{n} by the recurrence

F_{n+1} = F_{n}XT_{ε} − T_{ε}F_{n−1}

with F_{−1} = 0, F_{0} = I. Then the Lommel polynomials are given by

R_{n}(x) = F_{n} 1

For example,

F_{1} = XT_{ε} , F_{2} = (XT_{ε})^{2} − T_{ε} , F_{3} = (XT_{ε})^{3} − 2T_{ε}XT_{ε}

etc.

Another approach to expressions of the form

∑_{k} \binom{n − k}{k}a^{n−2k}b^{k}

involves the nilpotent Lie algebra generated by the operators D^{2} = (d/dx)^{2} and X. The commutator [D^{2}, X] = D^{2}X − XD^{2} = 2D, while [D, X] = 1. Thus, { D^{2}, D, X, 1 } form the basis for a nilpotent Lie algebra of step 3, i.e., all commutators of length greater than 3 vanish. Now,

3.3 Proposition. Let f_{n}(x) = ∑_{k} \binom{n − k}{k}b^{k}x^{n−2k}. Then

f_{n}(x) = _{0}F_{1} ({− \atop −n} | −bD^{2}) x^{n}

Proof: Expanding the _{0}F_{1} function gives

∑_{k} \frac{(−bD^{2})^{k}}{(−n)_{k} k!} x^{n} = ∑_{k} \frac{(n − k)!}{n! k!} b^{k}D^{2k} x^{n}

from which the result is clear.

To see the connection with Lommel polynomials, first we review the basic operator calculus needed. Consider the formal series in one variable

V (z) = ∑_{n=0}^{∞} a_{n}z^{n}

this is the symbol of the generalized differential operator V (D), which acts on polynomials in the variable x. This satisfies

[V (D), X] = V′(D)  (3.2)

V′(z) denoting the derivative of the series V (z). We assume that a_{0} = 0, a_{1} = 1. Thus, V′ has a formal multiplicative inverse 1/V′(z), which we denote by W (z). From equation (3.2), we see that, defining ξ = XW (D), we have

[V (D), ξ] = 1

From which the usual rules of polynomial calculus follow, such as

V ξ^{n}1 = nξ^{n−1}1

The shift operator T_{ε} has symbol e^{−εz}. Thus, for the operator ξ = XT_{ε}, we have the corresponding operator V (D) with symbol

V (z) = \frac{1}{ε} (e^{εz} − 1)  (3.3)

which is the (forward) finite-difference operator with step size ε. Next, define the finite-difference Laplacian with symbol

Δ_{ε}(z) = \frac{1}{ε^{2}} (e^{εz} + e^{−εz} − 2)

Now we have

3.4 Proposition. The Lommel polynomials R_{n}(x) satisfy

R_{n}(x) = _{0}F_{1} ({− \atop −n} | Δ_{ε}) ξ^{n}1

with ξ = XT_{ε}.

Proof: Write equation (3.1) in the form

R_{n}(x) = ∑_{k} \binom{n − k}{k}(−T_{ε})^{k}ξ^{n−2k}1

Then, as in Proposition 3.3,

R_{n}(x) = _{0}F_{1} ({− \atop −n} | T_{ε}V (D)^{2}) ξ^{n}1

with V (D) the difference operator in equation (3.3). Now calculating with symbols, we see that

T_{ε}(z)V (z)^{2} = \frac{1}{ε} (e^{εz} − 1)(1 − e^{−εz} ) = Δ_{ε}(z)

and hence the result.

IV. Concluding remarks

It would be interesting to consider the combinatorial approach for other families of orthogonal polynomials as indicated in §II. In [4], the function _{0}F_{1} arises naturally in the sl(2) calculus yielding eigenfunctions of the radial Laplacian in Euclidean space. Here, we see that the Lommel polynomials correspond to the finite-difference Laplacian. It appears that the Lommel polynomials play a natural role in harmonic analysis on a lattice and merit further study in this context.

References

1. F. Bergeron, A Combinatorial Outlook on Symmetric Functions, Journal of Combinatorial Theory, Series A, vol 50, 2, 1989, 226–234.

2. A. de Médicis et X.G. Viennot, Moments des q-Polynômes de Laguerre et la Bijection de Foata-Zeiberger, Advances in Applied Mathematics 15, 262-304 1994.

3. S. Dulucq and L. Favreau, Un modèle combinatoire pour les polynômes de Bessel, Séminaire Lotharingien de Combinatoire (1990), Publication Université de Strasbourg, 1991.

4. P. Feinsilver and R. Schott, Agebraic Structures and Operator Calculus, Volume 1: Representations and Probability Theory, Kluwer 1993.

5. P. Feinsilver and R. Schott, On Bessel functions and rate of convergence of zeros of Lommel polynomials, Mathematics of Computation 59, 199, 153-156, 1992.

6. A. Joyal, Une théorie combinatoire des séries formelles, Adv. in Math. 42, 1-82, 1981.

7. A. Joyal, Foncteurs analytiques et espèces de structures, Proceedings, Colloque de Comb. Enumer. UQAM, 1985, Lecture Notes in Math. 1234, 126-159, Springer Verlag, 1986.

8. G. Labelle, Une nouvelle démonstration combinatoire des formules d’inversion de Lagrange, Adv. in Math. 42, 217-247, 1981.

9. P. Leroux and V. Strehl, Jacobi Polynomials: combinatorics of the basic identities, Discrete Math., 57, 167-187, 1985.

10. G.C. Rota (ed.), Finite operator calculus, Academic Press, 1975.

11. G. Szëgo, Orthogonal polynomials, AMS Colloq. Publ., 1975.

12. X.G. Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, Notes de cours, Université du Quebec à Montréal, 1983.

13. G.N. Watson, A Treatise on the Theory of Bessel Functions, Cambridge University Press, 1980.