OFFSET
1,2
COMMENTS
a(n) is the number of orderings of the vertices that a greedy coloring algorithm will properly 2-color the n-path graph. If the colors are positive integers, the greedy algorithm always assigns the least color that is distinct from those of already assigned neighbors. - Andrew Howroyd, Feb 28 2023
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..200
I. Bouwer and Z. Star, A question of protocol, The American mathematical monthly, 95.2 (1988): 118-121. See P(n).
Eric Weisstein's World of Mathematics, Path Graph.
FORMULA
EXAMPLE
From Andrew Howroyd, Feb 28 2023: (Start)
For n <= 3, a(n) = n! since any ordering of the vertices produces a 2-coloring.
a(4) = 4! - 6 = 18. The 6 orderings that produce a 3-coloring are those that start with one of the end vertices followed by the other end vertex and those that start with an end vertex, then its neighbor and then the other end vertex. The 6 orderings are: 1423, 1432, 4123, 4132, 1243, 4312.
(End)
PROG
(PARI) \\ Needs A360514seq from A360514.
seq(n) = {my(v=A360514seq(n)); vector(#v, n, if(n%2, if(n==1, 1, (n-1)*n*v[n-2]), 2*v[n]))} \\ Andrew Howroyd, Feb 27 2023
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Feb 27 2023
EXTENSIONS
Terms a(11) and beyond from Andrew Howroyd, Feb 27 2023
STATUS
approved