A106512 -id:A106512 - cp's OEIS frontend

A092297 Number of ways of 3-coloring an annulus consisting of n zones joined like a pearl necklace.

0, 6, 6, 18, 30, 66, 126, 258, 510, 1026, 2046, 4098, 8190, 16386, 32766, 65538, 131070, 262146, 524286, 1048578, 2097150, 4194306, 8388606, 16777218, 33554430, 67108866, 134217726, 268435458, 536870910, 1073741826, 2147483646

Offset: 1

S. B. Step (stepy(AT)vesta.ocn.ne.jp), Feb 06 2004

A circular domain means a domain between two concentric circles and it is divided into n parts by n boundary lines perpendicular to the circles. Both sides of a line must have different colors. How many ways of coloring are there?
a(n) is also the multiple of six that's nearest to 2^n. - David Eppstein, Aug 31 2010
a(n) apparently is the trace of the n-th power of the adjacency matrix of the complete 3-graph, a 3 X 3 matrix with diagonal elements all zero and off-diagonal all ones (cf. A001045). If so, a(n) is the number of closed walks on the graph of length n. - Tom Copeland, Nov 06 2012
For n >= 2, a(n) is the number of length n words on 3 letters with no two consecutive like letters including the first and the last. Cf. A218034. - Geoffrey Critzer, Apr 05 2014

			a(2)=6 because we can color one zone in 3 colors and the other in 2, so 2*3=6 in all.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
K. Böhmová, C. Dalfó, and C. Huemer, On cyclic Kautz digraphs, Preprint 2016.
Cristina Dalfó, From subKautz digraphs to cyclic Kautz digraphs, arXiv:1709.01882 [math.CO], 2017.
Cristina Dalfó, The spectra of subKautz and cyclic Kautz digraphs, Linear Algebra and its Applications, 531 (2017), p. 210-219.
Fern Gossow, Lyndon-like cyclic sieving and Gauss congruence, arXiv:2410.05678 [math.CO], 2024. See p. 25.
Paul P. Martin and Siti Fatimah Zakaria, Zeros of the 4-state Potts model partition function for the square lattice revisited, J. Stat. Mech. 084003 (2019). eq. (7).
Carlos I. Perez-Sanchez, The Spectral Action on quivers, arXiv:2401.03705 [math.RT], 2024.
Index entries for linear recurrences with constant coefficients, signature (1,2).

Column k=3 of A106512.

Cf. A001045.

[2^n+2*(-1)^n : n in [1..40]]; // Vincenzo Librandi, Sep 27 2011

nn=28;Drop[CoefficientList[Series[6x^2/(1+x)^2/(1-3x/(1+x)),{x,0,nn}],x],1] (* Geoffrey Critzer, Apr 05 2014 *)
a[ n_] := 2 (2^(n - 1) + (-1)^n); (* Michael Somos, Oct 25 2014 *)
a[ n_] := If[ n < 1, -(-2)^(n - 1) a[2 - n] , (-1)^n HypergeometricPFQ[ Table[ -2, {k, n}], Table[ 1, {k, n - 1}], 1]] (* Michael Somos, Oct 25 2014 *)
LinearRecurrence[{1,2},{0,6},40] (* Harvey P. Dale, May 21 2024 *)

{a(n) = 2 * (2^(n-1) - (-1)^n)}; /* Michael Somos, Oct 25 2014 */

a(n) = 2^n + 2*(-1)^n; recurrence a(1)=0, a(2)=6, a(n) = 2*a(n-2) + a(n-1).
O.g.f: -6*x^2/((1+x)*(2*x-1)) = -3 - 1/(2*x-1) + 2/(1+x). - R. J. Mathar, Dec 02 2007
a(n) = 6*A001045(n-1). - R. J. Mathar, Aug 30 2008
a(n) = (-1)^n * a(2-n) * 2^(n-1) for all n in Z. - Michael Somos, Oct 25 2014

A208544 T(n,k) = Number of n-bead necklaces of k colors allowing reversal, with no adjacent beads having the same color.

Original entry on oeis.org

1, 2, 0, 3, 1, 0, 4, 3, 0, 0, 5, 6, 1, 1, 0, 6, 10, 4, 6, 0, 0, 7, 15, 10, 21, 3, 1, 0, 8, 21, 20, 55, 24, 13, 0, 0, 9, 28, 35, 120, 102, 92, 9, 1, 0, 10, 36, 56, 231, 312, 430, 156, 30, 0, 0, 11, 45, 84, 406, 777, 1505, 1170, 498, 29, 1, 0, 12, 55, 120, 666, 1680, 4291, 5580, 4435

Offset: 1

R. H. Hardin, Feb 27 2012

Table starts
.1.2..3...4....5.....6......7......8.......9......10......11.......12.......13
.0.1..3...6...10....15.....21.....28......36......45......55.......66.......78
.0.0..1...4...10....20.....35.....56......84.....120.....165......220......286
.0.1..6..21...55...120....231....406.....666....1035....1540.....2211.....3081
.0.0..3..24..102...312....777...1680....3276....5904....9999....16104....24882
.0.1.13..92..430..1505...4291..10528...23052...46185...86185...151756...254618
.0.0..9.156.1170..5580..19995..58824..149796..341640..714285..1391940..2559414
.0.1.30.498.4435.25395.107331.365260.1058058.2707245.6278140.13442286.26942565

			All solutions for n=7, k=3:
..1....1....1....1....1....1....1....1....1
..2....2....2....2....2....2....2....2....2
..3....3....1....1....3....1....3....1....3
..1....1....2....2....1....2....2....3....2
..2....3....3....3....3....1....3....1....3
..3....1....1....2....2....2....2....2....1
..2....3....3....3....3....3....3....3....3

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 264 terms from R. H. Hardin)

Cf. A081720, A208535, A106512.
Main diagonal is A208538.
Columns 3..7 are A208539, A208540, A208541, A208542, A208543.
Row 2 is A000217(n-1).
Row 3 is A000292(n-2).
Row 4 is A002817(n-1).
Row 5 is A164938(n-1).
Row 6 is A027670(n-1).

T[n_, k_] := If[n == 1, k, (DivisorSum[n, EulerPhi[n/#]*(k-1)^#&]/n + If[ OddQ[n], 1-k, k*(k-1)^(n/2)/2])/2]; Table[T[n-k+1, k], {n, 1, 12}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Oct 30 2017, after Andrew Howroyd *)

T(n, k) = if(n==1, k, (sumdiv(n, d, eulerphi(n/d)*(k-1)^d)/n + if(n%2, 1-k, k*(k-1)^(n/2)/2))/2);
for(n=1, 10, for(k=1, 10, print1(T(n, k), ", ")); print) \\ Andrew Howroyd, Oct 14 2017

T(2n+1,k) = A208535(2n+1,k)/2 for n > 0, T(2n,k) = (A208535(2n,k) + (k*(k-1)^n)/2)/2. - Andrew Howroyd, Mar 12 2017
Empirical for row n:
n=1: a(k) = k
n=2: a(k) = (1/2)*k^2 - (1/2)*k
n=3: a(k) = (1/6)*k^3 - (1/2)*k^2 + (1/3)*k
n=4: a(k) = (1/8)*k^4 - (1/4)*k^3 + (3/8)*k^2 - (1/4)*k
n=5: a(k) = (1/10)*k^5 - (1/2)*k^4 + k^3 - k^2 + (2/5)*k
n=6: a(k) = (1/12)*k^6 - (1/2)*k^5 + (3/2)*k^4 - (7/3)*k^3 + (23/12)*k^2 - (2/3)*k
n=7: a(k) = (1/14)*k^7 - (1/2)*k^6 + (3/2)*k^5 - (5/2)*k^4 + (5/2)*k^3 - (3/2)*k^2 + (3/7)*k

A287376 Array read by antidiagonals: T(m,n) = number of independent vertex sets in the complete prism graph K_m X C_n.

Original entry on oeis.org

1, 3, 1, 4, 7, 1, 7, 13, 13, 1, 11, 35, 34, 21, 1, 18, 81, 121, 73, 31, 1, 29, 199, 391, 325, 136, 43, 1, 47, 477, 1300, 1361, 731, 229, 57, 1, 76, 1155, 4285, 5781, 3771, 1447, 358, 73, 1, 123, 2785, 14161, 24473, 19606, 8881, 2605, 529, 91, 1

Offset: 1

Andrew Howroyd, May 23 2017

Equivalently, the number of 0..m words of length n with cyclically adjacent letters unequal with the exception that 0's may be adjacent.

			Table starts:
====================================================
m\n| 1  2   3    4     5      6       7        8
---|------------------------------------------------
1  | 1  3   4    7    11     18      29       47 ...
2  | 1  7  13   35    81    199     477     1155 ...
3  | 1 13  34  121   391   1300    4285    14161 ...
4  | 1 21  73  325  1361   5781   24473   103685 ...
5  | 1 31 136  731  3771  19606  101781   528531 ...
6  | 1 43 229 1447  8881  54763  337429  2079367 ...
7  | 1 57 358 2605 18551 132504  946037  6754805 ...
8  | 1 73 529 4361 35361 287305 2333745 18957321 ...
...

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

Rows 2-7 are A051927, A051928, A051929, A051930, A051931, A051932.

Cf. A135597 (K_m X P_n), A106512, A175243.

max = 10; row[m_] := ((m+1) - (m^2 - 2)*x - (2*m - 1)*x^2)/(1 - (m-1)*x - (m+1)*x^2 - x^3) + O[x]^(max+1) // CoefficientList[#, x]& // Rest;
T = Table[row[m], {m, 1, max}];
Table[T[[m-n+1, n]], {m, 1, max}, {n, m, 1, -1}] // Flatten (* Jean-François Alcover, Jun 06 2017 *)

RowGf(m,x)=((m+1)-(m^2-2)*x-(2*m-1)*x^2)/(1-(m-1)*x-(m+1)*x^2-x^3);
for (m=1,8,for(n=1,8,print1(Vec(RowGf(m,x)+O(x^(n+1)))[n+1], " "));print);

Row g.f.: ((m+1)-(m^2-2)*x-(2*m-1)*x^2)/(1-(m-1)*x-(m+1)*x^2-x^3).

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

A226493 Closed walks of length n in K_4 graph.

Original entry on oeis.org

0, 12, 24, 84, 240, 732, 2184, 6564, 19680, 59052, 177144, 531444, 1594320, 4782972, 14348904, 43046724, 129140160, 387420492, 1162261464, 3486784404, 10460353200, 31381059612, 94143178824, 282429536484, 847288609440, 2541865828332, 7625597484984, 22876792454964

Offset: 1

Gustavo Gordillo, Jun 09 2013

Essentially the same as A218034.

Mike Krebs and Tony Shaheen, Expander Families and Cayley Graphs, Oxford University Press, Inc. 2011

K. Böhmová, C. Dalfó, and C. Huemer, On cyclic Kautz digraphs, Preprint 2016.
Cristina Dalfó, From subKautz digraphs to cyclic Kautz digraphs, arXiv:1709.01882 [math.CO], 2017.
C. Dalfó, The spectra of subKautz and cyclic Kautz digraphs, Linear Algebra and its Applications, 531 (2017), p. 210-219.
Carlos I. Perez-Sanchez, The Spectral Action on quivers, arXiv:2401.03705 [math.RT], 2024.
Index entries for linear recurrences with constant coefficients, signature (2,3).

Column k=4 of A106512.

Cf. A218034.

Mathematica
```
Table[3 (-1)^k + 3^k, {k, 30}]
```

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

a(n) = 3*(-1)^n + 3^n = 12*A015518(n-1).

G.f.: 12*x^2 / ( (1+x)*(1-3*x) ). - R. J. Mathar, Jun 29 2013

cp's OEIS Frontend

A092297 Number of ways of 3-coloring an annulus consisting of n zones joined like a pearl necklace.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A208544 T(n,k) = Number of n-bead necklaces of k colors allowing reversal, with no adjacent beads having the same color.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A287376 Array read by antidiagonals: T(m,n) = number of independent vertex sets in the complete prism graph K_m X C_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A226493 Closed walks of length n in K_4 graph.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula