A092297 -id:A092297 - cp's OEIS frontend

A007040 Number of (marked) cyclic n-bit binary strings containing no runs of length > 2.

2, 2, 6, 6, 10, 20, 28, 46, 78, 122, 198, 324, 520, 842, 1366, 2206, 3570, 5780, 9348, 15126, 24478, 39602, 64078, 103684, 167760, 271442, 439206, 710646, 1149850, 1860500, 3010348, 4870846, 7881198, 12752042, 20633238, 33385284, 54018520

Offset: 1

N. J. A. Sloane

For n >= 3, also the number of maximal independent vertex sets (and minimal vertex covers) in the n-prism graph. - Eric W. Weisstein, Mar 30 and Aug 07 2017
From Petros Hadjicostas, Jul 08 2018: (Start)
Let q and m be positive integers. We denote by f1(m,q,n) the number of (marked) cyclic q-ary strings of length n that contain no runs of lengths > m when no wrapping around is allowed, and by f2(m,q,n) when wrapping around is allowed.
It is clear that f1(m,q,n) = f2(m,q,n) for n > m, but f1(m,q,n) = q^n and f2(m,q,n) = q^n - q when 1 <= n <= m.
Burstein and Wilf (1997) and Edlin and Zeilberger (2000) considered f1(m,q,n) while Hadjicostas and Zhang considered f2(m,q,n).
Let g(m, q, x) = (m+1-m*q*x)/(1-q*x+(q-1)*x^(m+1)) - (m+1)/(1-x^(m+1)).
By generalizing Moser (1991, 1993), Burstein and Wilf (1997) proved that the g.f. of the numbers f1(m,q,n) is F1(m,q,x) = ((1-x^m)/(1-x))*(q*x + (q-1)*x* g(m, q, x)).
Using the above formula by Burstein and Wilf (1997), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f2(m,q,n) is F2(m,q,x) = ((q-1)*x*(1-x^m)/(1-x))*g(m, q, x).
A necklace is an unmarked cyclic string. If f3(m,q,n) is the number of q-ary necklaces of length n with no runs of length > m (and wrapping around is allowed), then f3(m,q,n) = (1/n)*Sum_{d|n} phi(n/d)*f2(m,q,d), where phi(.) is Euler's totient function. Using this formula and F2(m,q,x), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f3(m,q,n) is given by F3(m,q,x) = -(q-1)*x*(1-x^m)/((1-x)*(1-x^(m+1))) - Sum_{s>=1} (phi(s)/s)*log(1 - (q-1)*(x^s - x^(s*(m+1)))/(1-x^s)).
For the current sequence, we have q = 2 and m = 2. We have a(n) = f1(m=2, q=2, n) = f2(m=2, q=2, n) for n >= 3, but for a(1) and a(2) it is unclear what approach the author of the sequence is following. He has a(1) = q^1 = 2, but a(2) = q^2 - q = 2^2 - 2 = 2. (Note that, for q = m = 2, we have f1(m=2, q=2, 1) = 2, f1(m=2, q=2, 2) = 4, f2(m=2, q=2, 1) = 0, and f2(m=2, q=2, 2) = 2.)
If A(x) is the g.f. of the current sequence, we have A(x) = F1(m=2,q=2, x) - 2*x^2 = F2(m=2, q=2, x) + 2*x.
When m = 1 and q = 3, we have f1(m=1, q=3, n) = number of marked cyclic words on three letters with no two consecutive like letters. We have f1(m=1, q=3, n) = A092297(n) for n >= 2. This was first stated in the comments of that sequence by G. Critzer.
When m = 1 and q = 4, we have f1(m=1, q=4, n) = number of marked cyclic words on four letters with no two consecutive like letters. We have f1(m=1, q=4, n) = A218034(n) for n >= 1. This was first stated in the comments of that sequence by J. Arndt.
A generalization of the above formula by Burstein and Wilf (1997) was given by Taylor (2014) in Section 5 of his paper. (End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Z. Agur, A. S. Fraenkel, and S. T. Klein, The number of fixed points of the majority rule, Discr. Math., 70 (1988), 295-302.
A. Burstein and H. S. Wilf, On cyclic strings without long constant blocks, Fibonacci Quarterly, 35 (1997), 240-247.
A. E. Edlin and D. Zeilberger, The Goulden-Jackson cluster method for cyclic words, Adv. Appl. Math., 25 (2000), 228-232.
W. Florek, A class of generalized Tribonacci sequences applied to counting problems, Appl. Math. Comput., 338 (2018), 809-821.
Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
Matthew Macauley, Jon McCammond, and Henning S. Mortveit, Dynamics groups of asynchronous cellular automata, Journal of Algebraic Combinatorics, 33(1) (2011), 11-35.
A. McLeod and W. O. J. Moser, Counting cyclic binary strings, Math. Mag., 80(1) (2007), 29-37.
W. O. J. Moser, On cyclic binary n-bit strings, Report from the Department of Mathematics and Statistics, McGill University, 1991. (Annotated scanned copy)
W. O. J. Moser, Cyclic binary strings without long runs of like (alternating) bits, Fibonacci Quart. 31(1) (1993), 2-6.
Noriaki Sannomiya, Hosho Katsura, and Yu Nakayama, Supersymmetry breaking and Nambu-Goldstone fermions with cubic dispersion, arXiv:1612.02285 [cond-mat.str-el], 2016. See Table I, line 2.
Jair Taylor, Counting Words with Laguerre Series, Electron. J. Combin., 21 (2014), P2.1.
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set.
Eric Weisstein's World of Mathematics, Minimal Vertex Cover.
Eric Weisstein's World of Mathematics, Prism Graph.
Index entries for linear recurrences with constant coefficients, signature (0,1,2,1).

Cf. A000032, A007039, A316660.

Join[{2}, LinearRecurrence[{0, 1, 2, 1}, {2, 6, 6, 10}, 40]] (* Harvey P. Dale, Nov 09 2011 *)
Join[{2}, Table[n Sum[Binomial[2 k, n - 2 k]/k, {k, n}], {n, 2, 40}]] (* Harvey P. Dale, Nov 09 2011 *)
Table[LucasL[n] + 2 Cos[2 n Pi/3], {n, 20}] (* Eric W. Weisstein, Mar 30 2017 *)

a(n)=if(n<3,2,([0,1,0,0; 0,0,1,0; 0,0,0,1; 1,2,1,0]^(n-2)*[2;6;6;10])[1,1]) \\ Charles R Greathouse IV, Jun 15 2015

a(n) = a(n-2) + 2*a(n-3) + a(n-4), n >= 7. - David W. Wilson
a(n) = n*Sum_{k=1..n} binomial(2*k, n-2*k)/k for n > 1 with a(0) = 0 and a(1) = 2. - Vladimir Kruchinin, Oct 12 2011
G.f.: 2*x*(1 + x + 2*x^2 - x^4)/((1 - x - x^2)*(1 + x + x^2)). - Colin Barker, Mar 15 2012
a(n) = A000032(n) + 2*cos(2*Pi*n/3) for n > 1. - Eric W. Weisstein, Mar 30 2017
a(n) = 2*A100886(n-1), n > 1. - R. J. Mathar, Jan 20 2018
a(n) = A000032(n) - A061347(n) for n > 1. - Wojciech Florek, Feb 18 2018

Name clarified by Petros Hadjicostas, Jul 08 2018

A218034 Number of ways to seat 4 types of people in n labeled seats around a circle such that no two adjacent people are of the same type.

Original entry on oeis.org

1, 4, 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: 0

Amritpal Singh, Oct 19 2012

Number of length-n words with 4 letters and no two adjacent identical letters (including, for n >= 2, the first and last letter). - Joerg Arndt, Oct 21 2012
a(n), for n > 1, apparently is the trace of the n-th power of the adjacency matrix of the complete 4-graph, a 4 X 4 matrix with diagonal elements all zeros and off-diagonal all ones (cf. A054878). - Tom Copeland, Nov 06 2012
The corrected formula by Geoffrey Critzer below (for a general k) is a special case of Theorem 2 in Burstein and Wilf (1997). See also Edlin and Zeilberger (2000), Corollary 5.5 in Taylor (2014), and Section 5 in Hadjicostas and Zhang (2018). - Petros Hadjicostas, Jul 09 2018

K. Böhmová, C. Dalfó, C. Huemer, On cyclic Kautz digraphs, Preprint 2016.
A. Burstein and H. S. Wilf, On cyclic strings without long constant blocks, Fibonacci Quarterly, 35 (1997), 240-247.
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), pp. 210-219.
A. E. Edlin and D. Zeilberger, The Goulden-Jackson cluster method for cyclic words, Adv. Appl. Math., 25 (2000), 228-232.
Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
Jair Taylor, Counting Words with Laguerre Series, Electron. J. Combin., 21 (2014), P2.1.
Index entries for linear recurrences with constant coefficients, signature (2,3).

