Generating Orthogonal Polynomials and their Derivatives using

Vertex|Matching-Partitions of Graphs

John P. McSorley, Philip Feinsilver

Department of Mathematics Southern Illinois University Carbondale, IL 62901-4408

USA

 mcsorley60@hotmail.com
 pfeinsil@math.siu.edu

and

René Schott

IECN and LORIA Université Henri Poincaré 54506 Vandoeuvre-lès-Nancy

France

  Rene.Schott@loria.fr

Abstract

A vertex|matching-partition (V |M) of a simple graph G is a spanning collection of vertices and independent edges of G. Let vertex v ∈ V have weight w_{v} and edge e ∈ M have weight w_{e}. Then the weight of V |M is w(V |M) = ∏_{v∈V} w_{v} · ∏_{e∈M} w_{e}. Define the vertex|matching-partition function of G as W(G) = ∑_{V |M} w(V |M). In this paper we study this function when G is a path and a cycle. We generate all orthogonal polynomials as vertex|matching-partition functions of suitably labelled paths, and indicate how to find their derivatives in some cases. Here Taylor’s Expansion is used and an application to associated polynomials is given. We also give a combinatorial interpretation of coefficients in the case of multiplicative and additive weights. Results are extended to the weighted cycle.

1 Vertex|Matching-Partition Function, 3-Term Recurrence for Orthogonal Polynomials

In this paper we define a vertex|matching-partition and the vertex|matchingpartition function of a simple graph. The vertex|matching-partition function of a path was briefly discussed without development in Viennot [7, pp. VI-9], (see also Viennot [8]). Here we develop this idea further by showing how to generate any orthogonal polynomial as the vertex|matching-partition function of a suitably weighted path; many examples are given. We extend our results to the vertex|matching-partition function of a weighted cycle. Finally, we show how to generate derivatives of some orthogonal polynomials, and consider an application to the associated polynomials of Van Assche [6].

Let G be a simple graph with vertices V (G) and edges E(G). A matching M of G is a set of edges in E(G), no two of which are incident. For a matching M of G, let V_{M} = V denote the vertices of G which are not incident to any edge in M. Call the pair V |M a vertex|matching-partition or a vm-partition of G. For every v ∈ V (G) and every vm-partition V |M of G, either v ∈ V or v is incident to an edge in M which (with a slight abuse of notation) we write as v ∈ M, but not both. Call V the vertex-set and M the matching of the vm-partition V |M. Let V_{∅} denote the empty vertex-set, and M_{∅} the empty matching.

Let v ∈ V (G) have weight w_{v}, and let e = (u, v) ∈ E(G) have weight w_{e} = w_{(u,v)}. Now define the weight of a vm-partition V |M as

w(V |M) = ∏_{v∈V} w_{v} · ∏_{e∈M} w_{e},  (1)

where products over V_{∅} and M_{∅} are 1.

Finally define the vm-partition function of G as:

W(G) = ∑_{V |M} w(V |M),

where the summation is over all vm-partitions V |M of G.

Weighted Path P (n)

Let λ and μ be arbitrary variables, and let P (n) be the weighted path on the n + 1 vertices {0, 1, …, n}, see below. The vertex labels {0, 1, …, n} are shown below the path. The weights of the vertices and edges are shown above the path. We call this Model I.

•  •  •  •  •  • λ μw_{(0,1)} w_{1} w_{(1,2)} w_{2} w_{(2,3)} w_{3} ⋯ w_{n−1} w_{(n−1,n)} w_{n}^{0}  ^{1}  ^{2}  ^{3}  ^{n−1}  ^{n}

Let P_{n} be the vm-partition function of P (n), i.e.,

P_{n} = W(P (n)).

With P_{−1} = μ and P_{0} = λ we have,

Theorem 1.1 For n ≥ 1,

P_{n} = w_{n}P_{n−1} + w_{(n−1,n)}P_{n−2}.  (2)

Proof. Note that P_{0} = W(P (0)) = λ and P_{1} = W(P (1)) = λw_{1} +μw_{(0,1)}. Now, for n ≥ 1, consider vertex n, the last vertex of P (n); it has weight w_{n}. Let V |M be an arbitrary vm-partition of P (n), so either n ∈ V or n ∈ M.

If n ∈ V then w_{n} occurs as a factor of w(V |M). Upon factoring out w_{n} we obtain the weight of a vm-partition of P (n − 1); conversely, given the weight of any vm-partition of P (n − 1), its product with w_{n} gives the weight of a vm-partition of P (n) which contains n in its vertex-set. This accounts for the first term in the right-hand side of (2).

If n ∈ M then w_{(n−1,n)} occurs as a factor in w(V |M) and, by a similar argument to above, the sum of the weights of all such vm-partitions is w_{(n−1,n)}P_{n−2}, the second term in the right-hand side of (2).

Thus

P_{n} = w_{n}P_{n−1} + w_{(n−1,n)}P_{n−2}
= ∑_{n∈V^{V |M}} w(V |M) + ∑_{n∈M^{V |M}} w(V |M),

where the first summation is over all vm-partitions of P (n) which contain vertex n in its vertex-set, V; the second over all vm-partitions of P (n) which contain n in its matching, M. We say that equation (2) comes from decomposing P_{n} at vertex n.

Thus any sequence of polynomials which obey the 3-term recurrence (2) can be obtained as the sequence of vm-partition functions of P (n); in particular orthogonal polynomials obey such a 3-term recurrence.

Example 1

