A274017 -id:A274017 - cp's OEIS frontend

A001612 a(n) = a(n-1) + a(n-2) - 1 for n > 1, a(0)=3, a(1)=2.

3, 2, 4, 5, 8, 12, 19, 30, 48, 77, 124, 200, 323, 522, 844, 1365, 2208, 3572, 5779, 9350, 15128, 24477, 39604, 64080, 103683, 167762, 271444, 439205, 710648, 1149852, 1860499, 3010350, 4870848, 7881197, 12752044, 20633240, 33385283, 54018522

Offset: 0

N. J. A. Sloane

a(n+3) = A^(n)B^(2)(1), n >= 0, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 5=`00`, 8=`100`, 12=`1100`, ..., in Wythoff code.
From Petros Hadjicostas, Jan 11 2017: (Start)
a(n) is the number of cyclic sequences consisting of zeros and ones that avoid the pattern 001 (or equivalently, the pattern 110) provided the positions of zeros and ones on a circle are fixed. This can easily be proved by considering that sequence A000071(n+3) is the number of binary zero-one words of length n that avoid the pattern 001 and that a(n) = A000071(n+3) - 2*A000071(n). (From the collection of all zero-one binary sequences that avoid 001 subtract those that start with 1 and end with 00 and those that start with 01 and end with 0.)
For n = 1,2, the number a(n) still gives the number of cyclic sequences consisting of zeros and ones that avoid the pattern 001 (provided the positions of zeros and ones on a circle are fixed) even if we assume that the sequence wraps around itself on the circle. For example, when 01 wraps around itself, it becomes 01010..., and it never contains the pattern 001. (End)
For n >= 3, a(n) is also the number of independent vertex sets and vertex covers in the wheel graph on n+1 nodes. - Eric W. Weisstein, Mar 31 2017

			a(3) = 5 because the following cyclic sequences of length three avoid the pattern 001: 000, 011, 101, 110, 111. - _Petros Hadjicostas_, Jan 11 2017

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

T. D. Noe, Table of n, a(n) for n = 0..500
Nazim Fatès, Biswanath Sethi, and Sukanta Das, On the reversibility of ECAs with fully asynchronous updating: the recurrence point of view, hal-01571847 Preprint, 2017.
Martin Griffiths, On a Matrix Arising from a Family of Iterated Self-Compositions, Journal of Integer Sequences, 18 (2015), #15.11.8.
Fumio Hazama, Spectra of graphs attached to the space of melodies, Discr. Math., 311 (2011), 2368-2383. See Table 5.2.
Martin Herschend and Peter Jorgensen, Classification of higher wide subcategories for higher Auslander algebras of type A, arXiv:2002.01778 [math.RT], 2020.
Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 97.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Vertex Cover
Eric Weisstein's World of Mathematics, Wheel Graph
Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Cf. A000032, A000071, A274017.

a001612 n = a001612_list !! n
a001612_list = 3 : 2 : (map (subtract 1) $
   zipWith (+) a001612_list (tail a001612_list))
-- Reinhard Zumkeller, May 26 2013

A001612:=-(-2+3*z**2)/(z-1)/(z**2+z-1); # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence except for the initial 3

Join[{b=3},a=0;Table[c=a+b-1;a=b;b=c,{n,100}]] (* Vladimir Joseph Stephan Orlovsky, Mar 15 2011 *)
Table[Fibonacci[n] + Fibonacci[n - 2] + 1, {n, 20}] (* Eric W. Weisstein, Mar 31 2017 *)
LinearRecurrence[{2, 0, -1}, {3, 2, 4}, 20] (* Eric W. Weisstein, Mar 31 2017 *)
CoefficientList[Series[(3 - 4 x)/(1 - 2 x + x^3), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)

PARI
```
a(n)=fibonacci(n+1)+fibonacci(n-1)+1
```

G.f.: (3-4*x)/((1-x)*(1-x-x^2)).
a(n) = a(n-1) + a(n-2) - 1.
a(n) = A000032(n) + 1.
a(n) = A000071(n+3) - 2*A000071(n). - Petros Hadjicostas, Jan 11 2017

Additional comments from Michael Somos, Jun 01 2000

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

Original entry on oeis.org

1, 3, 6, 10, 21, 42, 103, 237, 603, 1519, 3942, 10257, 27131, 71940, 192462, 516933, 1395636, 3781356, 10283911, 28050600, 76732047, 210414811, 578330649, 1592821005, 4395261552, 12149386569, 33637309323, 93267459520, 258961863288, 719938597227, 2003881480452, 5583818718102, 15575529493713

Offset: 0

Marko Riedel, Jun 06 2016

nonn

The pattern in this enumeration must be contiguous (all three values next to each other in one sequence of three letters).

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

Math Stackexchange, Marko Riedel et al., Counting circular sequences.
Marko Riedel, Maple code for this sequence.

Cf. A000031, A274017, A274019, A274020.

G.f.: 1 - Sum_{n>=1} (phi(n)/n)*log(x^(3*n) - q*x^n + 1), where q=3 is the number of symbols in the alphabet we are using. - Petros Hadjicostas, Sep 12 2017

a(n) = (1/n)*Sum_{d|n} phi(n/d)*A215885(d) for n >= 1. - Petros Hadjicostas, Sep 13 2017

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

Original entry on oeis.org

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

Marko Riedel, Jun 06 2016

nonn

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

			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.

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.

Cf. A000031, A274017, A274018, A274020.

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

A274020 Number of n-bead 5-ary necklaces (no turning over allowed) that avoid the subsequence 110.

Original entry on oeis.org

1, 5, 15, 44, 160, 604, 2510, 10545, 45825, 201669, 900307, 4057625, 18447565, 84444000, 388878560, 1799985435, 8368841895, 39062428790, 182961584260, 859612223990, 4049955449888, 19128675877279, 90553562670495, 429560546547595, 2041573370075675, 9719864998575489, 46350124359578975, 221352533355568044

Offset: 0

Marko Riedel, Jun 06 2016

nonn

The pattern in this enumeration must be contiguous (all three values next to each other in one sequence of three letters).

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

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.

Cf. A000031, A274017, A274018, A274019.

G.f.: 1 - Sum_{n>=1} (phi(n)/n)*log(x^(3*n)-q*x^n+1), where q=5 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=5.) - Petros Hadjicostas, Jan 29 2018

cp's OEIS Frontend

A001612 a(n) = a(n-1) + a(n-2) - 1 for n > 1, a(0)=3, a(1)=2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A274020 Number of n-bead 5-ary necklaces (no turning over allowed) that avoid the subsequence 110.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula