A032190 -id:A032190 - cp's OEIS frontend

A001610 a(n) = a(n-1) + a(n-2) + 1, with a(0) = 0 and a(1) = 2.

0, 2, 3, 6, 10, 17, 28, 46, 75, 122, 198, 321, 520, 842, 1363, 2206, 3570, 5777, 9348, 15126, 24475, 39602, 64078, 103681, 167760, 271442, 439203, 710646, 1149850, 1860497, 3010348, 4870846, 7881195, 12752042, 20633238, 33385281, 54018520

Offset: 0

N. J. A. Sloane

For prime p, p divides a(p-1). - T. D. Noe, Apr 11 2009 [This result follows immediately from the fact that A032190(n) = (1/n)*Sum_{d|n} a(d-1)*phi(n/d). - Petros Hadjicostas, Sep 11 2017]
Generalization. If a(0,x)=0, a(1,x)=2 and, for n>=2, a(n,x)=a(n-1,x)+x*a(n-2,x)+1, then we obtain a sequence of polynomials Q_n(x)=a(n,x) of degree floor((n-1)/2), such that p is prime iff all coefficients of Q_(p-1)(x) are multiple of p (sf. A174625). Thus a(n) is the sum of coefficients of Q_(n-1)(x). - Vladimir Shevelev, Apr 23 2010
Odd composite numbers n such that n divides a(n-1) are in A005845. - Zak Seidov, May 04 2010; comment edited by N. J. A. Sloane, Aug 10 2010
a(n) is the number of ways to modify a circular arrangement of n objects by swapping one or more adjacent pairs. E.g., for 1234, new arrangements are 2134, 2143, 1324, 4321, 1243, 4231 (taking 4 and 1 to be adjacent) and a(4) = 6. - Toby Gottfried, Aug 21 2011
For n>2, a(n) equals the number of Markov equivalence classes with skeleton the cycle on n+1 nodes.  See Theorem 2.1 in the article by A. Radhakrishnan et al. below. - Liam Solus, Aug 23 2018
From Gus Wiseman, Feb 12 2019: (Start)
For n > 0, also the number of nonempty subsets of {1, ..., n + 1} containing no two cyclically successive elements (cyclically successive means 1 succeeds n + 1). For example, the a(5) = 17 stable subsets are:
  {1}, {2}, {3}, {4}, {5}, {6},
  {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {2,6}, {3,5}, {3,6}, {4,6},
  {1,3,5}, {2,4,6}.
(End)
Also the rank of the n-Lucas cube graph. - Eric W. Weisstein, Aug 01 2023

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
Daniel Birmajer, Juan B. Gil, Michael D. Weiner, Linear recurrence sequences with indices in arithmetic progression and their sums, arXiv:1505.06339 [math.NT], 2015.
Ning-Ning Cao and Feng-Zhen Zhao, Some Properties of Hyperfibonacci and Hyperlucas Numbers, J. Int. Seq. 13 (2010) # 10.8.8.
Ligia L. Cristea, Ivica Martinjak, and Igor Urbiha, Hyperfibonacci Sequences and Polytopic Numbers, Journal of Integer Sequences, Vol. 19, 2016, Issue 7, #16.7.6.
Taras Goy and Mark Shattuck, Toeplitz-Hessenberg determinant formulas for the sequence F_n-1, Online J. Anal. Comb. (2025) Vol. 19, Paper 1, 1-26.
Petros Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016), Article 16.8.2.
Fumio Hazama, Spectra of graphs attached to the space of melodies, Discrete Math., 311 (2011), 2368-2383. See Table 2.1.
Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 96.
Kantaphon Kuhapatanakul, On the Sums of Reciprocal Generalized Fibonacci Numbers, J. Int. Seq. 16 (2013) #13.7.1.
Rui Liu and Feng-Zhen Zhao, On the Sums of Reciprocal Hyperfibonacci Numbers and Hyperlucas Numbers, Journal of Integer Sequences, Vol. 15 (2012), #12.4.5. - From _N. J. A. Sloane_, Oct 05 2012
Richard J. Mathar, Hardy-Littlewood constants embedded into infinite products over all positive integers, sequence a_{1,s}, arXiv:0903.2514 [math.NT], 2009-2011.
El-Mehdi Mehiri, Saad Mneimneh, and Hacène Belbachir, The Towers of Fibonacci, Lucas, Pell, and Jacobsthal, arXiv:2502.11045 [math.CO], 2025. See p. 12.
Natascha Neumärker, Realizability of Integer Sequences as Differences of Fixed Point Count Sequences, Journal of Integer Sequences 12 (2009) 09.4.5, Example 10.
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
Adityanarayanan Radhakrishnan, Liam Solus, and Caroline Uhler. Counting Markov equivalence classes for DAG models on trees, arXiv:1706.06091 [math.CO], 2017; Discrete Applied Mathematics 244 (2018): 170-185.
Vladimir Shevelev, On divisibility of C(n-i-1,i-1) by i, Int. J. of Number Theory, 3 (2007), no.1, 119-139. [_Vladimir Shevelev_, Apr 23 2010]
Eric Weisstein's World of Mathematics, Graph Rank
Eric Weisstein's World of Mathematics, Lucas Cube Graph
John W. Wrench, Jr., Evaluation of Artin's constant and the twin-prime constant, Math. Comp., 15 (1961), 396-398.
Li-Na Zheng, Rui Liu, and Feng-Zhen Zhao, On the Log-Concavity of the Hyperfibonacci Numbers and the Hyperlucas Numbers, Journal of Integer Sequences, Vol. 17 (2014), #14.1.4.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1).

