The number of graph homomorphisms between paths and cycles with loops, a problem from Stanley’s enumerative combinatorics
نویسندگان
1 Department of Mathematics, Northern Virginia Community College, 2645 College Drive, Woodbridge, VA 22191, United States of America
2 Department of Mathematics, Northern Virginia Community College, 2645 College Drive, Woodbridge, VA 22191, United States of America
doi
10.22108/toc.2022.131646.1949چکیده
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$.
