A274019 Number of n-bead quaternary necklaces (no turning over allowed) that avoid the subsequence 110.

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

Offset: 0

Author

Marko Riedel, Jun 06 2016

Keywords

• nonn

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

Examples

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

Links

• P. Hadjicostas and L. Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
• Math Stackexchange, Marko Riedel et al., Counting circular sequences.
• Marko Riedel, Maple code for this sequence.

Crossrefs

Cf. A000031, A274017, A274018, A274020.

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^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