A360516 Number of 2-color vertex orderings of the labeled path graph on n vertices.

1, 2, 6, 18, 80, 370, 2352, 14434, 117504, 902178, 8983040, 82751218, 973639680, 10464269842, 142066391040, 1744984627650, 26849099841536, 371007716472130, 6380079728689152, 97957282718195410, 1861853565120675840, 31444800527373324210, 654585210392831590400

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

a(n) = A360514(n) + A360515(n).

a(2*n) = 2*A360514(2*n); a(2*n+1) = 2*n*(2*n + 1)*A360514(2*n - 1) for n >= 1.

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

Cf. A360514, A360515, A360517.

Sequence in context: A141580 A007869 A263915 * A144557 A327729 A273001

Adjacent sequences: A360513 A360514 A360515 * A360517 A360518 A360519

Keyword

nonn

Author

N. J. A. Sloane, Feb 27 2023

Extensions

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

Status

approved