Cf. A092297.

nn=28; CoefficientList[Series[1+4x +12x^2/(1+x)^2/(1-4x/(1+x)),{x,0,nn}],x] (* Geoffrey Critzer, Apr 05 2014 *)

a[0]:1$ a[1]:4$ a[n]:=3^n + 3*(-1)^n$ makelist(a[n],n,0,40); /* Martin Ettl, Oct 21 2012 */

a(n) = if( n<2, [1,4][n+1], 3^n + 3*(-1)^n ); /* Joerg Arndt, Oct 21 2012 */

a(0) = 1, a(1) = 4, a(n) = 3^n + 3*(-1)^n for n >= 2.
a(n) = 4 * A054878(n) for n >= 2. - Joerg Arndt, Oct 21 2012
G.f.: (1 + 2*x + x^2 - 12*x^3)/((1 + x)*(1 - 3*x)). - Colin Barker, Oct 22 2012
Generally for such words on k letters, g.f.: 1 + k*x + (k^2-k)*x^2/(1 + x)^2/(1 - k*x/(1 + x)). - Geoffrey Critzer, Apr 05 2014 [Corrected by Petros Hadjicostas, Jul 08 2018]
a(n+m) = a(n)*a(m)/4 + a(n+1)*a(m+1)/12. - Yuchun Ji, Sep 12 2017