P_{0} = W(P (0)) = λ P_{1} = W(P (1)) = λw_{1} + μw_{(0,1)} P_{2} = W(P (2)) = λw_{1}w_{2} + μw_{2}w_{(0,1)} + λw_{(1,2)} P_{3} = W(P (3)) = λw_{1}w_{2}w_{3}+μw_{2}w_{3}w_{(0,1)}+λw_{3}w_{(1,2)}+λw_{1}w_{(2,3)}+μw_{(0,1)}w_{(2,3)}.

For example P_{3} comes from P (3), shown below

•  •  •  • λ μw_{(0,1)} w_{1} w_{(1,2)} w_{2} w_{(2,3)} w_{3}^{0}  ^{1}  ^{2}  ^{3}

which has 5 vm-partitions:

vm-partition

• • • •

0 1 2 3

M_{∅}

• •

2 3

• •

0 1

• •

0 3

• •

1 2

• •

0 1

• •

2 3

V_{∅} • • 0 1 • • 2 3

weight

λw_{1}w_{2}w_{3}

w_{2}w_{3}μw_{(0,1)}

λw_{3}w_{(1,2)}

λw_{1}w_{(2,3)}

μw_{(0,1)}w_{(2,3)}

We now consider the two fundamental solutions to recurrence (2), f_{n} and g_{n}.

The first fundamental solution, f_{n}, of recurrence (2) is the solution with initial values f_{−1} = μ = 0 and f_{0} = λ = 1. Thus, from Model I, decomposing P_{n} at vertex 0, f_{n} is the vm-partition function of

(3)

•  •  •  •  • w_{1} w_{(1,2)} w_{2} w_{(2,3)} w_{3} ⋯ w_{n−1} w_{(n−1,n)} w_{n}^{1}  ^{2}  ^{3}  ^{n−1}  ^{n}

The second fundamental solution, g_{n}, has g_{−1} = μ = 1 and g_{0} = λ = 0. Thus, using Model I again, g_{n} = w_{(0,1)} × the vm-partition function of the path

(4)

•  •  •  • w_{2} w_{(2,3)} w_{3} ⋯ w_{n−1} w_{(n−1,n)} w_{n}^{2}  ^{3}  ^{n−1}  ^{n}

Now, decomposing P_{n} at vertex 0, gives:

Theorem 1.2 For n ≥ 1,

P_{n} = λf_{n} + μg_{n}.

Remark 1.3 Let G be a graph with V (G) = {1, …, n} with vertex weights w_{v} for v ∈ V (G), and edge weights w_{e} for any edge e ∈ E(G), and with vm-partition function G.

(i) Suppose we replace any particular vertex weight w_{v′} with ηw_{v′}, and replace the weights w_{e′} on all edges e′ incident to v′ with weight ηw_{e′}, then the vm-partition function of this new graph is ηG. (ii) Extending (i), suppose we replace every vertex weight w_{v} with ηw_{v}, and replace every edge weight w_{e} with weight η^{2}w_{e}, then the vm-partition function of this graph is η^{n}G.

As mentioned above, orthogonal polynomials obey a 3-term recurrence, the next few examples involve well-known orthogonal polynomials.

Example 2 Chebyshev polynomials. U_{−1}(x) = 0 and U_{0}(x) = 1.

Consider the recurrence below for n ≥ 1,

P_{n} = 2xP_{n−1} − P_{n−2}.  (5)

The Chebyshev polynomials of the second kind, U_{n}(x), are the first fundamental solution of this recurrence, i.e., U_{n}(x) = f_{n}(x), (μ = U_{−1} = 0, λ = U_{0} = 1). Thus, comparing (5) with (2), then using (3) with w_{n} = 2x for n ≥ 1 and w_{(n−1,n)} = −1 for n ≥ 2, we see that U_{n}(x) is the vm-partition function of

(6)

•  •  •  •  • 2x −1 2x −1 2x ⋯ 2x −1 2x^{1}  ^{2}  ^{3}  ^{n−1}  ^{n}

The number of k-matchings in P (n) is \binom{n−k}{k}, see Godsil [3, p. 2], so

U_{n}(x) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋}(−1)^{k} \binom{n − k}{k} (2x)^{n−2k}. (See Riordan [4, p. 59].)

The Chebyshev polynomials of the first kind, T_{n}(x), are given by T_{n}(x) = f_{n}(x) + x g_{n}(x), (μ = T_{−1} = x, λ = T_{0} = 1). Thus T_{n}(x) is the vm-partition function of

(7)

•  •  •  •  •  • 1 −x 2x −1 2x −1 2x ⋯ 2x −1 2x^{0}  ^{1}  ^{2}  ^{3}  ^{n−1}  ^{n}

Now decompose T_{n}(x) at vertex 0 which has weight 1. This gives T_{n}(x) = 1 · U_{n}(x) + (−x) · U_{n−1}(x), i.e.,

T_{n}(x) = U_{n}(x) − x U_{n−1}(x),

a well-known formula which involves both types of Chebyshev polynomials. We derive the explicit formula for T_{n}(x) later in Example 7.

Example 3 Associated Legendre polynomials. ρ_{−1}(x) = 1 and ρ_{0}(x) = 1.

Consider the recurrence below for n ≥ 1,

P_{n} = (x + 2)P_{n−1} − P_{n−2}.

With μ = ρ_{−1} = 1 and λ = ρ_{0} = 1 we get the associated Legendre polynomials, ρ_{n}(x) = f_{n}(x) + g_{n}(x), see Riordan [4, p. 66] . Thus, ρ_{n}(x) is the vm-partition function of

(8)

