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

%I #17 Feb 28 2023 13:44:59

%S 1,2,6,18,80,370,2352,14434,117504,902178,8983040,82751218,973639680,

%T 10464269842,142066391040,1744984627650,26849099841536,

%U 371007716472130,6380079728689152,97957282718195410,1861853565120675840,31444800527373324210,654585210392831590400

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

%C 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

%H Andrew Howroyd, <a href="/A360516/b360516.txt">Table of n, a(n) for n = 1..200</a>

%H I. Bouwer and Z. Star, <a href="https://www.jstor.org/stable/2323065">A question of protocol</a>, The American mathematical monthly, 95.2 (1988): 118-121. See P(n).

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PathGraph.html">Path Graph</a>.

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

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

%e From _Andrew Howroyd_, Feb 28 2023: (Start)

%e For n <= 3, a(n) = n! since any ordering of the vertices produces a 2-coloring.

%e 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.

%e (End)

%o (PARI) \\ Needs A360514seq from A360514.

%o 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

%Y Cf. A360514, A360515, A360517.

%K nonn

%O 1,2

%A _N. J. A. Sloane_, Feb 27 2023

%E Terms a(11) and beyond from _Andrew Howroyd_, Feb 27 2023