A309380 Number of unordered pairs of 5-colorings of an n-wheel that differ in the coloring of exactly one vertex.

180, 240, 1380, 4200, 15420, 52080, 177780, 595320, 1978860, 6515520, 21298980, 69168840, 223369500, 717772560, 2296480980, 7319252760, 23247851340, 73615135200, 232462779780, 732245695080, 2301319648380, 7217727595440, 22594530691380, 70607719663800

Offset

3,1

Comments

The n-wheel graph is defined for n >= 4. The value of a(3) was computed using the complete graph on 3 vertices.

Links

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

Prateek Bhakta, Benjamin Brett Buckner, Lauren Farquhar, Vikram Kamat, Sara Krehbiel, Heather M. Russell, Cut-Colorings in Coloring Graphs, Graphs and Combinatorics, (2019) 35(1), 239-248.

Luis Cereceda, Janvan den Heuvel, Matthew Johnson, Connectedness of the graph of vertex-colourings, Discrete Mathematics, (2008) 308(5-6), 913-919.

Aalok Sathe, Coloring Graphs Library

Wikipedia, Wheel graph

Index entries for linear recurrences with constant coefficients, signature (6,-6,-16,15,18).

Formula

From Andrew Howroyd, Sep 10 2019: (Start)

a(n) = 10*(2^(n-1) - 2*(-1)^n + (n-1)*(3^(n-2) - 3*(-1)^n)).

a(n) = 10*A092297(n-1) + 5*A326347(n-1).

a(n) = binomial(k, 2)*A106512(n-1, k-2) + k*(n-1)*(binomial(k-2, 2)*A106512(n-3, k-1) + binomial(k-3, 2)*A106512(n-2, k-1)) where k = 5.

a(n) = 6*a(n-1) - 6*a(n-2) - 16*a(n-3) + 15*a(n-4) + 18*a(n-5) for n > 7.

G.f.: 60*x^3*(3 - 14*x + 17*x^2 + 4*x^3 - 6*x^4)/((1 + x)^2*(1 - 2*x)*(1 - 3*x)^2).

(End)

Prog

(PARI) a(n) = {10*(2^(n-1) - 2*(-1)^n + (n-1)*(3^(n-2) - 3*(-1)^n))} \\ Andrew Howroyd, Sep 10 2019
(PARI) Vec(60*(3 - 14*x + 17*x^2 + 4*x^3 - 6*x^4)/((1 + x)^2*(1 - 2*x)*(1 - 3*x)^2) + O(x^30)) \\ Andrew Howroyd, Sep 10 2019

Crossrefs

Cf. A092297, A106512, A309379 (similar sequence with 4 colors), A090860 (4-colorings), A309315 (5-colorings), A326347 (on n-cycle).

Sequence in context: A329189 A364976 A289056 * A030636 A378430 A350372

Adjacent sequences: A309377 A309378 A309379 * A309381 A309382 A309383

Keyword

nonn

Author

Aalok Sathe, Jul 26 2019

Extensions

Terms a(12) and beyond from Andrew Howroyd, Sep 10 2019

Status

approved