•  •  •  •  •  • 1  −1 x + 2 −1 x + 2 −1 x + 2 ⋯ x + 2 −1 x + 2^{0}  ^{1}  ^{2}  ^{3}  ^{n−1}  ^{n}

U_{n}(\frac{x}{2} + 1) is the vm-partition function of

•  •  •  •  •

x + 2 −1 x + 2 −1 x + 2 ⋯

x + 2 −1 x + 2

1  2  3  n−1  n

Decomposing the vm-partition function of (8), ρ_{n}(x), at vertex 0 yields

ρ_{n}(x) = U_{n} (\frac{x}{2} + 1) − U_{n−1} (\frac{x}{2} + 1) ,

for n ≥ 0, see Riordan [4, p. 85] .

Example 4 Bessel polynomials. θ_{−1}(x) = \frac{1}{x} and θ_{0}(x) = 1.

Consider the recurrence below for n ≥ 1,

P_{n} = (2n − 1)P_{n−1} + x^{2}P_{n−2}.

The Bessel polynomials, θ_{n}(x), are the solutions of this recurrence with μ = θ_{−1} = \frac{1}{x} and λ = θ_{0} = 1, i.e., θ_{n}(x) = f_{n}(x) + \frac{1}{x}g_{n}(x). Thus, θ_{n}(x) is the vm-partition function of

•  •  •  •  •  •

1  x  1 x^2 3 x^2 5

⋯

2n − 3 x^2 2n − 1

0  1  2  3  n−1  n

For the polynomials θ_{n}(x^{−1}) the model is

•  •  •  •  •  •

1 x^{−1} 1 x^{−2} 3 x^{−2} 5

⋯

2n − 3 x^{−2} 2n − 1

0  1  2  3  n−1  n

Let y_{n}(x) = x^{n}θ_{n}(x^{−1}) be the reciprocal Bessel polynomials (see Riordan [4, p. 77] ), then, modifying Remark 1.3(i) for the n vertices {1, …, n} with η = x, we see that y_{n}(x) is the vm-partition function of

•  •  •  •  •  •

1  1  x  1  3x  1  5x

⋯

(2n − 3)x 1 (2n − 1)x

0  1  2  3  n−1  n

By decomposing at vertex n we can derive the recurrence for y_{n} = y_{n}(x),

y_{n} = (2n − 1)xy_{n−1} + y_{n−2},

with y_{−1} = y_{0} = 1.

Example 5 Hermite polynomials. H_{−1}(x) = 0 and H_{0}(x) = 1.

Consider the recurrence below for n ≥ 1,

P_{n} = 2xP_{n−1} − (2n − 2)P_{n−2}.

The Hermite polynomials, H_{n}(x), are the first fundamental solution of this recurrence, i.e., H_{n}(x) = f_{n}(x), (μ = H_{−1} = 0, λ = H_{0} = 1). Thus, using (3), H_{n}(x) is the vm-partition function of

•  •  •  •  •

2x −2 2x −4 2x ⋯

2x −2(n − 1) 2x

1  2  3  n−1  n

Now the coefficient of x^{n−2k} in the vm-partition function of the above weighted path is

2^{n−2k}(−2)^{k} ∑_{N_{k}} ∏_{i∈N_{k}} i  (9)

where N_{k} is a k-subset of {1, …, n − 1} in which no two elements are consecutive. Using (9) and the well-known formula:

H_{n}(x) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋}(−1)^{k} \frac{n!}{k! (n − 2k)!} (2x)^{n−2k},

we have:

Corollary 1.4 Let N_{k} be a k-subset of {1, …, n − 1} in which no two elements are consecutive. Then

∑_{N_{k}} ∏_{i∈N_{k}} i = \frac{n!}{k! (n − 2k)! 2^{k}} .

For example, if n = 7, k = 3, then N_{3} can be any of the four subsets {1, 3, 5}, {1, 3, 6}, {1, 4, 6}, or {2, 4, 6}. We have

1 · 3 · 5 + 1 · 3 · 6 + 1 · 4 · 6 + 2 · 4 · 6 = \frac{7!}{3! 1! 2^{3}} 5.

Remark 1.5 Note the polynomials He_{n} which satisfy the recurrence He_{n} = x He_{n−1} − (n − 1) He_{n−2}. This recurrence arises by dividing all of the above weights by 2, and the relation H_{n}(x) = 2^{n/2} He_{n}(x\sqrt{2}) corresponds to Remark 1.3(ii).

Example 6 q-Lommel polynomials. U_{−1}(x; a, b) = 0 and U_{0}(x; a, b) = 1.

Consider the recurrence below for n ≥ 1,

P_{n} = x (1 + aq^{n−1})P_{n−1} − bq^{n−2}P_{n−2}.

Then the first fundamental solution of this recurrence, f_{n}(x), are the polynomials U_{n}(x; a, b) which appear in Al-Salam and Ismail [1].

For example U_{1}(x; a, b) = x (1+a) and U_{2}(x; a, b) = x^{2} (1+a)(1+aq)−b. Using (3), U_{n}(x; a, b) is the vm-partition function of

•  •  •  •

x(1 + a) −b x(1 + aq) ⋯

x(1 + aq^{n−2})−bq_{n−2} x(1 + aq^{n−1})

1  2  n−1  n

Note that, as stated in Al-Salam and Ismail [1], U_{n}(\frac{2}{x}; −q^{v}, q^{v}) are the q-Lommel polynomials of Ismail [5].

Weighted Cycle C(n)

The weighted path Model I generates P_{n} = λf_{n} + μg_{n} where f_{n} is the first fundamental solution of recurrence (2) and g_{n} is the second fundamental solution. Consider C(n), the cycle with n vertices and n edges, weighted as shown in Fig. 1. Call this Model II.

•

•

• •

•

w_{3}

w_{(2,3)}

w_{2}

λw_{(1,2)}

λw_{1} μw_{(0,1)} w_{n}

w_{(n−1,n)}

w_{n−1}

3

2

1 n

n−1

Figure 1. Weighted C(n)

Let C_{n} be the vm-partition function of C(n), i.e.,

C_{n} = W(C(n)).

Compare Theorem 1.2.

Theorem 1.6 For n ≥ 1,

C_{n} = λf_{n} + μg_{n−1}.

Proof. Let us decompose C_{n} at vertex n. This yields 3 types of vmpartitions of C(n). (a) Those for which vertex n lies in the vertex set. From Model II above, and using (3) for f_{n−1} and Remark 1.3 (i) on vertex 1 with η = λ, we see that these vm-partitions sum to w_{n} · λf_{n−1}. (b) Those which contain edge (n−1, n); these sum to w_{(n−1,n)} ·λf_{n−2}. Thus the vm-partitions in (a) and (b) together sum to λ(w_{n}f_{n−1} + w_{(n−1,n)}f_{n−2}) = λf_{n}. (c) Those which contain edge (n, 1). The sum of these is μg_{n−1}, using (4).

The vm-partitions in (a), (b), and (c) partition the set of vm-partitions of C(n), thus C_{n} = λf_{n} + μg_{n−1}, as required.

Example 7 Here we use Model II to generate T_{n}(x), the Chebyshev polynomials of the first kind, and derive the explicit form for T_{n}(x) as mentioned in Example 2.

Let T_{n} = λf_{n} + μg_{n−1}, where f_{n} and g_{n} are the fundamental solutions of (5). The values T_{0} = 1 and T_{1} = x give λ = μ = \frac{1}{2} i.e., T_{n} = \frac{1}{2}f_{n} + \frac{1}{2}g_{n−1}. Thus T_{n}(x) is the vm-partition function of the weighted cycle in Fig. 2.

•

•

• •

•

2x

−1

2x
−1/2

x −1/2 2x

−1

2x

3

2

1 n

n−1

Figure 2. Chebyshev weights

And, using Remark 1.3(i) at vertex 1 with η = 2, we see that 2 T_{n}(x) is the vm-partition function of the weighted cycle in Fig. 3.

•

•

• •

•

2x

−1

2x

−1

2x −1 2x

−1

2x

3

2

1 n

n−1

Figure 3. Chebyshev weights

See Godsil [3, p. 144].

The number of k-matchings in C(n) is \frac{n}{n−k} \binom{n−k}{k}, see Godsil [3, p. 14], so

2 T_{n}(x) = ∑_{k=0}^{⌊ \frac{n}{2} ⌋}(−1)^{k} \frac{n}{n − k} \binom{n − k}{k} (2x)^{n−2k}.

Now decompose 2 T_{n}(x) at edge (n, 1). A vm-partition of Fig. 3 which does not contain edge (n, 1) is a vm-partition of the path (6), the sum of all such vm-partitions is U_{n}(x). Similarly, the sum of the vm-partitions of Fig. 3 which contain edge (n, 1) is −U_{n−2}(x). Thus we get

2T_{n}(x) = U_{n}(x) − U_{n−2}(x),

the well-known relation between the two types of Chebyshev polynomials, see Riordan [4, p. 59] .

Example 8 Let t and u be arbitrary variables and consider the recurrence

P_{n} = (t + u)P_{n−1} − tuP_{n−2}.  (10)

Now A_{n} = t^{n} + u^{n} is a solution with A_{−1} = t^{−1} + u^{−1} = \frac{t+u}{tu} and A_{0} = 2. Thus A_{n} = 2f_{n} + \frac{t+u}{tu}g_{n} where f_{n} and g_{n} are the fundamental solutions to (10), and we could use Model I to generate A_{n}. However, a better generation is given by Model II: solving A_{n} = λf_{n} + μg_{n−1} at n = 0 yields λ = μ = 1. Thus, for n ≥ 1, A_{n} = f_{n} + g_{n−1} is the vm-partition function of the weighted cycle in Fig. 4.

•

•

• •

•

t + u

−tu

t + u

−tu

t + u −tu t + u

−tu

t + u

3

2

1 n

n−1

Figure 4. General Chebyshev weights Similar to Example 7 we have,

∑_{k=0}^{⌊ \frac{n}{2} ⌋}(−1)^{k} \frac{n}{n − k} \binom{n − k}{k} (t + u)^{n−2k}(tu)^{k} = t^{n} + u^{n},

a ‘very old’ identity, see Riordan [4, p. 58] .

It seems worthwhile to mention that f_{n} is the vm-partition function of

•  •  •  •  •

t + u −tu t + u −tu t + u ⋯

t + u −tu t + u

1  2  3  n−1  n

and it is straightforward to prove by induction that f_{n} = ∑_{i=0}^{n} t^{n−i} u^{i} = \frac{t^{n+1} − u^{n+1}}{t − u}, which is valid for t ≠ u. Now the matchings polynomial of P_{n} is ∑_{k=0}^{⌊ \frac{n}{2} ⌋} \binom{n−k}{k} x^{k}, thus we have,

∑_{k=0}^{⌊ \frac{n}{2} ⌋}(−1)^{k} \binom{n − k}{k} (t + u)^{n−2k}(tu)^{k} = ∑_{i=0}^{n} t^{n−i} u^{i} = \frac{t^{n+1} − u^{n+1}}{t − u} ,

