there is a lot of what ifs and conjecture

英语翻译
Conjecture 1.There exists a polynomial fk ∈ Q[x] with deg(fk) = ⌈(k−2)/2⌉ such that for a fixed nk (most probably nk = 2k) the equality lk(n) = fk(n) holds for n ≥ nk.
The aim of this paper is to confirm this conjecture by giving an explicit formula for the polynomial fk.For this purpose,we shall prove a new formula for the number of homomorphisms from Pn to Pk,which is the content of the following theorem.
Theorem 2.For any positive integers n and k,
|Hom(Pn,Pk)| = k × 2n−1
From the above theorem we are able to derive the following main result.
Theorem 3.If n ≥ 2k,then
Equivalently,the above formula can be rephrased as follows
When n ≥ 2k,Theorem 3 shows immediately that lk(n) is a polynomial in n of degree ⌈(k−2)/2⌉.This proves Conjecture 1.In particular,we have l1(n) = 1,l2(n) = 2,l3(n) = n,l4(n) = 2(n−1),l5(n) = 1 2n(n−1) and l6(n) = (n−1)(n−2),which coincide with the conjectured values in [5] after shifting the index by 1.
In the next section,we first recall some basic counting results about the lattice paths and then prove Theorem 2.In Section 3 we give the proof of Theorem 3.
2.The number of homomorphisms between paths
One can enumerate homomorphisms from Pn to Pk by picking a fixed point as image
of 1 and moving to vertices which are adjacent to this vertex,as
f ∈ Hom(Pn,Pk) ⇔ ∀x ∈ {1,...,n − 1} :{f(x),f(x + 1)} ∈ E(Pk).
Hence,one can describe all possible moves through the edge structure of the two paths.
For 1 ≤ j ≤ k,let
Obviously,we have
ON THE NUMBER OF CONGRUENCE CLASSES OF PATHS 3
Figure 1.A lattice path from (0,0) to (9,5) that stays between lines y = x and y = x − k + 1,where n = 15 and k = 11.