|
%I #53 Jul 04 2018 14:19:12
%S 1,4,10,23,66,192,636,2092,7228,25175,89212,318808,1150444,4177908,
%T 15268494,56078527,206903020,766342160,2848351388,10619472284,
%U 39702648534,148806583111,558999381656,2104255629608,7936108068008,29982733437844,113456750715426,429964269551767,1631663320986086
%N Number of n-bead quaternary necklaces (no turning over allowed) that avoid the subsequence 110.
%C The pattern in this enumeration must be contiguous (all three values next to each other in one sequence of three letters).
%C Because A(x) = Sum_{n>=1} a(n)*x^n = 1 - Sum_{n>=1} (phi(n)/n)*log(1-B(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_{d|n} phi(n/d)*c(d) for n>=1 by using the formula Sum_{n>=1} c(n)*x^n = C(x) = x*(dB/dx)/(1-B(x)). In our case, C(x) = x*(d(q*x-x^3)/dx)/(1-(q*x-x^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(n-1) - c(n-3) 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
%H P. Hadjicostas and L. Zhang, <a href="https://doi.org/10.1016/j.disc.2018.03.007">On cyclic strings avoiding a pattern</a>, Discrete Mathematics, 341 (2018), 1662-1674.
%H Math Stackexchange, Marko Riedel et al., <a href="http://math.stackexchange.com/questions/1812920/">Counting circular sequences</a>.
%H Marko Riedel, <a href="/A274017/a274017.maple.txt">Maple code for this sequence</a>.
%F 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
%F Define sequence (c(n): n>=1) by c(1) = q, c(2) = q^2, c(3) = q^3-3, and c(n) = q*c(n-1) - c(n-3) for n>=4. Then a(n) = (1/n)*Sum_{d|n} phi(n/d)*c(d) for n>=1. (Here q=4.) - _Petros Hadjicostas_, Jan 29 2018
%e The following necklace
%e . 1-1
%e . / \
%e . 0 0
%e . | |
%e . 1 3
%e . \ /
%e . 0-2
%e contains one instance of the subsequence starting in the upper left corner. Unlike a bracelet, the necklace is oriented.
%Y Cf. A000031, A274017, A274018, A274020.
%K nonn
%O 0,2
%A _Marko Riedel_, Jun 06 2016
|