a(0) = 1 prepended and more terms added by Joerg Arndt, Oct 21 2012

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

Original entry on oeis.org

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

A090860 Number of ways of 4-coloring a map in which there is a central circle surrounded by an annulus divided into n-1 regions. There are n regions in all.

Original entry on oeis.org

24, 72, 120, 264, 504, 1032, 2040, 4104, 8184, 16392, 32760, 65544, 131064, 262152, 524280, 1048584, 2097144, 4194312, 8388600, 16777224, 33554424, 67108872, 134217720, 268435464, 536870904, 1073741832, 2147483640, 4294967304

Offset: 4

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

nonn

The number of ways of m-coloring an annulus consisting of n zones joined like a pearl necklace is (m-1)^n + (-1)^n*(m-1), where m >= 3 (cf. A092297 for m=3). Now we must also color the central region.

			We can choose 4 colors to color the inside zone, therefore b(3)=6 because we can color one zone in the annulus in 3 colors, another in 2, the other in 1, so 3*2*1=6 in all and a(4)=4*6=24. We can also add a(3)=4*3*2=24 to this sequence.

Vincenzo Librandi, Table of n, a(n) for n = 4..3000
S. B. Step, More information.
Index entries for linear recurrences with constant coefficients, signature (1,2).

Cf. A001045, A092297.

[2^(n+1)-8*(-1)^n: n in [4..35]]; // Vincenzo Librandi, Oct 10 2011

