The number of graph homomorphisms between paths and cycles with loops, a problem from stanley’s enumerative combinatorics

	The number of graph homomorphisms between paths and cycles with loops, a problem from stanley’s enumerative combinatorics
Transactions on Combinatorics
مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 05 مرداد 1401 اصل مقاله (1.54 MB)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2022.131646.1949
نویسندگان
Zeinab Bandpey ¹؛ Jonathan David Farley²
¹Northern Virginia Community college
²Department of Mathematics, Morgan State University
چکیده
Let $g_{k}(n)$ be the number of sequences $t_{1},..., t_{n}$ such that $t_{j+1}equiv t_{j}-1, t_{j}$ or $t_{j}+1$ (mod k), $1leq jleq n$, (where $t_{n+1}$ is interpreted as $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}$. Thus this solves a problem from Richard P. Stanley's 1986 text, $Enumerative$ $Combinatorics$.
کلیدواژه‌ها
Trinomial coefficient؛ path؛ cycle؛ (graph) homomorphism؛ transfer matrix method

آمار تعداد مشاهده مقاله: 8 تعداد دریافت فایل اصل مقاله: 3

Journal Management System. Designed by sinaweb.