which is valid for t ≠ u.

2 Derivatives of vm-Partition Functions

Vertex Weights containing x

Consider Model I in which each vertex weight has been multiplied by a variable x. The other weight parameters λ, w_{v}, and w_{(u,v)} do not contain x. This gives the weighted path \overline{P} (n) as shown below. Call this Model \overline{I}, the case of multiplicative weights.

•  •  •  •  •  • xλ μw_{(0,1)} xw_{1} w_{(1,2)} xw_{2} w_{(2,3)} xw_{3} ⋯ xw_{n−1} w_{(n−1,n)} xw_{n}^{0}  ^{1}  ^{2}  ^{3}  ^{n−1}  ^{n}

Let \overline{P}_{n}(x) = \overline{P}_{n} = W(\overline{P} (n)) be the vm-partition function of this weighted path, and let \overline{P}_{n}^{(k)} denote its k-th derivative with respect to x for k ≥ 1.

Let V_{k} = \{v_{1}, …, v_{k}\} be a set of k distinct vertices of \overline{P} (n) and let \overline{P} (n) − V_{k} be the graph obtained when these k vertices and their incident edges are removed. The empty graph is the graph with no vertices and no edges, let its vm-partition function be 1.

Before the main result in this section we need:

For each i = 1, …, m let S_{i} be a weighted path. Let S = S_{1} ∪ S_{2} ∪ ⋯ ∪ S_{m} be a disjoint union of m such paths. Let S^{∗} denote the path obtained from S by joining the last vertex of S_{1} to the first vertex of S_{2}, then the last vertex of S_{2} to the first vertex of S_{3}, ... , and so on. Let these m − 1 new edges all have weight 0. Then, it is straightforward to prove,

Lemma 2.1

W(S) = W(S^{∗}).

Now the main result in this section. (See Godsil [3, p. 2] for a similar result with k = 1.)

Theorem 2.2 For any n ≥ 0 and k ≥ 1, the k-th derivative of \overline{P}_{n} is given by

\overline{P}_{n}^{(k)} = k! ∑_{V_{k}} w_{v_{1}} ⋯ w_{v_{k}}W(\overline{P} (n) − V_{k}),  (11)

where the sum is over every V_{k} = \{v_{1}, …, v_{k}\}, a k-set of vertices of \overline{P} (n).

Proof. For k = 1 denote \overline{P}_{n}^{(1)} by \overline{P}′_{n}, we use induction on n. First, for n = 0, we have \overline{P}_{0} = xλ and so \overline{P}′_{0} = λ as the left-hand side of (11); and the right-hand side equals λW(\overline{P} (0) − \{0\}) = λ also, because \overline{P} (0) − \{0\} is the empty graph. For n = 1 we have \overline{P}_{1} = x^{2}λw_{1} + μw_{(0,1)}, and \overline{P}′_{1} = 2xλw_{1} as the left-hand side of (11); the right-hand side equals λW(\overline{P} (1) − \{0\}) + w_{1}W(\overline{P} (1) − \{1\}) = λxw_{1} + w_{1}xλ = 2xλw_{1}, as required.

For n ≥ 2, \overline{P}_{n} = xw_{n}\overline{P}_{n−1} + w_{(n−1,n)}\overline{P}_{n−2}. So, using the product rule for derivatives at the first line, the induction hypothesis at the second line, and a modification of (2) to include the vm-partition function of a union of 2 paths (see Lemma 2.1 with m = 2) at the fourth line, we have

\overline{P}′_{n} = w_{n}\overline{P}_{n−1} + xw_{n}\overline{P}′_{n−1} + w_{(n−1,n)}\overline{P}′_{n−2},
= w_{n}\overline{P}_{n−1} + xw_{n} ∑_{v=0}^{n−1} w_{v}W(\overline{P} (n − 1) − \{v\})

+w_{(n−1,n)} ∑_{v=0}^{n−2} w_{v}W(\overline{P} (n − 2) − \{v\})

= w_{n}\overline{P}_{n−1} + xw_{n}w_{n−1}W(\overline{P} (n − 1) − \{n − 1\})

+ ∑_{v=0}^{n−2} w_{v}\{xw_{n}W(\overline{P} (n − 1) − \{v\}) + w_{(n−1,n)}W(\overline{P} (n − 2) − \{v\})\}

= w_{n}\overline{P}_{n−1} + xw_{n}w_{n−1}\overline{P}_{n−2} + ∑_{v=0}^{n−2} w_{v}W(\overline{P} (n) − \{v\})

= ∑_{v=0}^{n} w_{v}W(\overline{P} (n) − \{v\}),

as required. So (11) is true for k = 1.

Now we induct on k, so assume (11) is true for k, then

\overline{P}_{n}^{(k)} = k! ∑_{V_{k}} w_{v_{1}} ⋯ w_{v_{k}}W(\overline{P} (n) − V_{k}), and
\overline{P}_{n}^{(k+1)} = \overline{P}_{n}^{(k)′} = k! ∑_{V_{k}} w_{v_{1}} ⋯ w_{v_{k}}W(\overline{P} (n) − V_{k})′.

Now the graph \overline{P} (n) − V_{k} is a disjoint union of paths, hence, from Lemma 2.1 and the above,

\overline{P}_{n}^{(k+1)} = k! ∑_{V_{k}} w_{v_{1}} ⋯ w_{v_{k}} ( ∑_{v_{k+1}∉V_{k}} w_{v_{k+1}}W((\overline{P} (n) − V_{k}) − \{v_{k+1}\})) .

Each set V_{k} ∪ {v_{k+1}} will appear k + 1 times, so

\overline{P}_{n}^{(k+1)} = (k + 1)! ∑_{V_{k+1}} w_{v_{1}} ⋯ w_{v_{k+1}}W(\overline{P} (n) − V_{k+1}),

where the sum is over every V_{k+1} = {v_{1}, …, v_{k+1}}, a (k + 1)-set of vertices of \overline{P} (n); thus the induction goes through and (11) is true for all k ≥ 1.

From Taylor’s Expansion we have the following Corollaries, in which the notation x = y means replace x by y, etc:

Corollary 2.3 The polynomials \overline{P}_{n}(x) satisfy the identity

\overline{P}_{n}(x + y) = ∑_{k=0}^{n+1} x^{k} ∑_{V_{k}} w_{v_{1}} ⋯ w_{v_{k}}W(\overline{P} (n) − V_{k}) |_{x=y}

Setting y = 0 gives

Corollary 2.4 The vm-partition function for \overline{P} (n) with multiplicative weights is

\overline{P}_{n}(x) = ∑_{k=0}^{n+1} x^{k} ∑_{V_{k}} w_{v_{1}} ⋯ w_{v_{k}}W(\overline{P} (n) − V_{k}) |_{x=0}

Thus, we have a combinatorial interpretation of the coefficients of x^{k} in the case of multiplicative weights.

A special case of Corollary 2.4 is given by

P_{n} = \overline{P}_{n}(1) = ∑_{k=0}^{n+1} ∑_{V_{k}} w_{v_{1}} ⋯ w_{v_{k}}W(\overline{P} (n) − V_{k}) |_{x=0}

which corresponds to arranging the terms of P_{n} so that we sum over the vm-partitions V |M where |V | = k for k = 0, … n + 1.

We now give an alternative derivation of the above formula in Corollary 2.4.

A perfect matching of a graph with an even number of vertices is a set of edges, no two of which are incident and which cover every vertex exactly once. Clearly a path with an even number of vertices has a unique perfect matching obtained by choosing its left-most edge and then every second edge.

We say that the graph \overline{P} (n) − V_{k} for any k = 0, …, n + 1 is composed of k + 1 segments. Each segment is a path; we allow for an empty path if two of the vertices in V_{k} are adjacent in \overline{P} (n), or if vertex 0 ∈ V_{k} then the first segment in \overline{P} (n) − V_{k} is the empty path, similarly if vertex n ∈ V_{k} then the last segment in \overline{P} (n) − V_{k} is the empty path.

Now clearly W(\overline{P} (n) − V_{k})|_{x=0} = 0 unless each of the k + 1 segments in \overline{P} (n) − V_{k} is either the empty path or a path with an even number of vertices, since in a path with an odd number of vertices every vm-partition must contain at least one isolated vertex and hence every vm-partition has weight 0. In this former case we have W(\overline{P} (n) − V_{k})|_{x=0} = ∏_{e∈M} w_{e}, where M is the following set of edges: the first edge in the first non-empty segment of \overline{P} (n) − V_{k} followed by every second edge in this segment, then the first edge in the second non-empty segment of \overline{P} (n)−V_{k} followed by every second edge in this segment,..., and so on. That is, M is the unique perfect matching of \overline{P} (n) − V_{k}.

Now, from (1), modified for the case of multiplicative weights, a typical term in \overline{P}_{n}(x) is ∏_{v∈V} x^{|V |}w_{v} · ∏_{e∈M} w_{e}, where we now see that M is the unique perfect matching of \overline{P} (n) − V. Hence, setting |V | = k we have:

\overline{P}_{n}(x) = ∑_{k=0}^{n+1} ∑_{V_{k}} ∏_{v∈V_{k}} x^{k}w_{v} · ∏_{e∈M} w_{e}

= ∑_{k=0}^{n+1} x^{k} ∑_{V_{k}} w_{v_{1}} ⋯ w_{v_{k}}W(\overline{P} (n) − V_{k}) |_{x=0}

as above.

The polynomials U_{n}(x) from Example 2, H_{n}(x) from Example 5, and U_{n}(x; a, b) from Example 6 can be generated by Model \overline{I}.

Example 9 H_{4}(x) is the vm-partition function of

•  •  •  • 2x −2 2x −4 2x −6 2x^{1}  ^{2}  ^{3}  ^{4}

So H_{4}(x) = 16x^{4} − 48x^{2} + 12 and its second derivative H_{4}^{(2)}(x) = 192x^{2} − 96.

{1, 2} 2x −6 2x

• • 3 4

2 · 2 · (4x^{2} − 6)

{1, 3}  2x  2x

• • 2 4

2 · 2 · 4x^{2}

{1, 4} 2x −4 2x

• • 2 3

2 · 2 · (4x^{2} − 4)

{2, 3}  2x  2x

• • 1 4

2 · 2 · 4x^{2}

{2, 4}  2x  2x

• • 1 3

2 · 2 · 4x^{2}

{3, 4} 2x −2 2x

• • 1 2

2 · 2 · (4x^{2} − 2)

96x^{2} − 48

V_{2} = \{v_{1}, v_{2}\}  \overline{P} (4) − V_{2}  w_{v_{1}}w_{v_{2}}W(\overline{P} (4) − V_{2})

But k = 2 so 2! · (96x^{2} − 48) = 192x^{2} − 96 = H_{4}^{(2)}(x).