LinearRecurrence[{1,2},{24,72},30] (* Harvey P. Dale, Jan 25 2020 *)

m=4, a(n)=m*((m-2)^(n-1)+(-1)^(n-1)*(m-2)); recurrence m=4, b(1)=0, b(2)=(m-1)*(m-2), b(n)=(m-2)*b(n-2)+(m-3)*b(n-1), a(n)=m*b(n-1).
O.g.f.: -24*x^3 - 12*x + 6 - 8/(1+x) - 2/(2*x-1). - R. J. Mathar, Dec 02 2007
a(n) = 24*A001045(n-2). - R. J. Mathar, Aug 30 2008
a(n) = 2^(n+1) - 8*(-1)^n. - Vincenzo Librandi, Oct 10 2011

A140360 Inverse binomial transform of A140359.

Original entry on oeis.org

1, 0, 5, -5, 15, -25, 55, -105, 215, -425, 855, -1705, 3415, -6825, 13655, -27305, 54615, -109225, 218455, -436905, 873815, -1747625, 3495255, -6990505, 13981015, -27962025, 55924055, -111848105, 223696215, -447392425, 894784855, -1789569705, 3579139415

Offset: 0

Paul Curtz, Jun 24 2008

sign

For p*Jacobsthal numbers A001045, p=2: A078008 (A001045 differences, they are companions) or 1, 2*A001045(n), also in A133494; p=3: A062510; p=4: see A097073; p=6: A092297.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (-1, 2).

a:= n-> `if`(n=0, 1, (<<0|1>, <2|-1>>^(n-1). <<0,5>>)[1,1]):
seq(a(n), n=0..30);  # Alois P. Heinz, Dec 28 2010

{1}~Join~Table[(-5 (-1 + (-2)^(n - 1)))/3, {n, 32}] (* or *)
CoefficientList[Series[(-3 x^2 - x - 1)/(2 x^2 - x - 1), {x, 0, 32}], x] (* Michael De Vlieger, Apr 15 2016 *)

G.f.: (-3*x^2-x-1) / (2*x^2-x-1).
a(n) = (-5*(-1 + (-2)^(n-1)))/3, for n>0. - Andres Cicuttin, Apr 15 2016
a(n) = 5 - 2*a(n-1),  for n>2. - Andres Cicuttin, Apr 15 2016

More terms from Alois P. Heinz, Dec 28 2010

A106365 Number of necklaces with n beads of 3 colors, no 2 adjacent beads the same color.

Original entry on oeis.org

3, 3, 2, 6, 6, 14, 18, 36, 58, 108, 186, 352, 630, 1182, 2190, 4116, 7710, 14602, 27594, 52488, 99878, 190746, 364722, 699252, 1342182, 2581428, 4971066, 9587580, 18512790, 35792568, 69273666, 134219796, 260301174, 505294128, 981706830

Offset: 1

Christian G. Bower, Apr 29 2005

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..500
Petros Hadjicostas, Proof of an explicit formula for Bower's CycleBG transform
Index entries for sequences related to necklaces

Column 3 of A208535.

Cf. A000031, A001867.

a[n_] := If[n==1, 3, Sum[EulerPhi[n/d]*(2*(-1)^d+2^d), {d, Divisors[n]}]/n ];
Array[a, 35] (* Jean-François Alcover, Jul 06 2018, after Andrew Howroyd *)

a(n) = if(n==1, 3, sumdiv(n, d, eulerphi(n/d)*(2*(-1)^d + 2^d))/n); \\ Andrew Howroyd, Oct 14 2017

CycleBG transform of (3, 0, 0, 0, ...)
CycleBG transform T(A) = invMOEBIUS(invEULER(Carlitz(A)) + A(x^2) - A) + A.
Carlitz transform T(A(x)) has g.f. 1/(1-sum(k>0, (-1)^(k+1)*A(x^k))).
a(n) = (1/n)*sum_{d divides n} phi(n/d)*A092297(d) (n>1). - Seiichi Azuma, Oct 25 2014
a(n) = -1+(-1)^n+A000031(n) (n>1). - Seiichi Azuma, Oct 25 2014 [Corrected by Petros Hadjicostas, Feb 16 2018.]
From Petros Hadjicostas, Feb 16 2018: (Start)
General formula for the CycleBG transform: T(A)(x) = A(x) - Sum_{k>=0} A(x^(2k+1)) + Sum_{k>=1} (phi(k)/k)*log(Carlitz(A)(x^k)). For a proof, see the links above. (For this sequence, A(x) = 3*x.)
G.f.: Sum_{n>=1} a(n)*x^n = 3*x - 2*x/(1-x^2) - Sum_{n>=1} (phi(n)/n)*log(1-2*x^n) = 3*x - Sum_{n>=1} (phi(n)/n)*(2*log(1+x^n) + log(1-2*x^n)).
(End)

A171160 a(n) = a(n-1) + 2*a(n-2) with a(0)=3, a(1)=4.

Original entry on oeis.org

3, 4, 10, 18, 38, 74, 150, 298, 598, 1194, 2390, 4778, 9558, 19114, 38230, 76458, 152918, 305834, 611670, 1223338, 2446678, 4893354, 9786710, 19573418, 39146838, 78293674, 156587350, 313174698, 626349398, 1252698794, 2505397590, 5010795178, 10021590358

Offset: 0

Paul Curtz, Dec 04 2009

J. Mulder, Table of n, a(n) for n = 0..2999
Index entries for linear recurrences with constant coefficients, signature (1,2).

Cf. A001045, A078008, A175805.
Cf. A062510, A083582, (-1)^n*A140966.
Cf. A092297, A154879.
Cf. A062092, A083595.

f[n_]:=2/(n+1);x=5;Table[x=f[x];Numerator[x],{n,0,5!}] (* Vladimir Joseph Stephan Orlovsky, Mar 12 2010 *)
LinearRecurrence[{1,2},{3,4},40] (* Harvey P. Dale, Sep 04 2013 *)

Vec(-(x+3)/((x+1)*(2*x-1)) + O(x^100)) \\ Colin Barker, Feb 10 2015

a(n) = (1/3)*(2*(-1)^n + 7*2^n), with n>=0. - Paolo P. Lava, Dec 14 2009
G.f.: -(x+3) / ((x+1)*(2*x-1)). - Colin Barker, Feb 10 2015
From Paul Curtz, Jun 03 2022: (Start)
a(n) = A078008(n) + A078008(n+1) + A078008(n+2).
a(n) = 2^(n+1) + A078008(n).
a(n) = A001045(n+3) - A001045(n).
(a(n) + a(n+1) = a(n+2) - a(n) = A005009(n).)
a(n) + a(n+3) = A175805(n).
a(n) = A062510(n) + A083582(n-1) with A083582(-1) = 3.
a(n) = A092297(n) + A154879(n). (End)
a(n) = 2*A062092(n-1), for n>0; 2*a(n) = A083595(n+1). - Paul Curtz, Jun 08 2022

Edited by N. J. A. Sloane, Dec 05 2009
More terms from J. Mulder (jasper.mulder(AT)planet.nl), Jan 28 2010
More terms from Max Alekseyev, Apr 24 2010

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

A316660 Number of n-bit binary necklaces (unmarked cyclic n-bit binary strings) containing no runs of length > 2.

Original entry on oeis.org

0, 1, 2, 2, 2, 5, 4, 7, 10, 14, 18, 31, 40, 63, 94, 142, 210, 329, 492, 765, 1170, 1810, 2786, 4341, 6712, 10461, 16274, 25414, 39650, 62075, 97108, 152287, 238838, 375166, 589526, 927555, 1459960, 2300347, 3626242, 5721044, 9030450, 14264309, 22542396, 35646311, 56393862

