×

A note on counting homomorphisms of paths. (English) Zbl 1292.05023

Summary: We obtain two identities and an explicit formula for the number of homomorphisms of a finite path into a finite path. For the number of endomorphisms of a finite path these give over-count and under-count identities yielding the closed-form formulae of Myers. We also derive finite Laurent series as generating functions which count homomorphisms of a finite path into any path, finite or infinite.

MSC:

05A15 Exact enumeration problems, generating functions
60G50 Sums of independent random variables; random walks

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arworn, Sr.: An algorithm for the numbers of endomorphisms on paths. Discrete Math. 309 (2009), 94-103 · Zbl 1215.05178 · doi:10.1016/j.disc.2007.12.049
[2] Arworn, Sr., Wojtylak, P.: An algorithm for the number of path homomorphisms. Discrete Math. 309 (2009), 5569-5573 · Zbl 1182.05116 · doi:10.1016/j.disc.2008.04.010
[3] Lin, Z.C., Zeng, J.: On the number of congruence classes of paths. arXiv reprint 1112.4026v1 [math.CO]. 17 Dec 2011
[4] Myers, J.: OEIS sequence A102699, editorial note, 23 Dec 2008
[5] Sato M., Cong T.T.: The number of minimal lattice paths restricted by two parallel lines. Discrete Math. 43, 249-26 (1983) · Zbl 0518.05007
[6] The on-line encyclopedia of integer sequences. The OEIS Foundation. http://oeis.org/ · Zbl 1215.05178
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.