login
A350114
Number of Deutsch paths with peaks at odd height.
0
1, 0, 1, 0, 2, 2, 6, 11, 26, 56, 129, 294, 684, 1599, 3774, 8961, 21411, 51421, 124081, 300667, 731337, 1785010, 4370431, 10731270, 26419202, 65198847, 161262046, 399692001, 992559011, 2469265633, 6153306125, 15357906136, 38388056063, 96086525311, 240821963528
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
Cf. A166300.
Sequence in context: A299018 A364834 A269830 * A275312 A209026 A091764
KEYWORD
nonn,easy
AUTHOR
David Callan, Dec 14 2021
STATUS
approved