TY - JOUR
ID - 26788
TI - The number of graph homomorphisms between paths and cycles with loops, a problem from Stanleyâ€™s enumerative combinatorics
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - Bandpey, Zeinab
AU - Farley, Jonathan David
AD - Department of Mathematics, Northern Virginia Community College, 2645 College Drive, Woodbridge, VA 22191, United
States of America
Y1 - 2023
PY - 2023
VL - 12
IS - 3
SP - 115
EP - 130
KW - Trinomial coefficient
KW - Path
KW - cycle
KW - (graph) homomorphism
KW - transfer matrix method
DO - 10.22108/toc.2022.131646.1949
N2 - Let $g_{k}(n)$ denote the number of sequences $t_{1},ldots,t_{n}$ in $\{0, 1,\ldots,k-1\}$ such that $t_{j+1}\equiv t_{j}-1, t_{j}$ or $t_{j}+1$ (mod $k$), $1\leq j\leq n$, (where $t_{n+1}$ is identified with $t_{1}$). It is proved combinatorially that $g_{4}(n)= 3^{n}+2+(-1)^{n}$ and $g_{6}(n)= 3^{n}+2^{n+1}+(-1)^{n}$. This solves a problem from Richard P. Stanley's 1986 text, $Enumerative$ $Combinatorics$.
UR - https://toc.ui.ac.ir/article_26788.html
L1 - https://toc.ui.ac.ir/article_26788_8767f1e10b0ecd627858fb572c491887.pdf
ER -