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

Document Type : Research Paper

Authors

Department of Mathematics, Northern Virginia Community College, 2645 College Drive, Woodbridge, VA 22191, United States of America

Abstract

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$.

Keywords

Main Subjects

References

[1] J. D. Farley, The number of order-preserving maps between fences and crowns, Order, 12 (1995) 5–44.
[2] J. B. Remmel, A note on a recursion for the number of derangements, European J. Combin., 4 (1983) 371–374.
[3] Richard P. Stanley, Enumerative combinatorics, I, Wadsworth and Brooks/Cole, Monterey, California, 1986.
[4] R. P. Stanley, personal communication, circa 2003 or 2004.
[5] Richard P. Stanley, Enumerative Combinatorics, I, second edition, Cambridge University Press, Cambridge, 2012.
[6] E. W. Weisstein, Trinomial triangle, MathWorld.
Transactions on Combinatorics
Volume 12, Issue 3 - Serial Number 3
September 2023
Pages 115-130

Files

History

  • Receive Date: 03 January 2022
  • Revise Date: 11 July 2022
  • Accept Date: 27 July 2022
  • Published Online: 01 September 2023

Share

How to cite

Statistics