Offset: 1

Petros Hadjicostas, Jul 09 2018

nonn

This is the "unmarked" version of sequence A007040. An unmarked cyclic string is a necklace. Notice that we define a(1) = 0 and a(2) = 1 because wrapping around the circle is allowed here (otherwise we would have to let a(1) = 2 and a(2) = 3).
Let q and m be positive integers. We denote by f1(m,q,n) the number of marked cyclic q-ary strings of length n that contain no runs of lengths > m when no wrapping around is allowed, and by f2(m,q,n) when wrapping around is allowed.
It is clear that f1(m,q,n) = f2(m,q,n) for n > m, but f1(m,q,n) = q^n and f2(m,q,n) = q^n - q when 1 <= n <= m.
Burstein and Wilf (1997) and Edlin and Zeilberger (2000) considered f1(m,q,n) while Hadjicostas and Zhang considered f2(m,q,n).
Let g(m, q, x) = (m+1-m*q*x)/(1-q*x+(q-1)*x^(m+1)) - (m+1)/(1-x^(m+1)).
By generalizing Moser (1993), Burstein and Wilf (1997) proved that the g.f. of the numbers f1(m,q,n) is F1(m,q,x) = ((1-x^m)/(1-x))*(q*x + (q-1)*x* g(m, q, x)).
Using the above formula by Burstein and Wilf (1997), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f2(m,q,n) is F2(m,q,x) = ((q-1)*x*(1-x^m)/(1-x))*g(m, q, x).
If f3(m,q,n) is the number of q-ary necklaces (= unmarked cyclic strings) of length n with no runs of length > m (and wrapping around is allowed), then f3(m,q,n) = (1/n)*Sum_{d|n} phi(n/d)*f2(m,q,d), where phi(.) is Euler's totient function. Using this formula and F2(m,q,x), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f3(m,q,n) is given by F3(m,q,x) = -(q-1)*x*(1-x^m)/((1-x)*(1-x^(m+1))) - Sum_{s>=1} (phi(s)/s)*log(1 - (q-1)*(x^s - x^(s*(m+1)))/(1-x^s)).
If A(x) is the g.f. of the current sequence (a(n): n >= 1), we have A(x) = F3(m=2, q=2, x). Also, a(n) = f3(m=2, q=2, n) = (1/n)*Sum_{d|n} phi(n/d)*f2(m=2, q=2, d). Note that f2(m=2, q=2, n=1) = 0 and f2(m=2, q=2, n) = A007040(n) for n >= 2.

			For n=1 we have no allowable necklaces (because the strings 0 and 1 can be wrapped around themselves on a circle, and thus they contain runs of length > 2).
For n=2, the only allowable necklace is 01 (because 00 and 11 can be wrapped around themselves on a circle, and thus they contain runs of length > 2).
For n=3, the allowable necklaces are 011 and 100.
For n=4, the allowable necklaces are 0011 and 1010.
For n=5, the allowable necklaces are 01010 and 10101.
For n=6, the allowable necklaces are 010101, 001001, 110110, 101001, and 010110.

A. Burstein and H. S. Wilf, On cyclic strings without long constant blocks, Fibonacci Quarterly, 35 (1997), 240-247.
A. E. Edlin and D. Zeilberger, The Goulden-Jackson cluster method for cyclic words, Adv. Appl. Math., 25 (2000), 228-232.
Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
W. O. J. Moser, Cyclic binary strings without long runs of like (alternating) bits, Fibonacci Quart. 31 (1993), no. 1, 2-6.

Cf. A000358, A007040, A011655, A092297, A218034.

a(n) = (1/n) * sumdiv(n, d, eulerphi(n/d)*(fibonacci(d-1)+fibonacci(d+1))) - sign(n%3); \\ Michel Marcus, Jul 10 2018; using 2nd formula

