OFFSET
0,5
COMMENTS
a(n) is the number of closed Deutsch paths of n steps with all peaks at odd height. A Deutsch path is a lattice path of up-steps (1,1) and down-steps (1,-j), j>=1, starting at the origin that never goes below the x-axis, and it is closed if it ends on the x-axis.
A166300 counts closed Deutsch paths with all peaks at even height.
LINKS
Helmut Prodinger, Deutsch paths and their enumeration, preprint, arXiv:2003.01918 [math.CO], 2020.
FORMULA
With F = 1 + x^2 + 2*x^4 + 2*x^5+ ... the g.f. for Deutsch paths with all peaks at odd height and G = 1 + x^3 + x^4 + 2*x^5+ ... the g.f. for Deutsch paths with all peaks at even height, a count based on the decomposition of paths according to the size j of the first down-step (1,-j) that returns the path to ground level yields the pair of simultaneous equations
F = 1 + (x^2*F*G + x^3*(F-1)*F*G)/(1 - x^2*F*G),
G = 1 + (x^2*(F-1)*G + x^3*F*G^2)/(1 - x^2*F*G).
G.f.: (1 + x + x^2 - sqrt[(1 - 3*x + x^2)*(1 + x + x^2)])/(2*x*(1 + x)).
D-finite with recurrence (n+1)*a(n) +(-n+2)*a(n-1) +3*(-n+1)*a(n-2) +3*(-n+3)*a(n-3) +(-n+2)*a(n-4) +(n-5)*a(n-5)=0. - R. J. Mathar, Mar 06 2022
EXAMPLE
a(5) = 2 counts UUU12, UUU21, where U denotes an up-step and a down-step is denoted by its length, and a(6) = 6 counts UUUUU5, UUU1U3, UUU111, UUU3U1, U1UUU3, U1U1U1.
MATHEMATICA
CoefficientList[Series[(1 + x + x^2 - Sqrt[(1 - 3 x + x^2) (1 + x + x^2)])/(2 x + 2 x^2), {x, 0, 20}], x]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
David Callan, Dec 14 2021
STATUS
approved