Cf. A000032 (first differences), A000071, A000126, A000204, A000296, A001644, A032190, A169985, A174625, A306357.

List([0..40], n-> Lucas(1,-1,n+1)[2] -1); # G. C. Greubel, Jul 12 2019

a001610 n = a001610_list !! n
a001610_list =
   0 : 2 : map (+ 1) (zipWith (+) a001610_list (tail a001610_list))
-- Reinhard Zumkeller, Aug 21 2011

I:=[0,2]; [n le 2 select I[n] else Self(n-1)+Self(n-2)+1: n in [1..40]]; // Vincenzo Librandi, Mar 20 2015

[Lucas(n+1) -1: n in [0..40]]; // G. C. Greubel, Jul 12 2019

t = {0, 2}; Do[AppendTo[t, t[[-1]] + t[[-2]] + 1], {n, 2, 40}]; t
RecurrenceTable[{a[n] == a[n - 1] +a[n - 2] +1, a[0] == 0, a[1] == 2}, a, {n, 0, 40}] (* Robert G. Wilson v, Apr 13 2013 *)
CoefficientList[Series[x (2 - x)/((1 - x - x^2) (1 - x)), {x, 0, 40}], x] (* Vincenzo Librandi, Mar 20 2015 *)
Table[Fibonacci[n] + Fibonacci[n + 2] - 1, {n, 0, 40}] (* Eric W. Weisstein, Feb 13 2018 *)
LinearRecurrence[{2, 0, -1}, {2, 3, 6}, 20] (* Eric W. Weisstein, Feb 13 2018 *)
Table[LucasL[n] - 1, {n, 20}] (* Eric W. Weisstein, Aug 01 2023 *)
LucasL[Range[20]] - 1 (* Eric W. Weisstein, Aug 01 2023 *)

a(n)=([0,1,0; 0,0,1; -1,0,2]^n*[0;2;3])[1,1] \\ Charles R Greathouse IV, Sep 08 2016

vector(40, n, f=fibonacci; f(n+1)+f(n-1)-1) \\ G. C. Greubel, Jul 12 2019

[lucas_number2(n+1,1,-1) -1 for n in (0..40)] # G. C. Greubel, Jul 12 2019

a(n) = A000204(n)-1 = A000032(n+1)-1 = A000071(n+1) + A000045(n).
G.f.: x*(2-x)/((1-x-x^2)*(1-x)) = (2*x-x^2)/(1-2*x+x^3). [Simon Plouffe in his 1992 dissertation]
a(n) = F(n) + F(n+2) - 1 where F(n) is the n-th Fibonacci number. - Zerinvary Lajos, Jan 31 2008
a(n) = A014217(n+1) - A000035(n+1). - Paul Curtz, Sep 21 2008
a(n) = Sum_{i=1..floor((n+1)/2)} ((n+1)/i)*C(n-i,i-1). In more general case of polynomials Q_n(x)=a(n,x) (see our comment) we have Q_n(x) = Sum_{i=1..floor((n+1)/2)}((n+1)/i)*C(n-i,i-1)*x^(i-1). - Vladimir Shevelev, Apr 23 2010
a(n) = Sum_{k=0..n-1} Lucas(k), where Lucas(n) = A000032(n). - Gary Detlefs, Dec 07 2010
a(0)=0, a(1)=2, a(2)=3; for n>=3, a(n) = 2*a(n-1) - a(n-3). - George F. Johnson, Jan 28 2013
For n > 1, a(n) = A048162(n+1) + 3. - Toby Gottfried, Apr 13 2013
For n > 0, a(n) = A169985(n + 1) - 1. - Gus Wiseman, Feb 12 2019

A000358 Number of binary necklaces of length n with no subsequence 00, excluding the necklace "0".

Original entry on oeis.org

1, 2, 2, 3, 3, 5, 5, 8, 10, 15, 19, 31, 41, 64, 94, 143, 211, 329, 493, 766, 1170, 1811, 2787, 4341, 6713, 10462, 16274, 25415, 39651, 62075, 97109, 152288, 238838, 375167, 589527, 927555, 1459961, 2300348, 3626242, 5721045, 9030451, 14264309, 22542397, 35646312, 56393862, 89264835, 141358275

Offset: 1

Frank Ruskey

a(n) is also the number of inequivalent compositions of n into parts 1 and 2 where two compositions are considered to be equivalent if one is a cyclic rotation of the other. a(6)=5 because we have: 2+2+2, 2+2+1+1, 2+1+2+1, 2+1+1+1+1, 1+1+1+1+1+1. - Geoffrey Critzer, Feb 01 2014

Moebius transform is A006206. - Michael Somos, Jun 02 2019

			G.f. = x + 2*x^2 + 2*x^3 + 3*x^4 + 3*x^5 + 5*x^6 + 5*x^7 + 8*x^8 + 10*x^9 + ... - _Michael Somos_, Jun 02 2019
Binary necklaces are: 1; 01, 11; 011, 111; 0101, 0111, 1111; 01010, 01011, 01111. - _Michael Somos_, Jun 02 2019

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 499.
T. Helleseth and A. Kholosha, Bent functions and their connections to combinatorics, in Surveys in Combinatorics 2013, edited by Simon R. Blackburn, Stefanie Gerke, Mark Wildon, Camb. Univ. Press, 2013.

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Ricardo Gómez Aíza, Symbolic dynamical scales: modes, orbitals, and transversals, arXiv:2009.02669 [math.DS], 2020.
A. R. Ashrafi, J. Azarija, K. Fathalikhani, S. Klavzar, and Marko Petkovsek, Orbits of Fibonacci and Lucas cubes, dihedral transformations, and asymmetric strings, 2014.
A. R. Ashrafi, J. Azarija, K. Fathalikhani, S. Klavzar, and Marko Petkovsek, Vertex and Edge Orbits of Fibonacci and Lucas Cubes, Ann. Comb. 20 (2016), 209-229.
M. Assis, J. L. Jacobsen, I. Jensen, J.-M. Maillard, and B. M. McCoy, Integrability vs non-integrability: Hard hexagons and hard squares compared, arXiv preprint 1406.5566 [math-ph], 2014.
M. Assis, J. L. Jacobsen, I. Jensen, J.-M. Maillard, and B. M. McCoy, Integrability versus non-integrability: Hard hexagons and hard squares compared, J. Phys. A: Math. Theor. 47 (2014) 445001 (53pp.).
Daryl DeFord, Enumerating distinct chessboard tilings, Fibonacci Quart. 52 (2014), 102-116; see formula (5.3) in Theorem 5.2, p. 111.
P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
P. Flajolet and M. Soria, The Cycle Construction, SIAM J. Discr. Math., vol. 4 (1), 1991, pp. 58-60.
Benjamin Hackl and Helmut Prodinger, The Necklace Process: A Generating Function Approach, arXiv:1801.09934 [math.PR], 2018. [The paper mentions this sequence, but the authors mean sequence A032190(n) = a(n) - 1.]
Benjamin Hackl and Helmut Prodinger, The Necklace Process: A Generating Function Approach, Statistics and Probability Letters 142 (2018), 57-61. [The paper mentions this sequence, but the authors mean sequence A032190(n) = a(n) - 1.]
P. Hadjicostas, Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence, J. Integer Sequences 19 (2016), #16.8.2.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 119
Tom Roby, Dynamical algebraic combinatorics and homomesy: An action-packed introduction, AlCoVE: an Algebraic Combinatorics Virtual Expedition (2020).
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
C. J. Turner, A. A. Michailidis, D. A. Abanin, M. Serbyn, and Z. Papić, Quantum scarred eigenstates in a Rydberg atom chain: entanglement, breakdown of thermalization, and stability to perturbations, arXiv:1806.10933 [cond-mat.quant-gas], 2018.
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.
Index entries for sequences related to necklaces

