A Combinatorial Interpretation for Certain Relatives of the Conolly Sequence

Simple item page
dc.creatorBalamohan, B.
dc.creatorLi, Zhiqiang
dc.creatorTanny, Stephen
dc.date2008-01-07
dc.date2008-05-29
dc.date.accessioned2026-07-07T09:41:12Z
dc.date.available2026-07-07T09:41:12Z
dc.descriptionFor any integer s >= 0, we derive a combinatorial interpretation for the family of sequences generated by the recursion (parameterized by s) h_s(n) = h_s(n - s - h_s(n - 1)) + h_s(n - 2 - s - h_s(n - 3)), n > s + 3, with the initial conditions h_s(1) = h_s(2) = ... = h_s(s+2) = 1 and h_s(s+3) = 2. We show how these sequences count the number of leaves of a certain infinite tree structure. Using this interpretation we prove that h_s sequences are "slowly growing", that is, h_s sequences are monotone nondecreasing, with successive terms increasing by 0 or 1, so each sequence hits every positive integer. Further, for fixed s the sequence h_s(n) hits every positive integer twice except for powers of 2, all of which are hit s+2 times. Our combinatorial interpretation provides a simple approach for deriving the ordinary generating functions for these sequences.
dc.description13 pages, 6 figures, 1 table
dc.identifierhttps://arxiv.org/abs/0801.1097
dc.identifierhttp://arxiv.org/abs/0801.1097
dc.identifierJournal of Integer Sequences, Vol. 11 (2008), Article 08.2.1
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/161743
dc.subjectCombinatorics
dc.subject05A15 (Primary) 11B37, 11B39 (Secondary)
dc.titleA Combinatorial Interpretation for Certain Relatives of the Conolly Sequence
dc.typetext

Files

Collections

arXiv