# Them-Path Cover Polynomial of a Graph and a Model for General Coefficient Linear Recurrences

Authors: John P. McSorley; Philip Feinsilver
Journal: International Journal of Combinatorics
 (2014)

---

## Abstract

Anm-path cover Γ
=
{
P
ℓ
1
,
P
ℓ
2
,
…
,
P
ℓ
r
} of a simple graph G is a set of vertex disjoint paths of G, each with ℓ
k
≤
m vertices, that span G. With every P
ℓ we associate a weight, ω
(
P
ℓ
), and define the weight of Γ to be ω
(
Γ
)
=
∏
k
=
1
r
‍
ω
(
P
ℓ
k
). The m-path cover polynomial of G is then defined as ℙ
m
(
G
)
=
∑
Γ
‍
ω
(
Γ
)
, where the sum is taken over all m-path covers Γ of G. This polynomial is a specialization of the path-cover polynomial of Farrell. We consider the m-path cover polynomial of a weighted path P
(
m
-
1
,
n
) and find the (
m
+
1
)-term recurrence that it satisfies. The matrix form of this recurrence yields a formula equating the trace of the recurrence matrix with the m-path cover polynomial of a suitably weighted cycle C
(
n
). A directed graph, T
(
m
), the edge-weighted m-trellis, is introduced and so a third way to generate the solutions to the above (
m
+
1
)-term recurrence is presented. We also give a model for general-term linear recurrences and time-dependent Markov chains.


---

## Body

## 1. Introduction,m-Path Cover Polynomial, and Notation

LetG be a graph with no loops or multiple edges, with vertex set V
(
G
).First we review some basic concepts to establish notation.Apath
P
ℓ in G is a sequence of distinct vertices P
ℓ
=
[
v
1
,
v
2
,
…
,
v
ℓ
] where each pair (
v
i
,
v
i
+
1
) for 1
≤
i
≤
ℓ
-
1 is an edge. The length of a path is the number of vertices in it. Thus a path of length 1 is a vertex and a path of length 2 is an edge, and P
ℓ has length ℓ. Path P
ℓ
begins at vertex v
1, its first vertex, and ends at vertex v
ℓ, its last vertex. The path [
v
1
,
v
2
,
…
,
v
ℓ
] and its reverse [
v
ℓ
,
v
ℓ
-
1
,
…
,
v
1
] are considered to be the same path. The set of vertices in P
ℓ is V
(
P
ℓ
)
=
{
v
1
,
v
2
,
…
,
v
ℓ
}. Two paths P
ℓ and P
ℓ
′ in G are disjoint if V
(
P
ℓ
)
∩
V
(
P
ℓ
′
)
=
∅. The empty path has 0 vertices. Finally, recall that a subgraph of G
spans
G if it has the same vertex set as G.Now we introduce the central concept of this paper.Anm
-path
P
ℓ has ℓ
≤
m; that is, it is a path of length at most m for some fixed m with 1
≤
m
≤
|
V
(
G
)
|.Anm
-path cover
Γ
=
{
P
ℓ
1
,
P
ℓ
2
,
…
,
P
ℓ
r
} of G is a set of pairwise disjoint m-paths of G that span G. Thus each ℓ
k satisfies 1
≤
ℓ
k
≤
m, and every vertex of G lies in exactly one m-path; that is, V
(
G
)
=
∪
k
=
1
r
V
(
P
ℓ
k
) is a partition of V
(
G
).With everym-path P
ℓ we associate a weight, ω
(
P
ℓ
), and then the weight of Γ is ω
(
Γ
)
=
∏
k
=
1
r
‍
ω
(
P
ℓ
k
).Definition 1.
Them
-path cover polynomial of G, ℙ
m
(
G
), is the sum of the weights of all m-path covers of G; that is,
(1)
ℙ
m
(
G
)
=
∑
Γ
‍
ω
(
Γ
)
,
where Γ is an m-path cover of G.The path-cover polynomial (or path polynomial) of a graphG is a specialization of the F-cover polynomial of Farrell [1] where F is restricted to be a path; see Farrell [2]. Thus our m-path cover polynomial ℙ
m
(
G
) is a further specialization to paths of length ℓ
≤
m. See also Chow [3] and D’Antona and Munarini [4].It seems that this research is the first direct consideration of them-path cover polynomial of a graph. See McSorley et al. [5] for specialization to the case m
=
2, where all classical orthogonal polynomials are generated as 2-path cover polynomials of suitably weighted paths. For related work see the theory of weighted linear species developed in Joyal [6] and Bergeron et al. [7]. In particular, Munarini [8] uses the m-filtered linear partitions of a linearly ordered set to achieve some similar results; see especially our Sections 7 and 8.In Section2 we introduce a weighted path P
(
m
-
1
,
n
) and find the (
m
+
1
)-term recurrence that its m-path polynomial satisfies. In Section 3 the matrix form of this recurrence is presented and yields a trace formula that, in Section 4, gives the m-path cover polynomial of a suitably weighted cycle C
(
n
). Section 5 interprets our results in terms of a model for time-dependent Markov chains. In Section 6 a directed graph, T
(
m
), the edge-weighted m-trellis, is introduced and so a third way to generate the solutions to the above recurrence and trace is found. In Section 7 we model general constant coefficient linear recurrences, and we derive various relevant formulas with both algebraic and combinatorial proofs. Finally, in Section 8, we obtain a relevant new integer sequence and relate this sequence to known sequences in the literature.Notation. We write ℙ
m
[
v
1
,
v
2
,
…
,
v
ℓ
], instead of ℙ
m
(
[
v
1
,
v
2
,
…
,
v
ℓ
]
), for the m-cover polynomial of the path [
v
1
,
v
2
,
…
,
v
ℓ
]; similarly we write ω
[
v
1
,
v
2
,
…
,
v
ℓ
] instead of ω
(
[
v
1
,
v
2
,
…
,
v
ℓ
]
), and so forth.Vertices inP
(
m
-
1
,
n
) (Section 2) and in subpaths of P
(
s
,
n
) will be labelled u
i; vertices in C
(
n
) (Section 4) will be labelled v
i; and vertices in T
(
m
) (Section 6) will be labelled w
i.For1
≤
ℓ
≤
m we use indeterminate x
ℓ
,
i as the weight of a path of length ℓ in G. Throughout the paper m
≥
1 is fixed. In all the examples we set m
=
3, and many examples have n
=
4.


## 2. Weighted PathP
(
m
-
1
,
n
)

Form
≥
1 and n
≥
0 the path P
(
m
-
1
,
n
) has m
-
1
+
n vertices {
u
1
,
u
2
,
…
,
u
m
-
1
+
n
}. The first m
-
1 vertices are weighted with weight 1 and the remaining n vertices are weighted, one by one, with the indeterminates from the set {
x
1,1
,
x
1,2
,
…
,
x
1
,
n
}. Thus all vertices, that is, all paths of length ℓ
=
1, in P
(
m
-
1
,
n
) are weighted. For 2
≤
ℓ
≤
m a path of length ℓ in P
(
m
-
1
,
n
) is weighted with 0 if its last vertex has weight 1 and with x
ℓ
,
i if its last vertex has weight x
1
,
i. The path P
(
0,0
) is the empty path with no vertices.Definition 2.
Forn
≥
1 let f
m
,
n be the m-path cover polynomial of the weighted P
(
m
-
1
,
n
).Starting conditions aref
m
,
n
=
1 for -
(
m
-
1
)
≤
n
≤
0.As mentioned in Section1, throughout this paper the path [
u
a
,
u
a
+
1
,
…
,
u
b
] is a subpath of the weighted P
(
m
-
1
,
n
).We now derive our main(
m
+
1
)-term recurrence.Theorem 3.
For a fixedm
≥
1 and any n
≥
-
(
m
-
1
),
(2)
f
m
,
n
=
x
1
,
n
f
m
,
n
-
1
+
x
2
,
n
f
m
,
n
-
2
+
⋯
+
x
m
,
n
f
m
,
n
-
m
=
∑
ℓ
=
1
m
‍
x
ℓ
,
n
f
m
,
n
-
ℓ
.Proof.
The last vertexu
m
-
1
+
n of P
(
m
-
1
,
n
) lies in every m-path cover of P
(
m
-
1
,
n
). Suppose, in such an m-path cover, it is present as the last vertex in an m-path of length ℓ. Then this m-path has weight x
ℓ
,
n and begins at u
m
+
n
-
ℓ. The sum of the weights of all such m-path covers is therefore
(3)
x
ℓ
,
n
ℙ
m
[
u
1
,
u
2
,
…
,
u
m
-
1
+
n
-
ℓ
]
=
x
ℓ
,
n
f
m
,
n
-
ℓ
,
where [
u
1
,
u
2
,
…
,
u
m
-
1
+
n
-
ℓ
] is a subpath of P
(
m
-
1
,
n
). Now summing over ℓ gives the result. The initial conditions f
m
,
n
=
1 for -
(
m
-
1
)
≤
n
≤
0 ensure that this equation holds when ℓ
≥
n.Example 4.
Form
=
3 the weighted path P
(
2,3
) is
(4)The weights of paths of lengthsℓ
=
1 and 2 (vertices and edges) are shown above the path. Vertex labels and weights of paths of length ℓ
=
3 are shown below the path. Let
(5)
ℓ
=
1
:
ω
[
u
1
]
=
ω
[
u
2
]
=
1
,
ω
[
u
3
]
=
x
1,1
,
ω
[
u
4
]
=
x
1,2
,
ω
[
u
5
]
=
x
1,3
,
ℓ
=
2
:
ω
[
u
1
,
u
2
]
=
0
,
ω
[
u
2
,
u
3
]
=
x
2,1
,
ω
[
u
3
,
u
4
]
=
x
2,2
,
ω
[
u
4
,
u
5
]
=
x
2,3
,
ℓ
=
3
:
ω
[
u
1
,
u
2
,
u
3
]
=
x
3,1
,
ω
[
u
2
,
u
3
,
u
4
]
=
x
3,2
,
ω
[
u
3
,
u
4
,
u
5
]
=
x
3,3
.All 3-path covers ofP
(
2,3
) and their weights are shown below:
(6)
So f
3,3
=
x
1,1
x
1,2
x
1,3
+
x
1,2
x
1,3
x
2,1
+
x
1,3
x
2,2
+
x
1,1
x
2,3
+
x
2,1
x
2,3
+
x
1,2
x
1,3
x
3,1
+
x
1,3
x
3,2
+
x
2,3
x
3,1
+
x
3,3.Example 5.
Theorem3 with m
=
3 gives the 4-term recurrence for a fixed n
≥
1,
(7)
f
3
,
n
=
x
1
,
n
f
3
,
n
-
1
+
x
2
,
n
f
3
,
n
-
2
+
x
3
,
n
f
3
,
n
-
3
.
Then the starting conditions f
3
,
-
2
=
f
3
,
-
1
=
f
3,0
=
1 give
(8)
f
3,1
=
x
1,1
+
x
2,1
+
x
3,1
,
f
3,2
=
x
1,1
x
1,2
+
x
1,2
x
2,1
+
x
1,2
x
3,1
+
x
2,2
+
x
3,2
,
f
3,3
=
x
1,1
x
1,2
x
1,3
+
x
1,2
x
1,3
x
2,1
+
x
1,3
x
2,2
+
x
1,1
x
2,3
+
x
2,1
x
2,3
+
x
1,2
x
1,3
x
3,1
+
x
1,3
x
3,2
+
x
2,3
x
3,1
+
x
3,3
,
f
3,4
=
x
1,1
x
1,2
x
1,3
x
1,4
+
x
1,2
x
1,3
x
1,4
x
2,1
+
x
1,2
x
1,3
x
1,4
x
3,1
+
x
1,1
x
1,2
x
2,4
+
x
1,1
x
1,4
x
2,3
+
x
1,2
x
2,1
x
2,4
+
x
1,2
x
2,4
x
3,1
+
x
1,3
x
1,4
x
2,2
+
x
1,3
x
1,4
x
3,2
+
x
1,4
x
2,1
x
2,3
+
x
1,4
x
2,3
x
3,1
+
x
1,1
x
3,4
+
x
1,4
x
3,3
+
x
2,1
x
3,4
+
x
2,2
x
2,4
+
x
2,4
x
3,2
+
x
3,1
x
3,4
⋮
We check f
3,3 from Example 4.Definition 6.
For0
≤
r
≤
m
-
1 we define P
(
r
,
n
) as above for P
(
m
-
1
,
n
), except that we have r vertices instead of m
-
1 vertices of weight 1 at the beginning of the path. Thus P
(
r
,
n
) has r
+
n vertices and is formed from P
(
m
-
1
,
n
) by truncating from the right. All m-paths in P
(
r
,
n
) are weighted as in P
(
m
-
1
,
n
). We let 𝒫
m
(
r
,
n
) be the m-path cover polynomial of the weighted P
(
r
,
n
). We note that f
m
,
n
=
𝒫
m
(
m
-
1
,
n
).Example 7.
Form
=
3 and n
=
4,
(9)
𝒫
3
(
0,4
)
=
x
1,1
x
1,2
x
1,3
x
1,4
+
x
1,1
x
1,2
x
2,4
+
x
1,1
x
1,4
x
2,3
+
x
1,3
x
1,4
x
2,2
+
x
1,1
x
3,4
+
x
1,4
x
3,3
+
x
2,2
x
2,4
,
𝒫
3
(
1,4
)
=
x
1,1
x
1,2
x
1,3
x
1,4
+
x
1,2
x
1,3
x
1,4
x
2,1
+
x
1,3
x
1,4
x
2,2
+
x
1,1
x
1,4
x
2,3
+
x
1,1
x
1,2
x
2,4
+
x
1,4
x
2,1
x
2,3
+
x
1,2
x
2,1
x
2,4
+
x
1,3
x
1,4
x
3,2
+
x
1,1
x
3,4
+
x
1,4
x
3,3
+
x
2,1
x
3,4
+
x
2,2
x
2,4
+
x
2,4
x
3,2
,
𝒫
3
(
2,4
)
=
f
3,4
;
see Example 5.
For a fixedr with 0
≤
r
≤
m
-
1 we define the starting conditions,
(10)
𝒫
m
(
r
,
n
)
=
{
0
,
if
-
(
m
-
1
)
≤
n
≤
-
r
-
1
,
1
,
if
-
r
≤
n
≤
0
.
We then have the following recurrence; the proof is similar to the proof of Theorem3, and setting r
=
m
-
1 recovers Theorem 3.Theorem 8.
For a fixedr with 0
≤
r
≤
m
-
1 and any n
≥
1,
(11)
𝒫
m
(
r
,
n
)
=
∑
ℓ
=
1
m
‍
x
ℓ
,
n
𝒫
m
(
r
,
n
-
ℓ
)
.We now work with the fundamental solutions to recurrence (2).For1
≤
j
≤
m let f
m
,
n
(
j
) denote the jth fundamental solution to (2). Thus the f
m
,
n
(
j
) obey the recurrence
(12)
f
m
,
n
(
j
)
=
∑
ℓ
=
1
m
‍
x
ℓ
,
n
f
m
,
n
-
ℓ
(
j
)
,
with starting conditions
(13)
f
m
,
-
(
m
-
1
)
+
k
(
j
)
=
{
1
,
if
k
=
m
-
j
,
0
,
if
k
≠
m
-
j
,
where 0
≤
k
≤
m
-
1.We have(14)
f
m
,
n
=
∑
j
=
1
m
‍
f
m
,
n
(
j
)
.Our next result expressesf
m
,
n
(
j
) as the difference of two m-path cover polynomials. Consistent with (10) we set 𝒫
m
(
-
1
,
n
)
=
0 for every n
≥
-
(
m
-
1
).Lemma 9.
Forn
≥
1 and 1
≤
j
≤
m,
(15)
f
m
,
n
(
j
)
=
𝒫
m
(
j
-
1
,
n
)
-
𝒫
m
(
j
-
2
,
n
)
.Proof.
By induction onn, first consider n
=
1. Now f
m
,
1
-
ℓ
(
j
)
=
1 when ℓ
=
j and f
m
,
1
-
ℓ
(
j
)
=
0 otherwise. Each f
m
,
n
(
j
) satisfies (12), so f
m
,
1
(
j
)
=
∑
ℓ
=
1
m
‍
x
ℓ
,
1
f
m
,
1
-
ℓ
(
j
)
=
x
j
,
1. Now consider the path P
(
j
-
1,1
) shown below:
(16)
The first vertex u
1 lies in every m-path cover of P
(
j
-
1,1
) so, similar to the proof of Theorem 3, we have
(17)
𝒫
m
(
j
-
1,1
)
=
ω
[
u
1
]
𝒫
m
(
j
-
2,1
)
+
ω
[
u
1
,
u
2
]
𝒫
m
(
j
-
3,1
)
+
⋯
+
ω
[
u
1
,
u
2
,
…
,
u
j
]
=
1
·
𝒫
m
(
j
-
2,1
)
+
0
·
𝒫
m
(
j
-
3,1
)
+
⋯
+
x
j
,
1
.
Thus, from above, f
m
,
1
(
j
)
=
x
j
,
1
=
𝒫
m
(
j
-
1,1
)
-
𝒫
m
(
j
-
2,1
); that is, (15) is true for n
=
1.
Now we have(18)
f
m
,
n
+
1
(
j
)
=
∑
ℓ
=
1
m
‍
x
ℓ
,
n
+
1
f
m
,
n
+
1
-
ℓ
(
j
)
=
∑
ℓ
=
1
m
‍
x
ℓ
,
n
+
1
{
𝒫
m
(
j
-
1
,
n
+
1
-
ℓ
)
-
𝒫
m
(
j
-
2
,
n
+
1
-
ℓ
)
}
=
∑
ℓ
=
1
m
‍
x
ℓ
,
n
+
1
𝒫
m
(
j
-
1
,
n
+
1
-
ℓ
)
-
∑
ℓ
=
1
m
‍
x
ℓ
,
n
+
1
𝒫
m
(
j
-
2
,
n
+
1
-
ℓ
)
=
𝒫
m
(
j
-
1
,
n
+
1
)
-
𝒫
m
(
j
-
2
,
n
+
1
)
,
using (12) again at the first line, the induction hypothesis at the second line and Theorem 8 at the last line. Hence the induction goes through and (15) is true for all n
≥
1.Example 10.
Using (12) and the starting conditions following (12) for m
=
3 and n
=
4 the 3 fundamental solutions to recurrence (2) are
(19)
f
3,4
(
1
)
=
x
1,1
x
1,2
x
1,3
x
1,4
+
x
1,1
x
1,2
x
2,4
+
x
1,1
x
1,4
x
2,3
+
x
1,3
x
1,4
x
2,2
+
x
1,1
x
3,4
+
x
1,4
x
3,3
+
x
2,2
x
2,4
,
f
3,4
(
2
)
=
x
1,2
x
1,3
x
1,4
x
2,1
+
x
1,3
x
1,4
x
3,2
+
x
1,4
x
2,1
x
2,3
+
x
1,2
x
2,1
x
2,4
+
x
2,4
x
3,2
+
x
2,1
x
3,4
,
f
3,4
(
3
)
=
x
1,2
x
1,3
x
1,4
x
3,1
+
x
1,4
x
2,3
x
3,1
+
x
1,2
x
2,4
x
3,1
+
x
3,1
x
3,4
.We check (14) using Example 5,
(20)
f
3,4
=
f
3,4
(
1
)
+
f
3,4
(
2
)
+
f
3,4
(
3
)
.
We also check Lemma 9 using 𝒫
3
(
-
1,4
)
=
0 and Example 7,
(21)
f
3,4
(
1
)
=
𝒫
3
(
0,4
)
-
𝒫
3
(
-
1,4
)
=
𝒫
3
(
0,4
)
,
f
3,4
(
2
)
=
𝒫
3
(
1,4
)
-
𝒫
3
(
0,4
)
,
f
3,4
(
3
)
=
𝒫
3
(
2,4
)
-
𝒫
3
(
1,4
)
.By iteration of such formulas, we have Corollary11, where (ii) is a specialization of (i) with r
=
0.Corollary 11.
(i) For1
≤
j
≤
m,
(22)
𝒫
m
(
r
,
n
)
=
∑
j
=
1
r
+
1
‍
f
m
,
n
(
j
)
,
(ii) the first fundamental solution to recurrence (2) is given by
(23)
f
m
,
n
(
1
)
=
𝒫
m
(
0
,
n
)
.Corollary12 is a useful technical result.Corollary 12.
Forn
≥
1 and 1
≤
j
≤
m,
(24)
f
m
,
n
+
1
-
j
(
j
)
=
∑
ℓ
=
j
m
‍
x
ℓ
,
ℓ
+
1
-
j
ℙ
m
[
u
m
+
ℓ
+
1
-
j
,
…
,
u
m
+
n
-
j
]
.Proof.
Forj
=
1 from Corollary 11(ii) we have f
m
,
n
(
1
)
=
𝒫
m
(
0
,
n
). Now in the weighted path P
(
0
,
n
) let vertex u
1 be covered by a path Q
ℓ of length ℓ where 1
≤
ℓ
≤
m. Then Q
ℓ begins at vertex u
1 and ends at vertex u
ℓ, which has weight x
1
,
ℓ; so ω
(
Q
ℓ
)
=
x
ℓ
,
ℓ. Now in every m-path cover of P
(
0
,
n
) vertex u
1 must be covered by such a path Q
ℓ, so f
m
,
n
(
1
)
=
∑
ℓ
=
1
m
‍
x
ℓ
,
ℓ
ℙ
m
[
u
ℓ
+
1
,
…
,
u
n
], which is the above formula for j
=
1.
For any2
≤
j
≤
m the path [
u
m
+
1
-
j
,
…
,
u
m
-
1
+
n
] is a subpath of P
(
m
-
1
,
n
). In fact the weighted paths P
(
j
-
1
,
n
) and [
u
m
+
1
-
j
,
…
,
u
m
-
1
+
n
] (except for vertex labels) are identical, so 𝒫
m
(
j
-
1
,
n
)
=
ℙ
m
[
u
m
+
1
-
j
,
…
,
u
m
-
1
+
n
]. From Lemma 9 we have
(25)
f
m
,
n
+
1
-
j
(
j
)
=
𝒫
m
(
j
-
1
,
n
+
1
-
j
)
-
𝒫
m
(
j
-
2
,
n
+
1
-
j
)
=
ℙ
m
[
u
m
+
1
-
j
,
…
,
u
m
+
n
-
j
]
-
1
·
ℙ
m
[
u
m
+
2
-
j
,
…
,
u
m
+
n
-
j
]
=
sum
of
terms
of
ℙ
m
[
u
m
+
1
-
j
,
…
,
u
m
+
n
-
j
]
in
which
vertex
u
m
+
1
-
j
is
covered
by
a
path
whose
weight
is
an
indeterminate
as
opposed
to
a
path
with
weight
1
.
So let vertexu
m
+
1
-
j be covered by a path Q
ℓ of length ℓ
≥
1. Then Q
ℓ begins at vertex u
m
+
1
-
j and ends at vertex u
m
+
ℓ
-
j, which has weight x
1
,
ℓ
+
1
-
j. Hence ω
(
Q
ℓ
)
=
x
ℓ
,
ℓ
+
1
-
j. Furthermore, because Q
ℓ ends at u
m
+
ℓ
-
j if ℓ
<
j, then m
+
ℓ
-
j
≤
m
-
1; hence w
(
Q
ℓ
)
=
0, a contradiction; so ℓ
≥
j.
Now, similar to the above, the sum of the terms ofℙ
m
[
u
m
+
1
-
j
,
…
,
u
m
+
n
-
j
] that contain x
ℓ
,
ℓ
+
1
-
j is x
ℓ
,
ℓ
+
1
-
j
ℙ
m
[
u
m
+
ℓ
+
1
-
j
,
…
,
u
m
+
n
-
j
]. Finally, summing over the lengths ℓ of all possible paths Q
ℓ, namely, summing over ℓ with j
≤
ℓ
≤
m, gives the result.This completes study of the weighted pathP
(
m
-
1
,
n
).


## 3. Matrix Formulation and Trace

We set up our(
m
+
1
)-term recurrence (2) in matrix form.LetX
m
,
0
=
I
m be the m
×
m identity matrix, and for n
≥
1 let X
m
,
n be the m
×
m matrix
(26)
X
m
,
n
=
(
0
1
·
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
⋮
⋮
0
0
0
⋯
1
x
m
,
n
x
m
-
1
,
n
x
m
-
2
,
n
⋯
x
1
,
n
)
.
Let T denote transpose, and let F
m
,
n be the vector F
m
,
n
=
(
f
m
,
n
-
(
m
-
1
)
,
…
,
f
m
,
n
)
T. Then recurrence (2) can be written as
(27)
F
m
,
n
=
X
m
,
n
F
m
,
n
-
1
,
where F
m
,
0
=
(
f
m
,
-
(
m
-
1
)
,
…
,
f
m
,
0
)
T
=
(
1
,
…
,
1
)
T. By iterating this equation we have F
m
,
n
=
Y
m
,
n
F
m
,
0, where
(28)
Y
m
,
n
=
X
m
,
n
X
m
,
n
-
1
⋯
X
m
,
0
=
(
f
m
,
n
-
(
m
-
1
)
(
m
)
·
⋯
·
f
m
,
n
-
(
m
-
1
)
(
1
)
f
m
,
n
-
(
m
-
2
)
(
m
)
·
⋯
·
f
m
,
n
-
(
m
-
2
)
(
1
)
⋮
⋮
⋮
⋮
⋮
f
m
,
n
-
1
(
m
)
·
⋯
·
f
m
,
n
-
1
(
1
)
f
m
,
n
(
m
)
·
⋯
·
f
m
,
n
(
1
)
)
.With tr denoting trace, we have the following.Lemma 13.
Forn
≥
1,
(29)
tr
(
Y
m
,
n
)
=
∑
j
=
1
m
‍
f
m
,
n
+
1
-
j
(
j
)
.We now apply these results to the weighted cycleC
(
n
).


## 4. Weighted CycleC
(
n
) and Trace

We introduce the weighted cycleC
(
n
) for n
≥
1 shown in Figure 1. It has n vertices labelled {
v
1
,
v
2
,
…
,
v
n
} and n edges.Figure 1
WeightedC
(
n
).It is weighted as follows: for1
≤
ℓ
≤
m, let P
ℓ be a path of length ℓ that traverses C
(
n
) clockwise and ends at vertex v
i. We define ω
(
P
ℓ
)
=
x
ℓ
,
i.Thus the weighted cycleC
(
1
) is an isolated vertex v
1 with weight ω
(
v
1
)
=
x
1,1; and the weighted cycle C
(
2
) has 2 vertices {
v
1
,
v
2
} with ω
(
v
1
)
=
x
1,1 and ω
(
v
2
)
=
x
1,2 and 2 edges: edge (
v
1
,
v
2
) with ω
(
v
1
,
v
2
)
=
x
2,2 and edge (
v
2
,
v
1
) with ω
(
v
2
,
v
1
)
=
x
2,1.In Figure1 only the weights of paths of lengths ℓ
=
1 and 2 are shown.Lemma 14.
For1
≤
a
≤
b
≤
n the following m-path cover polynomials, the first which comes from C
(
n
) and the second from P
(
m
-
1
,
n
), are equal:
(30)
ℙ
m
[
v
a
,
…
,
v
b
]
=
ℙ
m
[
u
m
-
1
+
a
,
…
,
u
m
-
1
+
b
]
.Proof.
Except for vertex labels, the weighted paths[
v
a
,
…
,
v
b
] in C
(
n
) and [
u
m
-
1
+
a
,
…
,
u
m
-
1
+
b
] in P
(
m
-
1
,
n
) are identical. Hence the result is obtained.Definition 15.
Forn
≥
1 let 𝒞
m
(
n
) be the m-path cover polynomial of the weighted C
(
n
).In the following, when necessary, we reduce subscripts onu, v, and the second subscript on x, all modulo n. We write u
n
+
t
=
u
t, v
n
+
t
=
v
t, x
ℓ
,
n
+
t
=
x
ℓ
,
t, and so forth.Theorem16 is the main result of this section. Recall the matrix Y
m
,
n from (28).Theorem 16.
Forn
≥
1,
(31)
𝒞
m
(
n
)
=
tr
(
Y
m
,
n
)
.Proof.
Consider the weightedC
(
n
). Vertex v
1 lies in every m-path cover of C
(
n
). Suppose, in such an m-path cover, it is covered by a path P
ℓ of length ℓ that begins at v
n
-
p and ends at v
n
-
p
-
1
+
ℓ, for some p
∈
{
-
1,0
,
1
,
…
,
ℓ
-
2
}. Now 1
≤
ℓ
≤
m; that is, p
+
2
≤
ℓ
≤
m. The sum of the weights of all such paths is then
(32)
∑
ℓ
=
p
+
2
m
‍
x
ℓ
,
n
-
p
-
1
+
ℓ
ℙ
m
[
v
n
-
p
+
ℓ
,
…
,
v
n
-
p
-
1
]
.
But p
∈
{
-
1,0
,
1
,
…
,
m
-
2
}, so
(33)
𝒞
m
(
n
)
=
∑
p
=
-
1
m
-
2
‍
∑
ℓ
=
p
+
2
m
‍
x
ℓ
,
n
-
p
-
1
+
ℓ
ℙ
m
[
v
n
-
p
+
ℓ
,
…
,
v
n
-
p
-
1
]
=
∑
j
=
1
m
‍
∑
ℓ
=
j
m
‍
x
ℓ
,
n
+
ℓ
+
1
-
j
ℙ
m
[
v
n
+
ℓ
+
2
-
j
,
…
,
v
n
+
1
-
j
]
=
∑
j
=
1
m
‍
∑
ℓ
=
j
m
‍
x
ℓ
,
ℓ
+
1
-
j
ℙ
m
[
u
m
+
ℓ
+
1
-
j
,
…
,
u
m
-
j
]
=
∑
j
=
1
m
‍
f
m
,
n
+
1
-
j
(
j
)
=
tr
(
Y
m
,
n
)
,
letting j
=
p
+
2 at the second line, and using subscript reduction modulo n and Lemma 14 at the third line, then Corollary 12 at the fourth line, and Lemma 13 at the last line.Example 17.
Form
=
3 and n
=
4 consider the weighted C
(
4
) in Figure 2.Figure 2
WeightedC
(
4
).The3-paths are weighted as follows:
(34)
ℓ
=
1
:
ω
[
v
1
]
=
x
1,1
,
ω
[
v
2
]
=
x
1,2
,
ω
[
v
3
]
=
x
1,3
,
ω
[
v
4
]
=
x
1,4
,
ℓ
=
2
:
ω
[
v
1
,
v
2
]
=
x
2,2
,
ω
[
v
2
,
v
3
]
=
x
2,3
,
ω
[
v
3
,
v
4
]
=
x
2,4
,
ω
[
v
4
,
v
1
]
=
x
2,1
,
ℓ
=
3
:
ω
[
v
1
,
v
2
,
v
3
]
=
x
3,3
,
ω
[
v
2
,
v
3
,
v
4
]
=
x
3,4
,
ω
[
v
3
,
v
4
,
v
1
]
=
x
3,1
,
ω
[
v
4
,
v
1
,
v
2
]
=
x
3,2
.
By considering all 3-path covers, the 3-path cover polynomial of the weighted C
(
4
) is
(35)
𝒞
3
(
4
)
=
x
1,1
x
1,2
x
1,3
x
1,4
+
x
1,1
x
1,2
x
2,4
+
x
1,2
x
1,3
x
2,1
+
x
1,3
x
1,4
x
2,2
+
x
1,1
x
1,4
x
2,3
+
x
1,3
x
3,2
+
x
1,4
x
3,3
+
x
1,1
x
3,4
+
x
1,2
x
3,1
+
x
2,1
x
2,3
+
x
2,2
x
2,4
.Similar to Example10, the recurrence (12) and the starting conditions following (12) give
(36)
f
3,4
(
1
)
=
x
1,1
x
1,2
x
1,3
x
1,4
+
x
1,1
x
1,2
x
2,4
+
x
1,1
x
1,4
x
2,3
+
x
1,3
x
1,4
x
2,2
+
x
1,1
x
3,4
+
x
1,4
x
3,3
+
x
2,2
x
2,4
,
f
3,3
(
2
)
=
x
1,2
x
1,3
x
2,1
+
x
1,3
x
3,2
+
x
2,1
x
2,3
,
f
3,2
(
3
)
=
x
1,2
x
3,1
.Together with the following matrices(37)
Y
3,4
=
X
3,4
X
3,3
X
3,2
X
3,1
X
3,0
=
(
0
1
0
0
0
1
x
3,4
x
2,4
x
1,4
)
(
0
1
0
0
0
1
x
3,3
x
2,3
x
1,3
)
(
0
1
0
0
0
1
x
3,2
x
2,2
x
1,2
)
(
0
1
0
0
0
1
x
3,1
x
2,1
x
1,1
)
=
(
x
1,2
x
3,1
x
1,2
x
2,1
+
x
3,2
x
1,1
x
1,2
+
x
2,2
x
1,2
x
1,3
x
3,1
+
x
2,3
x
3,1
x
1,3
x
3,2
+
x
2,1
x
2,3
+
x
1,2
x
1,3
x
2,1
x
1,1
x
2,3
+
x
1,3
x
2,2
+
x
1,1
x
1,2
x
1,3
+
x
3,3
x
1,2
x
2,4
x
3,1
+
x
1,2
x
1,3
x
1,4
x
3,1
+
x
1,4
x
2,3
x
3,1
+
x
3,1
x
3,4
x
1,2
x
2,4
x
2,1
+
x
1,2
x
1,3
x
1,4
x
2,1
+
x
1,3
x
1,4
x
3,2
+
x
1,4
x
2,1
x
2,3
+
x
2,1
x
3,4
+
x
2,4
x
3,2
x
1,1
x
3,4
+
x
1,1
x
1,2
x
2,4
+
x
1,1
x
1,4
x
2,3
+
x
1,1
x
1,2
x
1,3
x
1,4
+
x
1,3
x
1,4
x
2,2
+
x
1,4
x
3,3
+
x
2,2
x
2,4
)
,we may check the results from Lemma 13 and Theorem 16,
(38)
𝒞
3
(
4
)
=
tr
(
Y
3,4
)
=
∑
j
=
1
3
‍
f
3,5
-
j
(
j
)
=
f
3,4
(
1
)
+
f
3,3
(
2
)
+
f
3,2
(
3
)
.


## 5. Markov Chain Interpretation

In this section we consider an interesting special case, where in the matrix formulation of the recurrence we have stochastic matrices. A matrix of Form (26) can be considered a transition matrix for a Markov chain with m states under the conditions
(39)
∑
j
‍
x
j
,
n
=
1
,
x
j
,
n
≥
0
,
∀
j
.
Because the probabilities x
j
,
n vary with n, these are the transition matrices for a nonhomogeneous Markov chain. Note also that, as transition matrices are multiplied from left to right, the process is effectively time reversed. In fact,
(40)
P
[
jump
at
time
ν
from
state
m
to
state
j
]
=
x
m
-
j
+
1
,
n
-
ν
+
1
.
This process is often referred to as a ladder process. From any state j, with j
<
m, the process jumps with certainty to j
+
1, then to j
+
2, and so forth, up the ladder, till it reaches state m. At that point it jumps randomly back down the ladder to one of the intermediates states j, 1
≤
j
<
m, and the procedure repeats. Because all of the matrices are stochastic, the row sums of matrices such as Y
m
,
n, see (28), will all equal 1. Recall from Section 3 that
(41)
(
f
m
,
n
-
m
+
1
⋮
f
m
,
n
)
=
Y
m
,
n
(
1
⋮
1
)
.
Thus, we have the following.Proposition 18.
In the stochastic case, all of the path polynomialsf
m
,
n evaluate to 1.


### 5.1. Homogeneous Case

In the case of constant coefficients (see (26)), sending x
ℓ
,
i
→
x
ℓ, for all i, we drop the dependence on n and write
(42)
X
m
=
(
0
1
·
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
⋮
⋮
0
0
0
⋯
1
x
m
x
m
-
1
x
m
-
2
⋯
x
1
)
,
with ∑
‍
x
j
=
1. Now
(43)
Y
m
,
n
=
(
X
m
)
n
is the n-step transition matrix. It is easy to see that a row vector (on the left) fixed by X
m is
(44)
(
x
m
,
x
m
+
x
m
-
1
,
…
,
x
m
+
x
m
-
1
+
⋯
+
x
2
,
1
)
.
Furthermore, under the assumption x
j
>
0, for all j, it is immediate that the chain is irreducible and aperiodic, hence ergodic. That is,
(45)
lim
n
→
∞
Y
m
,
n
=
Ω
exists and has equal rows, and each row proportional to the left-invariant vector indicated above normalized to row sum 1.Example 19.
Take the uniform casex
j
=
1
/
m, 1
≤
j
≤
m. Then we have the fixed vector (
1,2
,
3
,
…
,
m
) and the limits
(46)
lim
n
→
∞
f
m
,
n
(
j
)
=
2
(
m
-
j
+
1
)
m
(
m
+
1
)
.
Thus, for large n, if we randomly choose an m-path cover of P
(
m
-
1
,
n
) then the probability that it belongs to the j-fundamental solution is 2
(
m
-
j
+
1
)
/
m
(
m
+
1
). In particular, the first fundamental solution satisfies
(47)
lim
n
→
∞
f
m
,
n
(
1
)
=
2
m
+
1
.
So them-path cover polynomial model provides a combinatorial model for nonhomogeneous Markov chains. A closely related model, the trellis, is discussed in detail below.


## 5.1. Homogeneous Case

In the case of constant coefficients (see (26)), sending x
ℓ
,
i
→
x
ℓ, for all i, we drop the dependence on n and write
(42)
X
m
=
(
0
1
·
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
⋮
⋮
0
0
0
⋯
1
x
m
x
m
-
1
x
m
-
2
⋯
x
1
)
,
with ∑
‍
x
j
=
1. Now
(43)
Y
m
,
n
=
(
X
m
)
n
is the n-step transition matrix. It is easy to see that a row vector (on the left) fixed by X
m is
(44)
(
x
m
,
x
m
+
x
m
-
1
,
…
,
x
m
+
x
m
-
1
+
⋯
+
x
2
,
1
)
.
Furthermore, under the assumption x
j
>
0, for all j, it is immediate that the chain is irreducible and aperiodic, hence ergodic. That is,
(45)
lim
n
→
∞
Y
m
,
n
=
Ω
exists and has equal rows, and each row proportional to the left-invariant vector indicated above normalized to row sum 1.Example 19.
Take the uniform casex
j
=
1
/
m, 1
≤
j
≤
m. Then we have the fixed vector (
1,2
,
3
,
…
,
m
) and the limits
(46)
lim
n
→
∞
f
m
,
n
(
j
)
=
2
(
m
-
j
+
1
)
m
(
m
+
1
)
.
Thus, for large n, if we randomly choose an m-path cover of P
(
m
-
1
,
n
) then the probability that it belongs to the j-fundamental solution is 2
(
m
-
j
+
1
)
/
m
(
m
+
1
). In particular, the first fundamental solution satisfies
(47)
lim
n
→
∞
f
m
,
n
(
1
)
=
2
m
+
1
.
So them-path cover polynomial model provides a combinatorial model for nonhomogeneous Markov chains. A closely related model, the trellis, is discussed in detail below.


## 6. Edge-Weightedm-Trellis T
(
m
)

In this section we deal with theedge-weighted
m
-trellis, T
(
m
), shown in Figure 3, and give another method of generating f
m
,
n
(
j
) and 𝒞
m
(
n
).Figure 3
Edge-weightedm-trellis T
(
m
).The vertices ofT
(
m
) are labelled {
w
1
,
w
2
,
…
,
w
m
}. All edges in T
(
m
) are directed, with arrows as shown. All circuits in T
(
m
) are directed and are traversed in the direction of the arrows. We use S to denote a directed circuit in T
(
m
), which we simply call a circuit. A circuit is based at vertex w
j if it begins and ends at vertex w
j. A circuit may pass through the same vertex more than once. The length of a circuit S is the number of edges in it.The weights on the edges ofT
(
m
) are taken from {
1
,
x
1
,
d
,
…
,
x
m
,
d
} where d
≥
1, as shown. The weight of circuit S, w
(
S
), is the product of the weights of all the edges in S. If the edge with weight x
j
,
d is traversed as the kth edge in S, then x
j
,
k is a factor in w
(
S
); thus the meaning of x
j
,
d here is different from that in Sections 2 and 4. We allow empty circuits with length 0.Definition 20.
Let𝒯
m
(
w
j
,
0
)
=
1 and, for s
≥
1, let 𝒯
m
(
w
j
,
s
) be the sum of the weights of all circuits in T
(
m
) that are based at vertex w
j with length s.Notation. We use standard multiset notation: 1
k
=
1
·
1
⋯
1
·
1
︸
k, and 1
0 means no occurrences of 1.Theorem 21.
Fors
≥
0,
(48)
𝒯
m
(
w
1
,
s
)
=
𝒫
m
(
0
,
s
)
.Proof.
By strong induction ons. Now 𝒯
m
(
w
1
,
0
)
=
𝒫
m
(
0,0
)
=
1; hence (48) is true for s
=
0. We now assume that 𝒯
m
(
w
1
,
s
′
)
=
𝒫
m
(
0
,
s
′
) for all 0
≤
s
′
≤
s. Consider any term in 𝒯
m
(
w
1
,
s
+
1
) is the weight of some circuit S in T
(
m
) based at vertex w
1 with length s
+
1. Clearly S ends with a k-cycle based at vertex w
1, for some k with 1
≤
k
≤
m. Thus the last edge of S is (
w
k
,
w
1
), with weight x
k
,
s
+
1, and the previous k
-
1 edges are (
w
k
,
w
k
-
1
)
,
(
w
k
-
1
,
w
k
-
2
)
,
…
,
(
w
2
,
w
1
), each of weight 1. Hence ω
(
S
)
=
𝒯
m
(
w
1
,
s
+
1
-
k
)
1
k
-
1
x
k
,
s
+
1. Thus
(49)
𝒯
m
(
w
1
,
s
+
1
)
=
∑
k
=
1
m
‍
x
k
,
s
+
1
𝒯
m
(
w
1
,
s
+
1
-
k
)
=
∑
k
=
1
m
‍
x
k
,
s
+
1
𝒫
m
(
0
,
s
+
1
-
k
)
=
𝒫
m
(
0
,
s
+
1
)
,
using the strong induction hypothesis and then Theorem 8. So the induction goes through and (48) is true for all s
≥
0.Let𝒯
m
+
c
(
w
1
,
s
) be the expression obtained when every indeterminate x
a
,
b in 𝒯
m
(
w
1
,
s
) is replaced by x
a
,
b
+
c; similarly for other expressions.Recall that[
u
m
,
…
,
u
m
-
1
+
s
] is a subpath of P
(
m
-
1
,
n
) for s
≥
0; for s
=
0 the path [
u
m
,
u
m
-
1
] is the empty path P
(
0,0
), and 𝒫
m
(
0,0
)
=
1.Corollary 22.
Fors
≥
0 and 0
≤
c
≤
n
-
s,
(50)
𝒯
m
+
c
(
w
1
,
s
)
=
ℙ
m
[
u
m
+
c
,
…
,
u
m
-
1
+
s
+
c
]
.Proof.
Fors
=
0 we have 𝒯
m
+
c
(
w
1
,
0
)
=
ℙ
m
[
u
m
+
c
,
u
m
-
1
+
c
]
=
1. For s
≥
1 then [
u
m
,
…
,
u
m
-
1
+
s
] is a subpath of P
(
m
-
1
,
n
) so, for every n
≥
s, we have 𝒫
m
(
0
,
s
)
=
ℙ
m
[
u
m
,
…
,
u
m
-
1
+
s
]. Now, from Theorem 21, 𝒯
m
(
w
1
,
s
)
=
𝒫
m
(
0
,
s
), so 𝒯
m
+
c
(
w
1
,
s
)
=
𝒫
m
+
c
(
0
,
s
)
=
ℙ
m
[
u
m
+
c
,
…
,
u
m
-
1
+
s
+
c
], as required.We now connect𝒯
m
(
w
j
,
n
) and the fundamental solutions of the (
m
+
1
)-term recurrence (2).Theorem 23.
Forn
≥
0,
(51)
𝒯
m
(
w
j
,
n
)
=
f
m
,
n
+
1
-
j
(
j
)
.Proof.
Consider a circuitS in T
(
m
) based at vertex w
j with n edges. Then, for some 0
≤
k
≤
m
-
j, the first k edges in this circuit are (
w
j
,
w
j
+
1
)
,
(
w
j
+
1
,
w
j
+
2
)
,
…
,
(
w
j
+
k
-
1
,
w
j
+
k
), followed by edge (
w
j
+
k
,
w
1
) ending at vertex w
1. These edges contribute 1
k
x
j
+
k
,
k
+
1 to w
(
S
). Now, starting at vertex w
1, the last j
-
1 edges traversed in S are (
w
1
,
w
2
)
,
(
w
2
,
w
3
)
,
…
,
(
w
j
-
1
,
w
j
), contributing 1
j
-
1 to w
(
S
). Hence ω
(
S
)
=
x
j
+
k
,
k
+
1
𝒯
m
+
(
k
+
1
)
(
w
1
,
n
-
j
-
k
).
Thus(52)
𝒯
m
(
w
j
,
n
)
=
∑
k
=
0
m
-
j
‍
x
j
+
k
,
k
+
1
𝒯
m
+
(
k
+
1
)
(
w
1
,
n
-
j
-
k
)
=
∑
ℓ
=
j
m
‍
x
ℓ
,
ℓ
+
1
-
j
𝒯
m
+
(
ℓ
+
1
-
j
)
(
w
1
,
n
-
ℓ
)
=
∑
ℓ
=
j
m
‍
x
ℓ
,
ℓ
+
1
-
j
ℙ
m
[
u
m
+
ℓ
+
1
-
j
,
…
,
u
m
+
n
-
j
]
=
f
m
,
n
+
1
-
j
(
j
)
,
putting ℓ
=
j
+
k at the second line, then using Corollary 22 with c
=
ℓ
+
1
-
j and s
=
n
-
ℓ at the third line, and finally using Corollary 12 at the last line.Example 24.
ConsiderT
(
3
), the edge-weighted 3-trellis; see Figure 4.(a)
𝒯
3
(
w
2
,
5
) = sum of weights of circuits of T
(
3
) based at w
2 with length 5
=
x
2,1
x
1,2
x
1,3
x
1,4
1
+
x
2,1
x
1,2
1
x
2,4
1
+
x
2,1
1
·
1
x
3,4
1
+
x
2,1
1
x
2,3
x
1,4
1
+
1
x
3,2
x
1,3
x
1,4
1 + 1
x
3,2
1
x
2,4
1
=
f
3,4
(
2
), as in Example 10.
(b)
𝒯
3
(
w
3
,
6
)
= sum of weights of circuits based at w
3 with length 6. We observe that the first edge in such a circuit is edge (
w
3
,
w
1
) of weight x
3,1; hence x
3,1 is a factor of every term in 𝒯
3
(
w
3
,
6
)
=
f
3,4
(
3
), consistent with Example 10 again.
Finally, we bring the results from Lemma13 and Theorems 16 and 23 together in Theorem 25.Figure 4
Edge-weighted3-trellis T
(
3
).Theorem 25.
For1
≤
n
≤
m,
(53)
𝒞
m
(
n
)
=
tr
(
Y
m
,
n
)
=
∑
j
=
1
m
‍
𝒯
m
(
w
j
,
n
)
.Example 26.
Again, fromT
(
3
), we have 𝒞
3
(
4
)
=
∑
j
=
1
3
‍
𝒯
3
(
w
j
,
4
):
(54)
𝒯
3
(
w
1
,
4
)
=
x
1,1
x
1,2
x
1,3
x
1,4
+
x
1,1
x
1,2
1
x
2,4
+
x
1,1
1
x
2,3
x
1,4
+
x
1,1
1
·
1
x
3,4
+
1
x
2,2
x
1,3
x
1,4
+
1
x
2,2
1
x
2,4
+
1
·
1
x
3,3
x
1,4
=
f
3,4
(
1
)
,
𝒯
3
(
w
2
,
4
)
=
x
2,1
x
1,2
x
1,3
1
+
x
2,1
1
x
2,3
1
+
1
x
3,2
x
1,3
1
=
f
3,3
(
2
)
,
𝒯
3
(
w
3
,
4
)
=
x
3,1
x
1,2
1
·
1
=
f
3,2
(
3
)
,
which are consistent with the above definitions and results and with Example 17.


## 7. Homogeneous Case,x
ℓ
,
i
→
x
ℓ

In this section, we consider the case of constant coefficients, that is, where the indeterminatesx
ℓ
,
i are independent of i.Notation. We use * to modify a path or expression or matrix in which weights or indeterminates x
ℓ
,
i are replaced with x
ℓ.First we review some known properties ofm-path polynomials using standard techniques. Then we show how our model recovers these results combinatorially.


### 7.1. Constant Coefficient Recurrences

This subsection mainly establishes notation and recalls basic results of interest.Consider the recurrence(55)
y
n
=
∑
i
=
1
m
‍
x
i
y
n
-
i
.We begin with the first fundamental solution. The following is standard and readily derived via geometric series and multinomial expansion.Proposition 27.
One has the generating function and formula(56)
∑
n
≥
0
‍
h
n
t
n
=
1
1
-
∑
i
=
1
m
x
i
t
i
=
∑
n
≥
0
‍
∑
∑
ℓ
s
ℓ
=
n
‍
(
s
1
+
s
2
+
⋯
+
s
m
s
1
,
s
2
,
…
,
s
m
)
x
1
s
1
x
2
s
2
⋯
x
m
s
m
t
n
giving the (first) fundamental solution, h
n, to the recurrence, that is, with initial values h
i
=
0, -
(
m
-
1
)
≤
i
<
0, h
0
=
1.The matrixX
m takes the form, confor Section 5.1,
(57)
X
m
=
(
0
1
0
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
⋱
⋮
0
0
0
⋱
1
x
m
x
m
-
1
x
m
-
2
⋯
x
1
)
so that det
(
I
-
t
X
m
)
=
1
-
∑
i
=
1
m
‍
x
i
t
i. Define the (
r
+
1
)st fundamental solution to recurrence (55) to be the one with initial conditions
(58)
y
i
=
0
,
for
-
(
m
-
1
)
≤
i
≤
0
,
i
≠
-
r
y
-
r
=
1
,
and denote this fundamental solution by h
n
(
r
+
1
), with h
n
=
h
n
(
1
). Then the entries in the bottom row of (
X
m
)
n are exactly the values
(59)
(
(
X
m
)
n
)
(
m
,
j
)
=
h
n
(
m
-
j
+
1
)
.
In general,
(60)
(
(
X
m
)
n
)
(
i
,
j
)
=
h
n
-
m
+
i
(
m
-
j
+
1
)
.The fundamental solutions forr
>
0 can be expressed in terms of the first fundamental solution as follows.Proposition 28.
The(
r
+
1
)st fundamental solution to the recurrence (55) is given by
(61)
h
n
(
r
+
1
)
=
h
n
+
r
-
∑
k
=
0
r
-
1
‍
h
n
+
k
x
r
-
k
,
where h
n denotes the first fundamental solution.Proof.
We will illustrate forr
≤
2 that shows how the general case works. We have
(62)
h
n
(
1
)
=
h
n
,
h
n
(
2
)
=
h
n
+
1
-
x
1
h
n
,
h
n
(
3
)
=
h
n
+
2
-
x
1
h
n
+
1
-
x
2
h
n
.
For r
=
1, we obtain 0 for nonpositive n, except for n
=
-
1, as required. Similarly, for r
=
2, for nonpositive n we obtain 1 precisely for n
=
-
2; otherwise we get 0. Note that the subtractions are necessary to cancel off terms when 0
≥
n
>
-
r. Since the coefficients are independent of n, these are indeed solutions to the recurrence. Thus the result is obtained.Now for the trace, we have the following.Proposition 29.
The trace of(
X
m
)
n is given by
(63)
tr
(
X
m
)
n
=
∑
j
=
1
m
‍
j
h
n
-
j
x
j
.Proof.
From (60), we have, using Proposition 28,
(64)
tr
(
X
m
)
n
=
∑
i
=
1
m
‍
h
n
-
m
+
i
(
m
-
i
+
1
)
=
∑
i
=
0
m
-
1
‍
h
n
-
i
(
i
+
1
)
=
∑
i
=
0
m
-
1
‍
[
h
n
-
∑
k
=
0
i
-
1
‍
h
n
-
i
+
k
x
i
-
k
]
=
∑
i
=
0
m
-
1
‍
[
h
n
-
∑
j
=
1
i
‍
h
n
-
j
x
j
]
=
m
h
n
-
∑
i
=
0
m
-
1
‍
∑
j
=
1
i
‍
h
n
-
j
x
j
(
next
,
interchanging
the
order
of
summation
)
=
m
h
n
-
∑
j
=
1
m
-
1
‍
∑
i
=
j
m
-
1
‍
h
n
-
j
x
j
=
m
h
n
-
∑
j
=
1
m
-
1
‍
(
m
-
j
)
h
n
-
j
x
j
=
m
[
h
n
-
∑
j
=
1
m
-
1
‍
h
n
-
j
x
j
]
+
∑
j
=
1
m
-
1
‍
j
h
n
-
j
x
j
=
∑
j
=
1
m
‍
j
h
n
-
j
x
j
(
by
the
recurrence
for
{
h
n
}
)
.Remark 30.
These are a variation on Newton’s Identities relating power sum symmetric functions and elementary symmetric functions. Here, the homogeneous symmetric functions,h
n, play a role as well.


### 7.2. Combinatorial Proofs

We now show how these formulas may be derived combinatorially by our model with the specializationx
ℓ
,
i
→
x
ℓ. The weighted path P
*
(
2,3
) looks like
(65)Notation. Consistent with the above, we use h or ℋ to represent expressions in which we have replaced x
ℓ
,
i with x
ℓ. Thus ℋ
m
(
r
,
n
)
=
𝒫
m
*
(
r
,
n
), for 0
≤
r
≤
m
-
1; see Definition 6 of weighted path P
(
r
,
n
).


#### 7.2.1. First Fundamental Solution

Proposition27 is readily seen from the weighting of path P
*
(
m
-
1
,
n
). For the first fundamental solution, there are no vertices with weight 1, and no edges weighted 0. The first vertex has weight x
1, and so on. In an m-path cover the exponent s
ℓ is the number of paths of length ℓ, for each 1
≤
ℓ
≤
m, and the multinomial coefficient counts the number of m-path covers obtained from any fixed set of m-paths. So this model gives a visual interpretation to the analytic formula.


#### 7.2.2. Higher Fundamental Solutions

Start with the following.Lemma 31.
For a fixedr with 1
≤
r
≤
m
-
1 and any n
≥
1,
(66)
ℋ
m
(
r
,
n
)
-
ℋ
m
(
r
-
1
,
n
)
=
∑
ℓ
=
r
+
1
m
‍
x
ℓ
ℋ
m
(
0
,
n
+
r
-
ℓ
)
.Proof.
Forr
≥
1, consider the weighted path P
*
(
r
,
n
). The first vertex u
1 must lie in every m-path cover of this path, say on a path Q
ℓ of length ℓ for 1
≤
ℓ
≤
m, starting at u
1. If ℓ
=
1 then ω
(
Q
1
)
=
ω
(
u
1
)
=
1, and the sum of all such m-path covers is thus 1
·
ℋ
m
(
r
-
1
,
n
). If 2
≤
ℓ
≤
r then Q
ℓ finishes at vertex u
ℓ where ω
(
u
ℓ
)
=
1, so ω
(
Q
ℓ
)
=
0. And if r
+
1
≤
ℓ
≤
m then Q
ℓ finishes at vertex u
ℓ where ω
(
u
ℓ
)
=
x
1 and so ω
(
Q
ℓ
)
=
x
ℓ, and the sum of all such m-path covers is x
ℓ
ℋ
m
(
0
,
n
+
r
-
ℓ
). Hence ℋ
m
(
r
,
n
)
=
ℋ
m
(
r
-
1
,
n
)
+
∑
ℓ
=
r
+
1
m
‍
x
ℓ
ℋ
m
(
0
,
n
+
r
-
ℓ
), and so the result is obtained.Now for a combinatorial proof of Proposition28.Theorem 32.
For the fundamental solutions to the recurrence for the homogeneous path polynomials, one has(67)
h
n
(
r
+
1
)
=
h
n
+
r
-
∑
ℓ
=
1
r
‍
x
ℓ
h
n
+
r
-
ℓ
.Proof.
By our definitions and Corollary11(ii) we have h
n
=
f
m
,
n
(
1
)
*
=
𝒫
m
*
(
0
,
n
)
=
ℋ
m
(
0
,
n
). And, from Lemmas 9 and 31, we have
(68)
h
n
(
r
+
1
)
=
ℋ
m
(
r
,
n
)
-
ℋ
m
(
r
-
1
,
n
)
=
∑
ℓ
=
r
+
1
m
‍
x
ℓ
h
n
+
r
-
ℓ
.
Now(69)
h
n
+
r
=
ℋ
m
(
0
,
n
+
r
)
=
∑
ℓ
=
1
m
‍
x
ℓ
h
n
+
r
-
ℓ
=
∑
ℓ
=
1
r
‍
x
ℓ
h
n
+
r
-
ℓ
+
∑
ℓ
=
r
+
1
m
‍
x
ℓ
h
n
+
r
-
ℓ
=
∑
ℓ
=
1
r
‍
x
ℓ
h
n
+
r
-
ℓ
+
h
n
(
r
+
1
)
,
where, at the second line, we note that in every m-path cover of the weighted path P
*
(
0
,
n
+
r
) vertex u
n
+
r must lie on a path Q
ℓ of length ℓ and weight x
ℓ where 1
≤
ℓ
≤
m, and at the last line we use (68). This gives the result.


#### 7.2.3. Trace Formula

We now give a combinatorial derivation of the trace formula in Proposition29.First let𝒯
m
(
n
) be the sum of the weights of all circuits of length n in T
*
(
m
) and the m-trellis with edge-weights x
ℓ
,
i replaced by x
ℓ; that is, 𝒯
m
(
n
)
=
∑
j
=
1
m
‍
𝒯
m
*
(
w
j
,
n
); see Section 6.Theorem 33.
For anyn
≥
1,
(70)
tr
(
X
m
)
n
=
∑
j
=
1
m
‍
j
x
j
h
n
-
j
.Proof.
We recall that the indeterminates in any term of𝒯
m
(
n
) are initially ordered according to the edges traversed in the corresponding circuit; see Example 26. Let 𝒳
=
x
j
x
ℓ
1
x
ℓ
2
⋯
x
ℓ
r be a typical ordered term in 𝒯
m
(
n
) with all 1’s removed and with first indeterminate x
j. We first show that term 𝒳 occurs j times in 𝒯
m
(
n
).
When there are two successive indeterminatesx
ℓ and x
ℓ
′ in 𝒳, then, in the corresponding circuit, the edges traversed are first (
w
ℓ
,
w
1
) of weight x
ℓ, followed by the ℓ
′
-
1 edges (
w
1
,
w
2
)
,
(
w
2
,
w
3
)
,
…
,
(
w
ℓ
′
-
1
,
w
ℓ
′
) each of weight 1, and then finishing with the edge (
w
ℓ
′
,
w
1
) of weight x
ℓ
′. Hence pair x
ℓ
x
ℓ
′ becomes x
ℓ
1
ℓ
′
-
1
x
ℓ
′ when the indeterminates are considered as weights on edges in a circuit in T
*
(
m
).
Now, because the first indeterminate in𝒳 is x
j, any circuit corresponding to 𝒳 must be based at vertex w
j
′ for some j
′
∈
{
1,2
,
…
,
j
}. Hence 𝒳 will appear in 𝒯
m
(
n
) as
(71)
1
j
-
j
′
x
j
1
ℓ
1
-
1
x
ℓ
1
1
ℓ
2
-
1
x
ℓ
2
1
ℓ
3
-
1
⋯
1
ℓ
r
-
1
x
ℓ
r
1
j
′
-
1
,
for each j
′
∈
{
1,2
,
…
,
j
} in 𝒯
m
(
n
). There are j such j
′, so there are j occurrences of term 𝒳 in 𝒯
m
(
n
).
Now consider an occurrence of𝒳 in which j
′
=
j, namely,
(72)
x
j
1
ℓ
1
-
1
x
ℓ
1
1
ℓ
2
-
1
x
ℓ
2
1
ℓ
3
-
1
⋯
1
ℓ
r
-
1
x
ℓ
r
1
j
-
1
.
Let(73)
𝒳
x
j
1
j
-
1
=
1
ℓ
1
-
1
x
ℓ
1
1
ℓ
2
-
1
x
ℓ
2
1
ℓ
3
-
1
⋯
1
ℓ
r
-
1
x
ℓ
r
=
𝒵
.
Then the sequence of edges traversed in T
*
(
m
) corresponding to 𝒵 begins at w
1 and ends at w
1, and so is a circuit based at w
1, with length n
-
1
-
(
j
-
1
)
=
n
-
j. Thus 𝒵
∈
𝒯
m
*
(
w
1
,
n
-
j
). Conversely given any 𝒵
∈
𝒯
m
*
(
w
1
,
n
-
j
) then x
j
𝒵
1
j
-
1 is an occurrence of term 𝒳 starting with 1
0 and ending with 1
j
-
1. Thus (
∑
j
′
=
j
‍
𝒳
)
/
x
j
=
𝒯
m
*
(
w
1
,
n
-
j
) and ∑
j
′
=
j
‍
𝒳
=
x
j
𝒯
m
*
(
w
1
,
n
-
j
).
Now we can partition the weighted circuits ofT
*
(
m
) of length n by their first indeterminate x
j (ignoring the edges of weight 1 preceding this first indeterminate). That is, we can partition the terms of 𝒯
m
(
n
) by their first indeterminate x
j. So, using the above arguments, we have
(74)
𝒯
m
(
n
)
=
∑
j
=
1
m
‍
j
x
j
𝒯
m
*
(
w
1
,
n
-
j
)
.
Furthermore, 𝒯
m
*
(
w
1
,
n
-
j
)
=
𝒫
m
*
(
0
,
n
-
j
)
=
f
m
,
n
-
j
(
1
)
*
=
h
n
-
j; the first equality is Theorem 21, the second is Corollary 11(ii), and the third is by definition of h
n. So finally,
(75)
tr
(
X
m
n
)
=
𝒯
m
(
n
)
=
∑
j
=
1
m
‍
j
x
j
𝒯
m
*
(
w
1
,
n
-
j
)
=
∑
j
=
1
m
‍
j
x
j
h
n
-
j
.Example 34.
See Examples17 and 26. Here m
=
3 and n
=
4:
(76)
tr
(
X
3
4
)
=
𝒯
3
(
4
)
=
x
1
4
+
4
x
1
2
x
2
+
4
x
1
x
3
+
2
x
2
2
=
x
1
(
x
1
3
+
2
x
1
x
2
+
x
3
)
+
2
x
2
(
x
1
2
+
x
2
)
+
3
x
3
(
x
1
)
=
x
1
(
f
3,3
(
1
)
*
)
+
2
x
2
(
f
3,2
(
1
)
*
)
+
3
x
3
(
f
3,1
(
1
)
*
)
=
x
1
h
3
+
2
x
2
h
2
+
3
x
3
h
1
,
where, at line 2, we have rearranged the terms according to their first indeterminate x
j, using Example 26, and combined like terms.Remark 35.
From Theorem25 and our definitions of matrices Y
m
,
n and X
m from Sections 3 and 5.1, respectively, we have the following equalities:
(77)
𝒞
m
*
(
n
)
=
tr
(
Y
m
,
n
*
)
=
∑
j
=
1
m
‍
𝒯
m
*
(
w
j
,
n
)
,
tr
(
Y
m
,
n
*
)
=
tr
(
X
m
n
)
.
Thus, from Theorem33,
(78)
∑
j
=
1
m
‍
𝒯
m
*
(
w
j
,
n
)
=
∑
j
=
1
m
‍
j
x
j
𝒯
m
*
(
w
1
,
n
-
j
)
.


## 7.1. Constant Coefficient Recurrences

This subsection mainly establishes notation and recalls basic results of interest.Consider the recurrence(55)
y
n
=
∑
i
=
1
m
‍
x
i
y
n
-
i
.We begin with the first fundamental solution. The following is standard and readily derived via geometric series and multinomial expansion.Proposition 27.
One has the generating function and formula(56)
∑
n
≥
0
‍
h
n
t
n
=
1
1
-
∑
i
=
1
m
x
i
t
i
=
∑
n
≥
0
‍
∑
∑
ℓ
s
ℓ
=
n
‍
(
s
1
+
s
2
+
⋯
+
s
m
s
1
,
s
2
,
…
,
s
m
)
x
1
s
1
x
2
s
2
⋯
x
m
s
m
t
n
giving the (first) fundamental solution, h
n, to the recurrence, that is, with initial values h
i
=
0, -
(
m
-
1
)
≤
i
<
0, h
0
=
1.The matrixX
m takes the form, confor Section 5.1,
(57)
X
m
=
(
0
1
0
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
⋱
⋮
0
0
0
⋱
1
x
m
x
m
-
1
x
m
-
2
⋯
x
1
)
so that det
(
I
-
t
X
m
)
=
1
-
∑
i
=
1
m
‍
x
i
t
i. Define the (
r
+
1
)st fundamental solution to recurrence (55) to be the one with initial conditions
(58)
y
i
=
0
,
for
-
(
m
-
1
)
≤
i
≤
0
,
i
≠
-
r
y
-
r
=
1
,
and denote this fundamental solution by h
n
(
r
+
1
), with h
n
=
h
n
(
1
). Then the entries in the bottom row of (
X
m
)
n are exactly the values
(59)
(
(
X
m
)
n
)
(
m
,
j
)
=
h
n
(
m
-
j
+
1
)
.
In general,
(60)
(
(
X
m
)
n
)
(
i
,
j
)
=
h
n
-
m
+
i
(
m
-
j
+
1
)
.The fundamental solutions forr
>
0 can be expressed in terms of the first fundamental solution as follows.Proposition 28.
The(
r
+
1
)st fundamental solution to the recurrence (55) is given by
(61)
h
n
(
r
+
1
)
=
h
n
+
r
-
∑
k
=
0
r
-
1
‍
h
n
+
k
x
r
-
k
,
where h
n denotes the first fundamental solution.Proof.
We will illustrate forr
≤
2 that shows how the general case works. We have
(62)
h
n
(
1
)
=
h
n
,
h
n
(
2
)
=
h
n
+
1
-
x
1
h
n
,
h
n
(
3
)
=
h
n
+
2
-
x
1
h
n
+
1
-
x
2
h
n
.
For r
=
1, we obtain 0 for nonpositive n, except for n
=
-
1, as required. Similarly, for r
=
2, for nonpositive n we obtain 1 precisely for n
=
-
2; otherwise we get 0. Note that the subtractions are necessary to cancel off terms when 0
≥
n
>
-
r. Since the coefficients are independent of n, these are indeed solutions to the recurrence. Thus the result is obtained.Now for the trace, we have the following.Proposition 29.
The trace of(
X
m
)
n is given by
(63)
tr
(
X
m
)
n
=
∑
j
=
1
m
‍
j
h
n
-
j
x
j
.Proof.
From (60), we have, using Proposition 28,
(64)
tr
(
X
m
)
n
=
∑
i
=
1
m
‍
h
n
-
m
+
i
(
m
-
i
+
1
)
=
∑
i
=
0
m
-
1
‍
h
n
-
i
(
i
+
1
)
=
∑
i
=
0
m
-
1
‍
[
h
n
-
∑
k
=
0
i
-
1
‍
h
n
-
i
+
k
x
i
-
k
]
=
∑
i
=
0
m
-
1
‍
[
h
n
-
∑
j
=
1
i
‍
h
n
-
j
x
j
]
=
m
h
n
-
∑
i
=
0
m
-
1
‍
∑
j
=
1
i
‍
h
n
-
j
x
j
(
next
,
interchanging
the
order
of
summation
)
=
m
h
n
-
∑
j
=
1
m
-
1
‍
∑
i
=
j
m
-
1
‍
h
n
-
j
x
j
=
m
h
n
-
∑
j
=
1
m
-
1
‍
(
m
-
j
)
h
n
-
j
x
j
=
m
[
h
n
-
∑
j
=
1
m
-
1
‍
h
n
-
j
x
j
]
+
∑
j
=
1
m
-
1
‍
j
h
n
-
j
x
j
=
∑
j
=
1
m
‍
j
h
n
-
j
x
j
(
by
the
recurrence
for
{
h
n
}
)
.Remark 30.
These are a variation on Newton’s Identities relating power sum symmetric functions and elementary symmetric functions. Here, the homogeneous symmetric functions,h
n, play a role as well.


## 7.2. Combinatorial Proofs

We now show how these formulas may be derived combinatorially by our model with the specializationx
ℓ
,
i
→
x
ℓ. The weighted path P
*
(
2,3
) looks like
(65)Notation. Consistent with the above, we use h or ℋ to represent expressions in which we have replaced x
ℓ
,
i with x
ℓ. Thus ℋ
m
(
r
,
n
)
=
𝒫
m
*
(
r
,
n
), for 0
≤
r
≤
m
-
1; see Definition 6 of weighted path P
(
r
,
n
).


### 7.2.1. First Fundamental Solution

Proposition27 is readily seen from the weighting of path P
*
(
m
-
1
,
n
). For the first fundamental solution, there are no vertices with weight 1, and no edges weighted 0. The first vertex has weight x
1, and so on. In an m-path cover the exponent s
ℓ is the number of paths of length ℓ, for each 1
≤
ℓ
≤
m, and the multinomial coefficient counts the number of m-path covers obtained from any fixed set of m-paths. So this model gives a visual interpretation to the analytic formula.


### 7.2.2. Higher Fundamental Solutions

Start with the following.Lemma 31.
For a fixedr with 1
≤
r
≤
m
-
1 and any n
≥
1,
(66)
ℋ
m
(
r
,
n
)
-
ℋ
m
(
r
-
1
,
n
)
=
∑
ℓ
=
r
+
1
m
‍
x
ℓ
ℋ
m
(
0
,
n
+
r
-
ℓ
)
.Proof.
Forr
≥
1, consider the weighted path P
*
(
r
,
n
). The first vertex u
1 must lie in every m-path cover of this path, say on a path Q
ℓ of length ℓ for 1
≤
ℓ
≤
m, starting at u
1. If ℓ
=
1 then ω
(
Q
1
)
=
ω
(
u
1
)
=
1, and the sum of all such m-path covers is thus 1
·
ℋ
m
(
r
-
1
,
n
). If 2
≤
ℓ
≤
r then Q
ℓ finishes at vertex u
ℓ where ω
(
u
ℓ
)
=
1, so ω
(
Q
ℓ
)
=
0. And if r
+
1
≤
ℓ
≤
m then Q
ℓ finishes at vertex u
ℓ where ω
(
u
ℓ
)
=
x
1 and so ω
(
Q
ℓ
)
=
x
ℓ, and the sum of all such m-path covers is x
ℓ
ℋ
m
(
0
,
n
+
r
-
ℓ
). Hence ℋ
m
(
r
,
n
)
=
ℋ
m
(
r
-
1
,
n
)
+
∑
ℓ
=
r
+
1
m
‍
x
ℓ
ℋ
m
(
0
,
n
+
r
-
ℓ
), and so the result is obtained.Now for a combinatorial proof of Proposition28.Theorem 32.
For the fundamental solutions to the recurrence for the homogeneous path polynomials, one has(67)
h
n
(
r
+
1
)
=
h
n
+
r
-
∑
ℓ
=
1
r
‍
x
ℓ
h
n
+
r
-
ℓ
.Proof.
By our definitions and Corollary11(ii) we have h
n
=
f
m
,
n
(
1
)
*
=
𝒫
m
*
(
0
,
n
)
=
ℋ
m
(
0
,
n
). And, from Lemmas 9 and 31, we have
(68)
h
n
(
r
+
1
)
=
ℋ
m
(
r
,
n
)
-
ℋ
m
(
r
-
1
,
n
)
=
∑
ℓ
=
r
+
1
m
‍
x
ℓ
h
n
+
r
-
ℓ
.
Now(69)
h
n
+
r
=
ℋ
m
(
0
,
n
+
r
)
=
∑
ℓ
=
1
m
‍
x
ℓ
h
n
+
r
-
ℓ
=
∑
ℓ
=
1
r
‍
x
ℓ
h
n
+
r
-
ℓ
+
∑
ℓ
=
r
+
1
m
‍
x
ℓ
h
n
+
r
-
ℓ
=
∑
ℓ
=
1
r
‍
x
ℓ
h
n
+
r
-
ℓ
+
h
n
(
r
+
1
)
,
where, at the second line, we note that in every m-path cover of the weighted path P
*
(
0
,
n
+
r
) vertex u
n
+
r must lie on a path Q
ℓ of length ℓ and weight x
ℓ where 1
≤
ℓ
≤
m, and at the last line we use (68). This gives the result.


### 7.2.3. Trace Formula

We now give a combinatorial derivation of the trace formula in Proposition29.First let𝒯
m
(
n
) be the sum of the weights of all circuits of length n in T
*
(
m
) and the m-trellis with edge-weights x
ℓ
,
i replaced by x
ℓ; that is, 𝒯
m
(
n
)
=
∑
j
=
1
m
‍
𝒯
m
*
(
w
j
,
n
); see Section 6.Theorem 33.
For anyn
≥
1,
(70)
tr
(
X
m
)
n
=
∑
j
=
1
m
‍
j
x
j
h
n
-
j
.Proof.
We recall that the indeterminates in any term of𝒯
m
(
n
) are initially ordered according to the edges traversed in the corresponding circuit; see Example 26. Let 𝒳
=
x
j
x
ℓ
1
x
ℓ
2
⋯
x
ℓ
r be a typical ordered term in 𝒯
m
(
n
) with all 1’s removed and with first indeterminate x
j. We first show that term 𝒳 occurs j times in 𝒯
m
(
n
).
When there are two successive indeterminatesx
ℓ and x
ℓ
′ in 𝒳, then, in the corresponding circuit, the edges traversed are first (
w
ℓ
,
w
1
) of weight x
ℓ, followed by the ℓ
′
-
1 edges (
w
1
,
w
2
)
,
(
w
2
,
w
3
)
,
…
,
(
w
ℓ
′
-
1
,
w
ℓ
′
) each of weight 1, and then finishing with the edge (
w
ℓ
′
,
w
1
) of weight x
ℓ
′. Hence pair x
ℓ
x
ℓ
′ becomes x
ℓ
1
ℓ
′
-
1
x
ℓ
′ when the indeterminates are considered as weights on edges in a circuit in T
*
(
m
).
Now, because the first indeterminate in𝒳 is x
j, any circuit corresponding to 𝒳 must be based at vertex w
j
′ for some j
′
∈
{
1,2
,
…
,
j
}. Hence 𝒳 will appear in 𝒯
m
(
n
) as
(71)
1
j
-
j
′
x
j
1
ℓ
1
-
1
x
ℓ
1
1
ℓ
2
-
1
x
ℓ
2
1
ℓ
3
-
1
⋯
1
ℓ
r
-
1
x
ℓ
r
1
j
′
-
1
,
for each j
′
∈
{
1,2
,
…
,
j
} in 𝒯
m
(
n
). There are j such j
′, so there are j occurrences of term 𝒳 in 𝒯
m
(
n
).
Now consider an occurrence of𝒳 in which j
′
=
j, namely,
(72)
x
j
1
ℓ
1
-
1
x
ℓ
1
1
ℓ
2
-
1
x
ℓ
2
1
ℓ
3
-
1
⋯
1
ℓ
r
-
1
x
ℓ
r
1
j
-
1
.
Let(73)
𝒳
x
j
1
j
-
1
=
1
ℓ
1
-
1
x
ℓ
1
1
ℓ
2
-
1
x
ℓ
2
1
ℓ
3
-
1
⋯
1
ℓ
r
-
1
x
ℓ
r
=
𝒵
.
Then the sequence of edges traversed in T
*
(
m
) corresponding to 𝒵 begins at w
1 and ends at w
1, and so is a circuit based at w
1, with length n
-
1
-
(
j
-
1
)
=
n
-
j. Thus 𝒵
∈
𝒯
m
*
(
w
1
,
n
-
j
). Conversely given any 𝒵
∈
𝒯
m
*
(
w
1
,
n
-
j
) then x
j
𝒵
1
j
-
1 is an occurrence of term 𝒳 starting with 1
0 and ending with 1
j
-
1. Thus (
∑
j
′
=
j
‍
𝒳
)
/
x
j
=
𝒯
m
*
(
w
1
,
n
-
j
) and ∑
j
′
=
j
‍
𝒳
=
x
j
𝒯
m
*
(
w
1
,
n
-
j
).
Now we can partition the weighted circuits ofT
*
(
m
) of length n by their first indeterminate x
j (ignoring the edges of weight 1 preceding this first indeterminate). That is, we can partition the terms of 𝒯
m
(
n
) by their first indeterminate x
j. So, using the above arguments, we have
(74)
𝒯
m
(
n
)
=
∑
j
=
1
m
‍
j
x
j
𝒯
m
*
(
w
1
,
n
-
j
)
.
Furthermore, 𝒯
m
*
(
w
1
,
n
-
j
)
=
𝒫
m
*
(
0
,
n
-
j
)
=
f
m
,
n
-
j
(
1
)
*
=
h
n
-
j; the first equality is Theorem 21, the second is Corollary 11(ii), and the third is by definition of h
n. So finally,
(75)
tr
(
X
m
n
)
=
𝒯
m
(
n
)
=
∑
j
=
1
m
‍
j
x
j
𝒯
m
*
(
w
1
,
n
-
j
)
=
∑
j
=
1
m
‍
j
x
j
h
n
-
j
.Example 34.
See Examples17 and 26. Here m
=
3 and n
=
4:
(76)
tr
(
X
3
4
)
=
𝒯
3
(
4
)
=
x
1
4
+
4
x
1
2
x
2
+
4
x
1
x
3
+
2
x
2
2
=
x
1
(
x
1
3
+
2
x
1
x
2
+
x
3
)
+
2
x
2
(
x
1
2
+
x
2
)
+
3
x
3
(
x
1
)
=
x
1
(
f
3,3
(
1
)
*
)
+
2
x
2
(
f
3,2
(
1
)
*
)
+
3
x
3
(
f
3,1
(
1
)
*
)
=
x
1
h
3
+
2
x
2
h
2
+
3
x
3
h
1
,
where, at line 2, we have rearranged the terms according to their first indeterminate x
j, using Example 26, and combined like terms.Remark 35.
From Theorem25 and our definitions of matrices Y
m
,
n and X
m from Sections 3 and 5.1, respectively, we have the following equalities:
(77)
𝒞
m
*
(
n
)
=
tr
(
Y
m
,
n
*
)
=
∑
j
=
1
m
‍
𝒯
m
*
(
w
j
,
n
)
,
tr
(
Y
m
,
n
*
)
=
tr
(
X
m
n
)
.
Thus, from Theorem33,
(78)
∑
j
=
1
m
‍
𝒯
m
*
(
w
j
,
n
)
=
∑
j
=
1
m
‍
j
x
j
𝒯
m
*
(
w
1
,
n
-
j
)
.


## 7.2.1. First Fundamental Solution

Proposition27 is readily seen from the weighting of path P
*
(
m
-
1
,
n
). For the first fundamental solution, there are no vertices with weight 1, and no edges weighted 0. The first vertex has weight x
1, and so on. In an m-path cover the exponent s
ℓ is the number of paths of length ℓ, for each 1
≤
ℓ
≤
m, and the multinomial coefficient counts the number of m-path covers obtained from any fixed set of m-paths. So this model gives a visual interpretation to the analytic formula.


## 7.2.2. Higher Fundamental Solutions

Start with the following.Lemma 31.
For a fixedr with 1
≤
r
≤
m
-
1 and any n
≥
1,
(66)
ℋ
m
(
r
,
n
)
-
ℋ
m
(
r
-
1
,
n
)
=
∑
ℓ
=
r
+
1
m
‍
x
ℓ
ℋ
m
(
0
,
n
+
r
-
ℓ
)
.Proof.
Forr
≥
1, consider the weighted path P
*
(
r
,
n
). The first vertex u
1 must lie in every m-path cover of this path, say on a path Q
ℓ of length ℓ for 1
≤
ℓ
≤
m, starting at u
1. If ℓ
=
1 then ω
(
Q
1
)
=
ω
(
u
1
)
=
1, and the sum of all such m-path covers is thus 1
·
ℋ
m
(
r
-
1
,
n
). If 2
≤
ℓ
≤
r then Q
ℓ finishes at vertex u
ℓ where ω
(
u
ℓ
)
=
1, so ω
(
Q
ℓ
)
=
0. And if r
+
1
≤
ℓ
≤
m then Q
ℓ finishes at vertex u
ℓ where ω
(
u
ℓ
)
=
x
1 and so ω
(
Q
ℓ
)
=
x
ℓ, and the sum of all such m-path covers is x
ℓ
ℋ
m
(
0
,
n
+
r
-
ℓ
). Hence ℋ
m
(
r
,
n
)
=
ℋ
m
(
r
-
1
,
n
)
+
∑
ℓ
=
r
+
1
m
‍
x
ℓ
ℋ
m
(
0
,
n
+
r
-
ℓ
), and so the result is obtained.Now for a combinatorial proof of Proposition28.Theorem 32.
For the fundamental solutions to the recurrence for the homogeneous path polynomials, one has(67)
h
n
(
r
+
1
)
=
h
n
+
r
-
∑
ℓ
=
1
r
‍
x
ℓ
h
n
+
r
-
ℓ
.Proof.
By our definitions and Corollary11(ii) we have h
n
=
f
m
,
n
(
1
)
*
=
𝒫
m
*
(
0
,
n
)
=
ℋ
m
(
0
,
n
). And, from Lemmas 9 and 31, we have
(68)
h
n
(
r
+
1
)
=
ℋ
m
(
r
,
n
)
-
ℋ
m
(
r
-
1
,
n
)
=
∑
ℓ
=
r
+
1
m
‍
x
ℓ
h
n
+
r
-
ℓ
.
Now(69)
h
n
+
r
=
ℋ
m
(
0
,
n
+
r
)
=
∑
ℓ
=
1
m
‍
x
ℓ
h
n
+
r
-
ℓ
=
∑
ℓ
=
1
r
‍
x
ℓ
h
n
+
r
-
ℓ
+
∑
ℓ
=
r
+
1
m
‍
x
ℓ
h
n
+
r
-
ℓ
=
∑
ℓ
=
1
r
‍
x
ℓ
h
n
+
r
-
ℓ
+
h
n
(
r
+
1
)
,
where, at the second line, we note that in every m-path cover of the weighted path P
*
(
0
,
n
+
r
) vertex u
n
+
r must lie on a path Q
ℓ of length ℓ and weight x
ℓ where 1
≤
ℓ
≤
m, and at the last line we use (68). This gives the result.


## 7.2.3. Trace Formula

We now give a combinatorial derivation of the trace formula in Proposition29.First let𝒯
m
(
n
) be the sum of the weights of all circuits of length n in T
*
(
m
) and the m-trellis with edge-weights x
ℓ
,
i replaced by x
ℓ; that is, 𝒯
m
(
n
)
=
∑
j
=
1
m
‍
𝒯
m
*
(
w
j
,
n
); see Section 6.Theorem 33.
For anyn
≥
1,
(70)
tr
(
X
m
)
n
=
∑
j
=
1
m
‍
j
x
j
h
n
-
j
.Proof.
We recall that the indeterminates in any term of𝒯
m
(
n
) are initially ordered according to the edges traversed in the corresponding circuit; see Example 26. Let 𝒳
=
x
j
x
ℓ
1
x
ℓ
2
⋯
x
ℓ
r be a typical ordered term in 𝒯
m
(
n
) with all 1’s removed and with first indeterminate x
j. We first show that term 𝒳 occurs j times in 𝒯
m
(
n
).
When there are two successive indeterminatesx
ℓ and x
ℓ
′ in 𝒳, then, in the corresponding circuit, the edges traversed are first (
w
ℓ
,
w
1
) of weight x
ℓ, followed by the ℓ
′
-
1 edges (
w
1
,
w
2
)
,
(
w
2
,
w
3
)
,
…
,
(
w
ℓ
′
-
1
,
w
ℓ
′
) each of weight 1, and then finishing with the edge (
w
ℓ
′
,
w
1
) of weight x
ℓ
′. Hence pair x
ℓ
x
ℓ
′ becomes x
ℓ
1
ℓ
′
-
1
x
ℓ
′ when the indeterminates are considered as weights on edges in a circuit in T
*
(
m
).
Now, because the first indeterminate in𝒳 is x
j, any circuit corresponding to 𝒳 must be based at vertex w
j
′ for some j
′
∈
{
1,2
,
…
,
j
}. Hence 𝒳 will appear in 𝒯
m
(
n
) as
(71)
1
j
-
j
′
x
j
1
ℓ
1
-
1
x
ℓ
1
1
ℓ
2
-
1
x
ℓ
2
1
ℓ
3
-
1
⋯
1
ℓ
r
-
1
x
ℓ
r
1
j
′
-
1
,
for each j
′
∈
{
1,2
,
…
,
j
} in 𝒯
m
(
n
). There are j such j
′, so there are j occurrences of term 𝒳 in 𝒯
m
(
n
).
Now consider an occurrence of𝒳 in which j
′
=
j, namely,
(72)
x
j
1
ℓ
1
-
1
x
ℓ
1
1
ℓ
2
-
1
x
ℓ
2
1
ℓ
3
-
1
⋯
1
ℓ
r
-
1
x
ℓ
r
1
j
-
1
.
Let(73)
𝒳
x
j
1
j
-
1
=
1
ℓ
1
-
1
x
ℓ
1
1
ℓ
2
-
1
x
ℓ
2
1
ℓ
3
-
1
⋯
1
ℓ
r
-
1
x
ℓ
r
=
𝒵
.
Then the sequence of edges traversed in T
*
(
m
) corresponding to 𝒵 begins at w
1 and ends at w
1, and so is a circuit based at w
1, with length n
-
1
-
(
j
-
1
)
=
n
-
j. Thus 𝒵
∈
𝒯
m
*
(
w
1
,
n
-
j
). Conversely given any 𝒵
∈
𝒯
m
*
(
w
1
,
n
-
j
) then x
j
𝒵
1
j
-
1 is an occurrence of term 𝒳 starting with 1
0 and ending with 1
j
-
1. Thus (
∑
j
′
=
j
‍
𝒳
)
/
x
j
=
𝒯
m
*
(
w
1
,
n
-
j
) and ∑
j
′
=
j
‍
𝒳
=
x
j
𝒯
m
*
(
w
1
,
n
-
j
).
Now we can partition the weighted circuits ofT
*
(
m
) of length n by their first indeterminate x
j (ignoring the edges of weight 1 preceding this first indeterminate). That is, we can partition the terms of 𝒯
m
(
n
) by their first indeterminate x
j. So, using the above arguments, we have
(74)
𝒯
m
(
n
)
=
∑
j
=
1
m
‍
j
x
j
𝒯
m
*
(
w
1
,
n
-
j
)
.
Furthermore, 𝒯
m
*
(
w
1
,
n
-
j
)
=
𝒫
m
*
(
0
,
n
-
j
)
=
f
m
,
n
-
j
(
1
)
*
=
h
n
-
j; the first equality is Theorem 21, the second is Corollary 11(ii), and the third is by definition of h
n. So finally,
(75)
tr
(
X
m
n
)
=
𝒯
m
(
n
)
=
∑
j
=
1
m
‍
j
x
j
𝒯
m
*
(
w
1
,
n
-
j
)
=
∑
j
=
1
m
‍
j
x
j
h
n
-
j
.Example 34.
See Examples17 and 26. Here m
=
3 and n
=
4:
(76)
tr
(
X
3
4
)
=
𝒯
3
(
4
)
=
x
1
4
+
4
x
1
2
x
2
+
4
x
1
x
3
+
2
x
2
2
=
x
1
(
x
1
3
+
2
x
1
x
2
+
x
3
)
+
2
x
2
(
x
1
2
+
x
2
)
+
3
x
3
(
x
1
)
=
x
1
(
f
3,3
(
1
)
*
)
+
2
x
2
(
f
3,2
(
1
)
*
)
+
3
x
3
(
f
3,1
(
1
)
*
)
=
x
1
h
3
+
2
x
2
h
2
+
3
x
3
h
1
,
where, at line 2, we have rearranged the terms according to their first indeterminate x
j, using Example 26, and combined like terms.Remark 35.
From Theorem25 and our definitions of matrices Y
m
,
n and X
m from Sections 3 and 5.1, respectively, we have the following equalities:
(77)
𝒞
m
*
(
n
)
=
tr
(
Y
m
,
n
*
)
=
∑
j
=
1
m
‍
𝒯
m
*
(
w
j
,
n
)
,
tr
(
Y
m
,
n
*
)
=
tr
(
X
m
n
)
.
Thus, from Theorem33,
(78)
∑
j
=
1
m
‍
𝒯
m
*
(
w
j
,
n
)
=
∑
j
=
1
m
‍
j
x
j
𝒯
m
*
(
w
1
,
n
-
j
)
.


## 8. Sequences,x
ℓ
,
i
→
1

In Section7 we specialized by replacing weights x
ℓ
,
i with x
ℓ. In this section we specialize further by replacing all weights x
ℓ
,
i with 1. We denote this operation by #. We then use these # matrices to count m-path covers of the path and cycle.Recall matrixX
m
,
n from (26), we define matrix Z
m:
(79)
Z
m
=
X
m
,
n
#
=
(
0
1
·
⋯
0
0
0
1
⋯
0
⋮
⋮
⋮
⋮
⋮
0
0
0
⋯
1
1
1
1
⋯
1
)
.
Similarly, let c
m
(
n
)
=
𝒞
m
#
(
n
) be the expression 𝒞
m
(
n
) evaluated when all x
ℓ
,
i
=
1. So Y
m
,
n
#
=
Z
m
n and c
m
(
n
)
=
tr
(
Y
m
,
n
#
)
=
tr
(
Z
m
n
). Thus c
m
(
n
) counts the number of m-path covers of the weighted C
(
n
) or of an arbitrary n-cycle. (cf., Corollary 11.1, Section 8, Farrell [2].)Theorem 36.
For1
≤
n
≤
m, one has c
m
(
n
)
=
2
n
-
1.Proof.
Let[
n
]
=
{
1,2
,
…
,
n
} and let C
[
n
] denote the cycle whose vertices are the elements of [
n
] arranged clockwise in a circle. Now n
≤
m so any path cover of C
[
n
] will be an m-path cover. We show that the number of path covers of C
[
n
] is 2
n
-
1.
Given a subset{
i
1
,
i
2
,
…
,
i
k
} of [
n
] with {
i
1
<
i
2
<
⋯
<
i
k
} we define a path cover [
i
1
,
i
1
+
1
,
…
,
i
2
-
1
]
,
[
i
2
,
i
2
+
1
,
…
,
i
3
-
1
]
,
…
,
[
i
k
,
i
k
+
1
,
…
,
i
1
-
1
], of C
[
n
]. Conversely, given a path cover [
i
1
,
i
1
+
1
,
…
,
i
2
-
1
]
,
[
i
2
,
i
2
+
1
,
…
,
i
3
-
1
]
,
…
,
[
i
k
,
i
k
+
1
,
…
,
i
1
-
1
] of C
[
n
] we take the first vertex from each path to form a subset {
i
1
,
i
2
,
…
,
i
k
} of [
n
] and then rearrange its elements to form a subset of [
n
] with increasing elements. These two operations illustrate a bijection from the set of non-empty subsets of [
n
] to the set of m-path covers of C
[
n
]. Hence c
m
(
n
)
=
2
n
-
1.From recurrence (2), Lemma 13, and Theorems 16 and 36, for n
≥
m
+
1 we see that c
m
(
n
) obeys the m-anacci recurrence,
(80)
c
m
(
n
)
=
c
m
(
n
-
1
)
+
c
m
(
n
-
2
)
+
⋯
+
c
m
(
n
-
m
)
=
∑
ℓ
=
1
m
‍
c
m
(
n
-
ℓ
)
,
with starting conditions c
m
(
n
)
=
2
n
-
1 for 1
≤
n
≤
m.In the square array (see Table1) c
m
(
n
) is the (
n
,
m
) entry, for n
,
m
≥
1. Column m is determined by the above m-anacci recurrence. We observe that the (
m
,
m
) main diagonal entry is c
m
(
m
)
=
2
m
-
1.Table 1
n
∖
m
1
2
3
4
5
6
7
8
9
10
⋯
1
1
1
1
1
1
1
1
1
1
1
⋯
2
1
3
3
3
3
3
3
3
3
3
⋯
3
1
4
7
7
7
7
7
7
7
7
⋯
4
1
7
11
15
15
15
15
15
15
15
⋯
5
1
11
21
26
31
31
31
31
31
31
⋯
6
1
18
39
51
57
63
63
63
63
63
⋯
7
1
29
71
99
113
120
127
127
127
127
⋯
8
1
47
131
191
223
239
247
255
255
255
⋯
9
1
76
241
367
439
475
493
502
511
511
⋯
10
1
123
443
708
863
943
983
1003
1013
1023
⋯
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮Consider the triangle, in bold, wherec
m
(
n
) is the (
n
,
m
) entry for all n
≥
1 and 1
≤
m
≤
n; it counts the number of m-path covers of a cycle with n vertices. We have entered the sequence obtained from reading this triangle row-by-row to the Online Encyclopedia of Integer Sequences [9]; it is sequence A185722.Each of the 10 columns of the square array (see Table1) appears as a sequence in [9]; for example, the second column (
m
=
2
) gives sequence A000204 and the third column (
m
=
3
) gives A001644. Thus we have a new combinatorial interpretation for each of these sequences and a connection between them.A closely related sequence is A126198 (replace “k” by “m” in its description). Let T
(
n
,
m
) be the (
n
,
m
) entry of the triangle corresponding to A126198, then T
(
n
,
m
) counts the number of compositions of integer n into parts of size ≤m. Now consider n vertices arranged in a path. A composition of n into parts of size ≤m corresponds naturally to an m-path cover of this path with n vertices by identifying a part of size ℓ in the composition with a path of length ℓ in the corresponding m-path cover. This correspondence can also be reversed. Thus in our terminology, T
(
n
,
m
) is the number of m-path covers of a path with n vertices, and, from Corollary 11(ii) and our operation #, we have T
(
n
,
m
)
=
f
m
,
n
(
1
)
#
=
𝒫
m
#
(
0
,
n
). The (
m
,
m
) main diagonal entry in this triangle is T
(
m
,
m
)
=
2
m
-
1 (as is well known, there are 2
m
-
1 compositions of m) and column m of this triangle is determined by the m-anacci recurrence,
(81)
T
(
n
,
m
)
=
T
(
n
-
1
,
m
)
+
T
(
n
-
2
,
m
)
+
⋯
+
T
(
n
-
m
,
m
)
=
∑
ℓ
=
1
m
‍
T
(
n
-
ℓ
,
m
)
,
for n
≥
m
+
1, with starting conditions T
(
n
,
m
)
=
2
n
-
1 for 1
≤
n
≤
m.The(
n
,
m
) entry in our triangle, c
m
(
n
), counts the number of m-path covers of a cycle with n vertices. We have starting conditions c
m
(
n
)
=
2
n
-
1 as opposed to T
(
n
,
m
)
=
2
n
-
1 above, for 1
≤
n
≤
m.Furthermore, from above and the definition of matrixY
m
,
n from (28), we have T
(
n
,
m
)
=
f
m
,
n
(
1
)
#
= the (
m
,
m
) entry of matrix Y
m
,
n
#
=
Z
m
n. Thus both
(82)
c
m
(
n
)
=
tr
(
Z
m
n
)
,
T
(
n
,
m
)
=
(
Z
m
n
)
(
m
,
m
)
,
can be obtained from matrix Z
m
n. This gives a new derivation of T
(
n
,
m
), and so of sequence A126198.Example 37.
m
=
3 and n
=
4. We have
(83)
Z
3
=
(
0
1
0
0
0
1
1
1
1
)
,
Z
3
4
=
(
1
2
2
2
3
4
4
6
7
)
,
gives
(84)
c
3
(
4
)
=
tr
(
Z
3
4
)
=
11
,
T
(
4,3
)
=
(
Z
3
4
)
(
3,3
)
=
7
;
see Examples 17, 26, and 7.


## Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of the paper.



---

*Source: 258017-2014-01-12.xml*