Cf. A006206, A032190, A093305, A280218, A280218.

Column k=0 of A320341.

A000358 := proc(n) local sum; sum := 0; for d in divisors(n) do sum := sum + phi(n/d)*(fibonacci(d+1)+fibonacci(d-1)) od; RETURN(sum/n); end;
with(combstruct); spec := {A=Union(zero,Cycle(one),Cycle(Prod(zero,Sequence(one,card>0)))),one=Atom,zero=Atom}; seq(count([A,spec,unlabeled],size=i),i=1..30);

nn=48;Drop[Map[Total,Transpose[Map[PadRight[#,nn]&,Table[ CoefficientList[ Series[CycleIndex[CyclicGroup[n],s]/.Table[s[i]->x^i+x^(2i),{i,1,n}],{x,0,nn}],x],{n,0,nn}]]]],1] (* Geoffrey Critzer, Feb 01 2014 *)
max = 50; B[x_] := x*(1+x); A = Sum[EulerPhi[k]/k*Log[1/(1-B[x^k])], {k, 1, max}]/x + O[x]^max; CoefficientList[A, x] (* Jean-François Alcover, Feb 08 2016, after Joerg Arndt *)
Table[1/n * Sum[EulerPhi[n/d] Total@ Map[Fibonacci, d + # & /@ {-1, 1}], {d, Divisors@ n}], {n, 47}] (* Michael De Vlieger, Dec 28 2016 *)
a[ n_] := If[ n < 1, 0, DivisorSum[n, EulerPhi[n/#] LucasL[#] &]/n]; (* Michael Somos, Jun 02 2019 *)

N=66;  x='x+O('x^N);
B(x)=x*(1+x);
A=sum(k=1, N, eulerphi(k)/k*log(1/(1-B(x^k))));
Vec(A)
/* Joerg Arndt, Aug 06 2012 */

{a(n) = if( n<1, 0, sumdiv(n, d, eulerphi(n/d) * (fibonacci(d+1) + fibonacci(d-1)))/n)}; /* Michael Somos, Jun 02 2019 */

from sympy import totient, lucas, divisors
def A000358(n): return (n&1^1)+sum(totient(n//k)*(lucas(k)-((k&1^1)<<1)) for k in divisors(n,generator=True))//n # Chai Wah Wu, Sep 23 2023

a(n) = (1/n) * Sum_{ d divides n } totient(n/d) [ Fib(d-1)+Fib(d+1) ].
G.f.: Sum_{k>=1} phi(k)/k * log( 1/(1-B(x^k)) ) where B(x)=x*(1+x). - Joerg Arndt, Aug 06 2012
a(n) ~ ((1+sqrt(5))/2)^n / n. - Vaclav Kotesovec, Sep 12 2014
a(n) = Sum_{0 <= i <= ceiling((n-1)/2)} [ (1/(n - i)) * Sum_{d|gcd(i, n-i)} phi(d) * binomial((n - i)/d, i/d) ]. (This is DeFord's formula for the number of distinct Lucas tilings of a 1 X n bracelet up to symmetry, even though in the paper he refers to sequence A032192(n) = a(n) - 1.) - Petros Hadjicostas, Jun 07 2019

cp's OEIS Frontend

A001610 a(n) = a(n-1) + a(n-2) + 1, with a(0) = 0 and a(1) = 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Magma

Mathematica

PARI

PARI

Sage

Formula

A000358 Number of binary necklaces of length n with no subsequence 00, excluding the necklace "0".

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

A032278 Number of ways to partition n elements into pie slices each with at least 2 elements allowing the pie to be turned over.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A063686 Triangular array: T(n,k) is the number of binary necklaces (no turning over) of length n whose longest run of 1's has length k. Table begins at n=0, k=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions