A350114 Number of Deutsch paths with peaks at odd height.

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

Author

David Callan, Dec 14 2021

Keywords

• nonn
• easy

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.

Examples

			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.
		

Links

• Helmut Prodinger, Deutsch paths and their enumeration, preprint, arXiv:2003.01918 [math.CO], 2020.

Crossrefs

Cf. A166300.

Programs

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]

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