A090860 -id:A090860

Search: a090860 -id:a090860

Displaying 1-4 of 4 results found.

page 1

A106512

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

+10
6

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,5

COMMENTS

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

LINKS

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

FORMULA

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

EXAMPLE

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.

CROSSREFS

Columns include A092297, A226493. Main diagonal is A118537.

Rows 2-7 are A002378, A007531, A091940, A061167, A131472, A133499.

Cf. A090860, A208535.

KEYWORD

nonn,tabl

AUTHOR

Joshua Zucker, May 29 2005

EXTENSIONS

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

STATUS

approved

A309315

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

+10
3

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

3,1

COMMENTS

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

LINKS

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

FORMULA

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)

PROG

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

CROSSREFS

Cf. A010677, A090860.

KEYWORD

nonn,easy

AUTHOR

Aalok Sathe, Jul 23 2019

STATUS

approved

A309380

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

+10
3

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

(list; graph; refs; listen; history; text; internal format)

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

KEYWORD

nonn

AUTHOR

Aalok Sathe, Jul 26 2019

EXTENSIONS

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

STATUS

approved

A309379

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

+10
2

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

3,1

COMMENTS

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.

LINKS

Table of n, a(n) for n=3..32.

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

FORMULA

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

EXAMPLE

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)

PROG

(PARI) 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

CROSSREFS

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

KEYWORD

nonn

AUTHOR

Aalok Sathe, Jul 26 2019

EXTENSIONS

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

STATUS

approved

page 1

Search completed in 0.006 seconds