A090860 -id:A090860 - cp's OEIS frontend

A106512 Array read by antidiagonals: a(n,k) = number of k-colorings of a circle of n nodes (n >= 1, k >= 1).

0, 0, 0, 0, 2, 0, 0, 6, 0, 0, 0, 12, 6, 2, 0, 0, 20, 24, 18, 0, 0, 0, 30, 60, 84, 30, 2, 0, 0, 42, 120, 260, 240, 66, 0, 0, 0, 56, 210, 630, 1020, 732, 126, 2, 0, 0, 72, 336, 1302, 3120, 4100, 2184, 258, 0, 0, 0, 90, 504, 2408, 7770, 15630, 16380, 6564, 510, 2, 0, 0, 110

Offset: 1

Joshua Zucker, May 29 2005

Note that we keep one edge in the circular graph even when there's only one node (so there are 0 colorings of one node with k colors).

Number of closed walks of length n on the complete graph K_{k}. - Andrew Howroyd, Mar 12 2017

			From _Andrew Howroyd_, Mar 12 2017: (Start)
Table begins:
  0 0   0     0      0       0        0        0         0 ...
  0 2   6    12     20      30       42       56        72 ...
  0 0   6    24     60     120      210      336       504 ...
  0 2  18    84    260     630     1302     2408      4104 ...
  0 0  30   240   1020    3120     7770    16800     32760 ...
  0 2  66   732   4100   15630    46662   117656    262152 ...
  0 0 126  2184  16380   78120   279930   823536   2097144 ...
  0 2 258  6564  65540  390630  1679622  5764808  16777224 ...
  0 0 510 19680 262140 1953120 10077690 40353600 134217720 ...
(End)
a(4,3) = 18 because there are three choices for the first node's color (call it 1) and then two choices for the second node's color (call it 2) and then the remaining two nodes can be 12, 13, or 32. So in total there are 3*2*3 = 18 ways. a(3,4) = 4*3*2 = 24 because the three nodes must be three distinct colors.

Andrew Howroyd, Table of n, a(n) for n = 1..1274

Columns include A092297, A226493. Main diagonal is A118537.
Rows 2-7 are A002378, A007531, A091940, A061167, A131472, A133499.
Cf. A090860, A208535.

a(n, k) = (k-1)^n + (-1)^n * (k-1).

a(67) corrected by Andrew Howroyd, Mar 12 2017

A309315 Number of 5-colorings of an n-wheel graph.

Original entry on oeis.org

60, 120, 420, 1200, 3660, 10920, 32820, 98400, 295260, 885720, 2657220, 7971600, 23914860, 71744520, 215233620, 645700800, 1937102460, 5811307320, 17433922020, 52301766000, 156905298060, 470715894120, 1412147682420, 4236443047200, 12709329141660

Offset: 3

Aalok Sathe, Jul 23 2019

Cf. A010677 (for 3-colorings), A090860 (for 4-colorings).

Colin Barker, Table of n, a(n) for n = 3..1000
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.
Eric Weisstein's World of Mathematics, Wheel Graph
Wikipedia, Chromatic polynomial
Wikipedia, Wheel graph
Index entries for linear recurrences with constant coefficients, signature (2,3).

Cf. A010677, A090860.

Vec(60*x^3 / ((1 + x)*(1 - 3*x)) + O(x^30)) \\ Colin Barker, Jul 24 2019

a(n) = 5*3^(n-1)-15*(-1)^n.
From Colin Barker, Jul 24 2019: (Start)
G.f.: 60*x^3 / ((1 + x)*(1 - 3*x)).
a(n) = 2*a(n-1) + 3*a(n-2) for n>4.
(End)

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

Original entry on oeis.org

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

Aalok Sathe, Jul 26 2019

nonn

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

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).

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

a(n) = {10*(2^(n-1) - 2*(-1)^n + (n-1)*(3^(n-2) - 3*(-1)^n))} \\ Andrew Howroyd, Sep 10 2019

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

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)

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

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

Original entry on oeis.org

36, 0, 108, 120, 444, 840, 2124, 4536, 10332, 22440, 49260, 106392, 229500, 491400, 1048716, 2228088, 4718748, 9961320, 20971692, 44040024, 92274876, 192937800, 402653388, 838860600, 1744830684, 3623878440, 7516193004, 15569256216, 32212254972, 66571992840

Offset: 3

Aalok Sathe, Jul 26 2019

nonn

Please refer to the Wikipedia page on n-wheel graphs linked here; an n-wheel graph has n-1 peripheral nodes and one central node, thus having n total nodes.

			From _Andrew Howroyd_, Aug 27 2019: (Start)
Case n=4: The 4-wheel graph is isomorphic to the complete graph on 4 vertices. Each vertex must be colored differently and it is not possible to change the color of just one vertex and still leave a valid coloring, so a(4) = 0.
Case n=5: The peripheral nodes can colored using one of the patterns 1212, 1213 or 1232. In the case of 1212, colors can be selected in 24 ways and any vertex including the center vertex can be flipped to the unused color giving 24*5 = 120. In the case of 1213 or 1232, colors can be selected in 24 ways and two vertices can have a color change giving 24*2*2 = 96. Since we are counting unordered pairs, a(5) = (120 + 96)/2 = 108.
(End)

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
Aalok Sathe, iPython notebook to generate terms of this sequence
Wikipedia, Wheel graph

Cf. A090860 (number of 4-colorings), A309315 (number of 5-colorings), A309380.

Vec(12*(3 - 9*x + 6*x^2 + 4*x^3 - 2*x^4)/((1 - x)*(1 + x)^2*(1 - 2*x)^2) + O(x^30)) \\ Andrew Howroyd, Aug 27 2019

G.f.: 12*x^3*(3 - 9*x + 6*x^2 + 4*x^3 - 2*x^4)/((1 - x)*(1 + x)^2*(1 - 2*x)^2). - Andrew Howroyd, Aug 27 2019

Terms a(14) and beyond from Andrew Howroyd, Aug 27 2019

cp's OEIS Frontend

A106512 Array read by antidiagonals: a(n,k) = number of k-colorings of a circle of n nodes (n >= 1, k >= 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A309315 Number of 5-colorings of an n-wheel graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions