A360514 Number of 2-color vertex orderings of the labeled path graph on n vertices in which the number 1 is assigned to a vertex in an odd position for n >= 1, a(0) = 1.

1, 1, 1, 4, 9, 56, 185, 1632, 7217, 81664, 451089, 6241280, 41375609, 676506624, 5232134921, 98709925888, 872492313825, 18655203885056, 185503858236065, 4432984678858752, 48978641359097705, 1293646660855398400, 15722400263686662105, 454816628946740707328

Offset

0,4

Comments

Permutations in which every peak (or local maximum) is odd. Bouwer and Star give a recurrence.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..200

I. Bouwer and Z. Star, A question of protocol, The American Mathematical Monthly, 95.2 (1988): 118-121. See O(n).

Ira M. Gessel, A coloring problem, Amer. Math. Monthly 98 (1991), 530-533.

Formula

E.g.f.: (1+sinh(x))/(cosh(x) -x*sinh(x)). - Ira M. Gessel, Feb 23 2026

Prog

(PARI) A360514seq(n) = {my(a=vector(n)); a[1]=a[2]=1; for(n=3, n, a[n] =(n-1) * if(n%2, 2*a[n-2], a[n-2] + (n-2)*a[n-3]) + 2*sum(k=1, (n-3)\2, binomial(n-1, 2*k) * k*(n-2*k-1)*a[2*k-1]*a[n-2*k-2])); a} \\ Andrew Howroyd, Feb 27 2023

Crossrefs

Cf. A360515, A360516, A360517. The odd index terms are A113583.

Sequence in context: A069507 A219894 A203464 * A358446 A152284 A109717

Adjacent sequences: A360511 A360512 A360513 * A360515 A360516 A360517

Keyword

nonn

Author

N. J. A. Sloane, Feb 27 2023

Extensions

Terms a(11) and beyond from Andrew Howroyd, Feb 27 2023

a(0) prepended by Ira M. Gessel, Feb 23 2026

Status

approved