login
a(n) = Lucas(n+1) - (n+1).
17

%I #41 Nov 16 2023 11:50:03

%S 1,1,3,6,12,22,39,67,113,188,310,508,829,1349,2191,3554,5760,9330,

%T 15107,24455,39581,64056,103658,167736,271417,439177,710619,1149822,

%U 1860468,3010318,4870815,7881163,12752009,20633204,33385246,54018484,87403765,141422285

%N a(n) = Lucas(n+1) - (n+1).

%C From _Gus Wiseman_, Feb 12 2019: (Start)

%C 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:

%C {{12}} {{123}} {{1234}} {{12345}} {{123456}}

%C {{12}{34}} {{12}{345}} {{12}{3456}}

%C {{14}{23}} {{123}{45}} {{123}{456}}

%C {{125}{34}} {{1234}{56}}

%C {{145}{23}} {{1236}{45}}

%C {{15}{234}} {{1256}{34}}

%C {{126}{345}}

%C {{1456}{23}}

%C {{156}{234}}

%C {{16}{2345}}

%C {{12}{34}{56}}

%C {{16}{23}{45}}

%C 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:

%C {} {} {} {} {}

%C {1,3} {1,3} {1,3}

%C {2,4} {1,4} {1,4}

%C {2,4} {1,5}

%C {2,5} {2,4}

%C {3,5} {2,5}

%C {2,6}

%C {3,5}

%C {3,6}

%C {4,6}

%C {1,3,5}

%C {2,4,6}

%C (End)

%H Harry J. Smith, <a href="/A066982/b066982.txt">Table of n, a(n) for n = 1..250</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,-1,1).

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

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

%F From _Colin Barker_, Jun 30 2012: (Start)

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

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

%F a(n) is the sum of the n-th antidiagonal of A352744 (assuming offset 0). - _Peter Luschny_, Nov 16 2023

%t a[1]=a[2]=1; a[n_]:= a[n] = a[n-1] +a[n-2] +n-2; Table[a[n], {n, 40}]

%t LinearRecurrence[{3, -2, -1, 1}, {1, 1, 3, 6}, 40] (* _Vladimir Joseph Stephan Orlovsky_, Feb 13 2012 *)

%t Table[LucasL[n+1]-n-1, {n, 40}] (* _Vladimir Reshetnikov_, Sep 15 2016 *)

%t 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 *)

%o (PARI) { for (n=1, 250, if (n>2, a=a1 + a2 + n - 2; a2=a1; a1=a, a=a1=1; a=a2=1); write("b066982.txt", n, " ", a) ) } \\ _Harry J. Smith_, Apr 14 2010

%o (PARI) vector(40, n, f=fibonacci; f(n+2)+f(n)-n-1) \\ _G. C. Greubel_, Jul 09 2019

%o (Magma) [Lucas(n+1)-n-1: n in [1..40]]; // _G. C. Greubel_, Jul 09 2019

%o (Sage) [lucas_number2(n+1,1,-1) -n-1 for n in (1..40)] # _G. C. Greubel_, Jul 09 2019

%o (GAP) List([1..40], n-> Lucas(1,-1,n+1)[2] -n-1); # _G. C. Greubel_, Jul 09 2019

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

%K nonn,easy

%O 1,3

%A _Benoit Cloitre_, Jan 27 2002

%E Corrected and extended by _Harvey P. Dale_, Feb 08 2002