We have a similar result for Model I with vertex weights x−λ on vertex 0 and x−w_{v} on vertex v ∈ {1, 2, …, n}, where λ, w_{v}, and w_{(u,v)} do not contain x. Call this weighted path P̂(n) and let P̂_{n} be its vm-partition function; it is shown below. We call this Model Î, the case of additive weights.

•  •  •  •

x − λ μw_{(0,1)} x − w_1 ⋯

x − w_{n−1} w_{(n−1,n)} x − w_n

0  1  n−1  n

Example 10 Poisson-Charlier polynomials. P_{−1}(x) = 0 and P_{0}(x) = 1. Consider the recurrence below for n ≥ 1,

P_{n} = (x − t − n + 1)P_{n−1} + t(n − 1)P_{n−2}.

Then the first fundamental solution of this recurrence are the Poisson-Charlier polynomials P_{n}(x, t), which can be generated by Model Î, shown below.

•  •  •  •

(x − t) t (x − t − 1)

⋯

(x − t − (n − 2)) (n − 1)t (x − t − (n − 1))

1  2  n−1  n

We have the following Theorem, the proof of which is similar to that of Theorem 2.2.

Theorem 2.5 For any n ≥ 0 and k ≥ 1, the k-th derivative of P̂_{n} is given by

P̂_{n}^{(k)} = k! ∑_{V_{k}} W(P̂(n) − V_{k}),

where the sum is over every V_{k}, a k-set of vertices of P̂(n).

and as for Theorem 2.2 we have the Corollaries:

Corollary 2.6 The polynomials P̂_{n}(x) satisfy the identity

P̂_{n}(x + y) = ∑_{k=0}^{n+1} x^{k} ∑_{V_{k}} W(P̂(n) − V_{k}) |_{x=y}

and

Corollary 2.7 The vm-partition functionfor P̂(n) with additive weights is

P̂_{n}(x) = ∑_{k=0}^{n+1} x^{k} ∑_{V_{k}} W(P̂(n) − V_{k}) |_{x=0}

As before, this gives a combinatorial interpretation of the coefficients of x^{k} in the case of additive weights.

We observe that:

W(P̂(n) − V_{k}) |_{x=0}= W(\overline{P} (n) − V_{k}) |_{x=−1}

Finally, see Feinsilver, McSorley, and Schott [2] for an application of Theorem 2.5 to Lommel polynomials.

Segment Polynomials

Consider Model I. For any 0 ≤ ℓ ≤ m ≤ n let P (ℓ, m) denote the weighted subpath of P (n) starting at vertex ℓ and ending at vertex m,

•  •  •  •  •

w_ℓ w_{(ℓ,ℓ+1)} w_{ℓ+1} w_{(ℓ+1,ℓ+2)} w_{ℓ+2} ⋯

w_{m−1} w_{(m−1,m)} w_m

ℓ  ℓ+1  ℓ+2  m−1  m

Now define

P_{ℓ,m} = W(P (ℓ, m))

to be the vm-partition function of P (ℓ, m).

Example 11 Starting with P (3) we have the weighted subpath P (1, 3):

•  •  • w_{1} w_{(1,2)} w_{2} w_{(2,3)} w_{3}^{1}  ^{2}  ^{3}

which has 3 vm-partitions:

vm-partition

• • •

1 2 3

M_{∅}

•

3

• •

1 2

•

1

• •

2 3

weight

w_{1}w_{2}w_{3}

w_{3}w_{(1,2)}

w_{1}w_{(2,3)}

Thus P_{1,3} = w_{1}w_{2}w_{3} + w_{3}w_{(1,2)} + w_{1}w_{(2,3)}.

Note that P_{0,n} = P_{n} for n ≥ 0. We also define P_{0,−1} = P_{−1} = μ. Then, with the starting conditions P_{ℓ,ℓ−2} = 0 and P_{ℓ,ℓ−1} = 1, we have for m ≥ 1,

P_{ℓ,m} = w_{m}P_{ℓ,m−1} + w_{(m−1,m)}P_{ℓ,m−2}.

Example 12 With natural notation we see, from the weighted path (6) in Example 2, that U_{ℓ,m}(x) = U_{m−ℓ+1}(x), for ℓ ≥ 1, these are Chebyshev segment polynomials of the second kind. Similarly, from the weighted path (7) we have T_{ℓ,m}(x) = U_{m−ℓ+1}(x), for ℓ ≥ 1, the Chebyshev segment polynomials of the first kind. We also have ρ_{ℓ,m}(x) = ρ_{m−ℓ+1}(x + 2), for ℓ ≥ 1, the associated Legendre segment polynomials.

For orthogonal polynomials satisfying the three-term recurrence

x p_{n}(x) = a_{n+1} p_{n+1}(x) + b_{n} p_{n}(x) + a_{n} p_{n−1}(x)

with p_{−1}(x) = 0, p_{0}(x) = 1, i.e., the first fundamental solution to the recurrence, the ℓ^{th} associated polynomials, p_{(n,ℓ)}(x) are the first fundamental solution to the recurrence

x p_{(n,ℓ)}(x) = a_{n+ℓ+1} p_{(n+1,ℓ)}(x) + b_{n+ℓ} p_{(n,ℓ)}(x) + a_{n+ℓ} p_{(n−1,ℓ)}(x)

(see Van Assche [6], with our notation a slight variant). In other words, the subscripts on the coefficients are shifted up ℓ units. This corresponds exactly to moving up ℓ vertices along the path, namely our segment polynomials. Thus we have a (new) combinatorial interpretation of the associated polynomials.

Equation 2.10 of Theorem 1 of [6] gives the relation

p′_{n}(x) = ∑_{j=1}^{n} \frac{1}{a_{j}} p_{j−1}(x) p_{(n−j,j)}(x).  (12)

This is the case k = 1 of our Theorem 2.2 which expands the first derivative of \overline{P}_{n}(x) in terms of segment polynomials. Explicitly, we have

\overline{P}′_{n} = ∑_{v=0}^{n} w_{v}P_{0,v−1}P_{v+1,n} = ∑_{v=0}^{n} w_{v}P_{v−1}P_{v+1,n}.  (13)

Furthermore, our model gives formulas for 2^{nd} and higher derivatives of \overline{P}_{n} in terms of more complicated combinations of segment polynomials.

Example 13 Note that equation (12) suggests the form of a convolution. An example that illustrates this is given by the Gegenbauer polynomials, C_{n}^{λ}(x), with generating function

G(x, v; λ) = (1 − 2xv + v^{2})^{−λ} = ∑_{n=0}^{∞} v^{n}C_{n}^{λ}(x).

Differentiating both sides with respect to x gives

2vλ G(x, v; λ + 1) = ∑_{n=0}^{∞} v^{n}(C_{n}^{λ}(x))′.

Or, for n ≥ 1,

(C_{n}^{λ}(x))′ = 2λ C_{n−1}^{λ+1}(x).

Observe that the relation G(x, v; λ + μ) = G(x, v; λ)G(x, v; μ) may be read as the statement that the sequence {C_{n}^{λ+μ}}_{n≥0} is the convolution of the sequences {C_{n}^{λ}}_{n≥0} and {C_{n}^{μ}}_{n≥0}. Now, the case μ = 1 gives C_{n}^{λ} = U_{n}, Chebyshev polynomials of the second kind. Thus,

(C_{n}^{λ}(x))′ = 2λ C_{n−1}^{λ+1}(x) = 2λ ∑_{j=1}^{n} C_{n−j}^{λ}(x) U_{j−1}(x)

holds in general. In particular, taking λ = 1, recalling equation (12) to the effect that the U_{n} are their own associated/segment polynomials, we have an exact correspondence with equations (12) and (13) for Chebyshev polynomials of the second kind.

Edge Weights containing x

Finally we consider derivatives with respect to variables on the edges of Model I.

Consider Model I in which each weight has been multiplied by the variable x. As before, other weight parameters do not contain x. Let \overline{Q}(n) denote this weighted path and let \overline{Q}_{n} be its vm-partition function, see below.

•  •  •  •  •  • λ xμw_{(0,1)} w_{1} xw_{(1,2)} w_{2} xw_{(2,3)} w_{3} ⋯ w_{n−1} xw_{(n−1,n)} w_{n}^{0}  ^{1}  ^{2}  ^{3}  ^{n−1}  ^{n}

Let M_{k} = \{e_{1}, …, e_{k}\} be a k-matching of \overline{Q}(n), then we have the following theorem, the proof of which is similar to the above proof of Theorem 2.2.

Theorem 2.8 For any n ≥ 0 and k ≥ 1, the k-th derivative of \overline{Q}_{n} is given by

\overline{Q}_{n}^{(k)} = k! ∑_{M_{k}} w_{e_{1}} ⋯ w_{e_{k}}W(\overline{Q}(n) − M_{k}),

the sum is over every M_{k} = \{e_{1}, …, e_{k}\}, a k-matching of \overline{Q}(n).

And Taylor’s Expansion gives results analogous to Corollaries 2.3 and 2.4. Finally, proceeding as before, call the weighted path with edge weights

as shown below Q̂(n), and call its vm-partition function Q̂_{n}.

•  •  •  •  • λ x − μw_{(0,1)} w^1 x − w_{(1,2)} w^2 ⋯

w_{n−1} x − w_{(n−1,n)} w_n

0  1  2  n−1  n

Theorem 2.9 For any n ≥ 0 and k ≥ 1, the k-th derivative of Q̂_{n} is given by

Q̂_{n}^{(k)} = k! ∑_{M_{k}} W(Q̂(n) − M_{k}),

where the sum is over every M_{k}, a k-matching of Q̂(n).

Similarly there are results analogous to Corollaries 2.6 and 2.7.

References

[1] W. A. Al-Salam and M. E. Ismail, Orthogonal polynomials associated with the Rogers-Ramanujan continued fraction, Pacific Jour. Math, 104, No. 2, (1983), 269–283.

[2] P. Feinsilver, J.P. McSorley, R. Schott, Combinatorial Interpretation and Operator Calculus of Lommel Polynomials, Jour. Comb. Theory, Series A, 75, No. 1, (1996), 163–171.

[3] C.D. Godsil, Algebraic Combinatorics, New York, Chapman & Hall, 1993.

[4] J. Riordan, Combinatorial Identities, New York, John Wiley & Sons, Inc, 1968.

[5] M. E. Ismail, The zeros of basic Bessel functions, the functions J_{v+ax}(x) and associated orthogonal polynomials, J. Math. Anal. Appl., 86, (1982), 1–19.

[6] W. Van Assche, Orthogonal polynomials, associated polynomials and functions of the second kind, J. Comput. Appl. Math. 37, (1991), 237– 249.

[7] G. Viennot, Une théorie combinatoire des polynômes orthogonaux généraux, Notes de cours. Université du Quebec à Montréal, 1984.

[8] G. Viennot, A combinatorial theory for general orthogonal polynomials with extensions and applications, Proceedings of the Laguerre Symposium, Bar-le-Duc, Polynômes Orthogonaux et Applications, Springer Lecture Notes in Mathematics, Springer, Berlin, 1985, 1171, 139–157.