A066982 a(n) = Lucas(n+1) - (n+1).

1, 1, 3, 6, 12, 22, 39, 67, 113, 188, 310, 508, 829, 1349, 2191, 3554, 5760, 9330, 15107, 24455, 39581, 64056, 103658, 167736, 271417, 439177, 710619, 1149822, 1860468, 3010318, 4870815, 7881163, 12752009, 20633204, 33385246, 54018484, 87403765, 141422285

Offset: 1

Author

Benoit Cloitre, Jan 27 2002

Keywords

• nonn
• easy

Comments

From Gus Wiseman, Feb 12 2019: (Start)

Also the number of ways to split an (n + 1)-cycle into nonempty connected subgraphs with no singletons. For example, the a(1) = 1 through a(5) = 12 partitions are:

{{12}} {{123}} {{1234}} {{12345}} {{123456}}

{{12}{34}} {{12}{345}} {{12}{3456}}

{{14}{23}} {{123}{45}} {{123}{456}}

{{125}{34}} {{1234}{56}}

{{145}{23}} {{1236}{45}}

{{15}{234}} {{1256}{34}}

{{126}{345}}

{{1456}{23}}

{{156}{234}}

{{16}{2345}}

{{12}{34}{56}}

{{16}{23}{45}}

Also the number of non-singleton subsets of {1, ..., (n + 1)} with no cyclically successive elements (cyclically successive means 1 succeeds n + 1). For example, the a(1) = 1 through a(5) = 12 subsets are:

{} {} {} {} {}

{1,3} {1,3} {1,3}

{2,4} {1,4} {1,4}

{2,4} {1,5}

{2,5} {2,4}

{3,5} {2,5}

{2,6}

{3,5}

{3,6}

{4,6}

{1,3,5}

{2,4,6}

(End)

Links

• Harry J. Smith, Table of n, a(n) for n = 1..250
• Index entries for linear recurrences with constant coefficients, signature (3,-2,-1,1).

Crossrefs

Cf. A000032, A000045, A000126, A000325, A005251, A169985, A323953, A323954, A352744.

Programs

GAP

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

Magma

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

Mathematica

a[1]=a[2]=1; a[n_]:= a[n] = a[n-1] +a[n-2] +n-2; Table[a[n], {n, 40}]
LinearRecurrence[{3, -2, -1, 1}, {1, 1, 3, 6}, 40] (* Vladimir Joseph Stephan Orlovsky, Feb 13 2012 *)
Table[LucasL[n+1]-n-1, {n, 40}] (* Vladimir Reshetnikov, Sep 15 2016 *)
CoefficientList[Series[(1-2*x+2*x^2)/((1-x)^2*(1-x-x^2)), {x, 0, 40}], x] (* L. Edson Jeffery, Sep 28 2017 *)

PARI

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

Sage

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

Formula

a(1) = a(2) = 1, a(n + 2) = a(n + 1) + a(n) + n.

For n > 2, a(n) = floor(phi^(n+1) - (n+1)) + (1-(-1)^n)/2.

From Colin Barker, Jun 30 2012: (Start)

a(n) = 3*a(n-1) - 2*a(n-2) - a(n-3) + a(n-4).

G.f.: x*(1-2*x+2*x^2)/((1-x)^2*(1-x-x^2)). (End)

a(n) is the sum of the n-th antidiagonal of A352744 (assuming offset 0). - Peter Luschny, Nov 16 2023

Extensions

Corrected and extended by Harvey P. Dale, Feb 08 2002