Title of article :
The number of graph homomorphisms between paths and cycles with loops, a problem from Stanley’s enumerative combinatorics
Author/Authors :
Bandpey ، Zeinab Department of Mathematics - Northern Virginia Community College - College Drive , Farley ، Jonathan Department of Mathematics - Northern Virginia Community College - College Drive
Abstract :
Abstract. Let gk(n) denote the number of sequences t1, . . . , tn in {0, 1, . . . , k − 1} such that tj+1 ≡ tj − 1, tj or tj + 1 (mod k), 1 ≤ j ≤ n, (where tn+1 is identified with t1). It is proved combinatorially that g4(n) = 3n + 2 + (−1)n and g6(n) = 3n + 2n+1 + (−1)n. This solves a problem from Richard P. Stanley’s 1986 text, Enumerative Combinatorics.
Keywords :
Trinomial coefficient , Path , cycle , (graph) homomorphism , transfer matrix method
Journal title :
Transactions on Combinatorics
Journal title :
Transactions on Combinatorics