For proofs of the following formulae, see the comments above.
a(n) = (1/n)*Sum_{d|n} phi(n/d)*A007040(d)*I(d > 1), where I(condition) = 1 if the condition holds, and 0 otherwise.
a(n) = A000358(n) - A011655(n). (This formula is the "unmarked" version of E. W. Weisstein's formula that can be found in the comments for sequence A007040.)
a(p) = A007040(p)/p for p prime >= 2.
G.f.: A(x) = -x*(1+x)/(1-x^3) - Sum_{s>=1} (phi(s)/s)*log(1 - x^s - x^(2*s)) = (g.f. of A000358) - (g.f. of A011655).

More terms from Michel Marcus, Jul 10 2018

A316699 Number of (marked) cyclic n-bit binary strings containing no runs of length > 3.

Original entry on oeis.org

2, 4, 8, 14, 20, 38, 70, 134, 240, 442, 814, 1502, 2756, 5070, 9326, 17158, 31552, 58034, 106742, 196334, 361108, 664182, 1221622, 2246918, 4132720, 7601258, 13980894, 25714878, 47297028, 86992798

Offset: 1

Petros Hadjicostas, Jul 10 2018

Let q and m be positive integers. We denote by f1(m,q,n) the number of (marked) cyclic q-ary strings of length n that contain no runs of lengths > m when no wrapping around is allowed, and by f2(m,q,n) when wrapping around is allowed.
It is clear that f1(m,q,n) = f2(m,q,n) for n > m, but f1(m,q,n) = q^n and f2(m,q,n) = q^n - q when 1 <= n <= m.
Burstein and Wilf (1997) and Edlin and Zeilberger (2000) considered f1(m,q,n) while Hadjicostas and Zhang considered f2(m,q,n).
Let g(m, q, x) = (m+1-m*q*x)/(1-q*x+(q-1)*x^(m+1)) - (m+1)/(1-x^(m+1)).
Burstein and Wilf (1997) proved that the g.f. of the numbers f1(m,q,n) is F1(m,q,x) = ((1-x^m)/(1-x))*(q*x + (q-1)*x* g(m, q, x)).
Using the above formula by Burstein and Wilf (1997), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f2(m,q,n) is F2(m,q,x) = ((q-1)*x*(1-x^m)/(1-x))*g(m, q, x).
A necklace is an unmarked cyclic string. If f3(m,q,n) is the number of q-ary necklaces of length n with no runs of length > m (and wrapping around is allowed), then f3(m,q,n) = (1/n)*Sum_{d|n} phi(n/d)*f2(m,q,d), where phi(.) is Euler's totient function. Using this formula and F2(m,q,x), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f3(m,q,n) is given by F3(m,q,x) = -(q-1)*x*(1-x^m)/((1-x)*(1-x^(m+1))) - Sum_{s>=1} (phi(s)/s)*log(1 - (q-1)*(x^s - x^(s*(m+1)))/(1-x^s)).
For the current sequence, we have q = 2 and m = 3. We have a(n) = f1(m=3, q=2, n) = f2(m=3, q=2, n) for n >= 4, but we have f1(m=3, q=2, n) = 2^n and f2(m=3, q=2, n) = 2^n - 2 for n = 1,2,3.
If A(x) is the g.f. of the current sequence, we have A(x) = F1(m=3,q=2, x) = F2(m=3, q=2, x) + 2*(x+x^2+x^3).
When m = 1 and q = 3, we have f1(m=1, q=3, n) = number of marked cyclic words on three letters with no two consecutive like letters. We have f1(m=1, q=3, n) = A092297(n) for n >= 2. This was first stated in the comments of that sequence by G. Critzer.
When m = 1 and q = 4, we have f1(m=1, q=4, n) = number of marked cyclic words on four letters with no two consecutive like letters. We have f1(m=1, q=4, n) = A218034(n) for n >= 1. This was first stated in the comments of that sequence by J. Arndt.
When m=2 and q=2, we have f1(m=2, q=2, n) = number of marked cyclic words on two letters containing no runs of length > 2. We have f1(m=2, q=2, n) = A007040(n) for n >= 3.
A generalization of the above formula by Burstein and Wilf (1997) was given by Taylor (2014) in Section 5 of his paper.

			For n=4, we have a(4) = 2^4 - 2 = 14 because we exclude 0000 and 1111.
For n=5, we have a(5) = 2^5 - 12 = 20 because we exclude 11111, 11110, 11101, 11011, 10111, 01111, and the same 6 strings with 0 switched with 1.
For n=6, we have a(6) = 2^6 - 26 = 38 because we exclude 111100, 111001, 110011, 100111, 001111, 011110, 111110, 111101, 111011, 110111, 101111, 011111, 111111, and the same 13 strings with 0 switched with 1.

G. C. Greubel, Table of n, a(n) for n = 1..1000
A. Burstein and H. S. Wilf, On cyclic strings without long constant blocks, Fibonacci Quarterly, 35 (1997), 240-247.
A. E. Edlin and D. Zeilberger, The Goulden-Jackson cluster method for cyclic words, Adv. Appl. Math., 25 (2000), 228-232.
Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
A. McLeod and W. O. J. Moser, Counting cyclic binary strings, Math. Mag., 80(1) (2007), 29-37.
Jair Taylor, Counting Words with Laguerre Series, Electron. J. Combin., 21 (2014), P2.1.
Index entries for linear recurrences with constant coefficients, signature (0,1,2,3,2,1).

Cf. A001644, A007040, A092297, A176563, A218034.

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( 2*x*(1+ x+x^2)*(1+x+x^2+x^3-3*x^4-2*x^5-x^6)/( (1+x)*(1+x^2)*(1-x-x^2-x^3)) )); // G. C. Greubel, Apr 23 2019

Rest[CoefficientList[Series[2*x*(1+x+x^2)*(1+x+x^2+x^3-3*x^4-2*x^5-x^6)/( (1+x)*(1+x^2)*(1-x-x^2-x^3)), {x, 0, 40}], x]] (* G. C. Greubel, Apr 23 2019 *)

my(x='x+O('x^40)); Vec(2*x*(1+x+x^2)*(1+x+x^2+x^3-3*x^4-2*x^5-x^6)/( (1+x)*(1+x^2)*(1-x-x^2-x^3))) \\ G. C. Greubel, Apr 23 2019

a=(2*x*(1+x+x^2)*(1+x+x^2+x^3-3*x^4-2*x^5-x^6)/( (1+x)*(1+x^2)*(1-x-x^2-x^3))).series(x, 40).coefficients(x, sparse=False); a[1:] # G. C. Greubel, Apr 23 2019

a(n) = A001644(n) + cos(n*Pi) + 2*cos(n*Pi/2) = A001644(n) - A176563(n+1) for n >= 4.
G.f.: 2*x*(1+x+x^2)*(1+x+x^2+x^3-3*x^4-2*x^5-x^6)/( (1+x)*(1+x^2)*(1-x-x^2-x^3) ).
a(n) = a(n-2) + 2*a(n-3) + 3*a(n-4) + 2*a(n-5) + a(n-6) for n>9. - Colin Barker, Jul 28 2019

cp's OEIS Frontend

A007040 Number of (marked) cyclic n-bit binary strings containing no runs of length > 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A218034 Number of ways to seat 4 types of people in n labeled seats around a circle such that no two adjacent people are of the same type.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

Extensions

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

A090860 Number of ways of 4-coloring a map in which there is a central circle surrounded by an annulus divided into n-1 regions. There are n regions in all.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A140360 Inverse binomial transform of A140359.

Views

Author

Keywords

Comments

Links

Programs

Maple

Mathematica

Formula

Extensions

A106365 Number of necklaces with n beads of 3 colors, no 2 adjacent beads the same color.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A171160 a(n) = a(n-1) + 2*a(n-2) with a(0)=3, a(1)=4.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula