

A274019


Number of nbead quaternary necklaces (no turning over allowed) that avoid the subsequence 110.


3



1, 4, 10, 23, 66, 192, 636, 2092, 7228, 25175, 89212, 318808, 1150444, 4177908, 15268494, 56078527, 206903020, 766342160, 2848351388, 10619472284, 39702648534, 148806583111, 558999381656, 2104255629608, 7936108068008, 29982733437844, 113456750715426, 429964269551767, 1631663320986086
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

The pattern in this enumeration must be contiguous (all three values next to each other in one sequence of three letters).
Because A(x) = Sum_{n>=1} a(n)*x^n = 1  Sum_{n>=1} (phi(n)/n)*log(1B(x^n)), where B(x) = q*x  x^3 and q = 4, we may find sequence (c(n): n>=1) that satisfies a(n) = (1/n)*Sum_{dn} phi(n/d)*c(d) for n>=1 by using the formula Sum_{n>=1} c(n)*x^n = C(x) = x*(dB/dx)/(1B(x)). In our case, C(x) = x*(d(q*xx^3)/dx)/(1(q*xx^3)) = (q*x  3*x^3)/(1  q*x + x^3). This implies that c(1) = q, c(2) = q^2, c(3) = q^3  3, and c(n) = q*c(n1)  c(n3) for n>=4. This comment applies not only to this sequence, but also to sequences A274017, A274018 and A274020 as well (corresponding to cases q=2, 3, and 5, respectively).  Petros Hadjicostas, Jan 31 2018


LINKS

Table of n, a(n) for n=0..28.
P. Hadjicostas and L. Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 16621674.
Math Stackexchange, Marko Riedel et al., Counting circular sequences.
Marko Riedel, Maple code for this sequence.


FORMULA

G.f.: 1  Sum_{n>=1} (phi(n)/n)*log(x^(3*n)q*x^n+1), where q=4 is the number of symbols in the alphabet we are using.  Petros Hadjicostas, Sep 12 2017
Define sequence (c(n): n>=1) by c(1) = q, c(2) = q^2, c(3) = q^33, and c(n) = q*c(n1)  c(n3) for n>=4. Then a(n) = (1/n)*Sum_{dn} phi(n/d)*c(d) for n>=1. (Here q=4.)  Petros Hadjicostas, Jan 29 2018


EXAMPLE

The following necklace
. 11
. / \
. 0 0
.  
. 1 3
. \ /
. 02
contains one instance of the subsequence starting in the upper left corner. Unlike a bracelet, the necklace is oriented.


CROSSREFS

Cf. A000031, A274017, A274018, A274020.
Sequence in context: A137531 A102549 A277789 * A008258 A008251 A174934
Adjacent sequences: A274016 A274017 A274018 * A274020 A274021 A274022


KEYWORD

nonn


AUTHOR

Marko Riedel, Jun 06 2016


STATUS

approved



