login
a(n+1) = a(n) + a(n-1) + Fibonacci(n), with a(0) = 0 and a(1) = 1.
31

%I #113 Apr 12 2024 12:41:27

%S 0,1,2,4,8,15,28,51,92,164,290,509,888,1541,2662,4580,7852,13419,

%T 22868,38871,65920,111556,188422,317689,534768,898825,1508618,2528836,

%U 4233872,7080519,11828620,19741179,32916068,54835556,91276202,151814645,252318312

%N a(n+1) = a(n) + a(n-1) + Fibonacci(n), with a(0) = 0 and a(1) = 1.

%C Number of matchings of the fan graph on n vertices, n>0 (a fan is the join of the path graph with one extra vertex).

%C a(n+1) gives row sums of A054450. - _Paul Barry_, Oct 23 2004

%C Number of parts in all compositions of n into odd parts. Example: a(5)=15 because the compositions 5, 311, 131, 113, and 11111 have a total of 1+3+3+3+5=15 parts.

%C a(n-1) is the number of compositions of n that contain one even part; for example, a(5-1)=a(4)=8 counts the compositions 1112, 1121, 1211, 14, 2111, 23, 32, 41. - _Joerg Arndt_, May 21 2013

%H Reinhard Zumkeller, <a href="/A029907/b029907.txt">Table of n, a(n) for n = 0..1000</a>

%H David Broadhurst, <a href="/A029907/a029907.txt">Zig-zag resistance and OEIS sequence A029907</a>, Apr 11 2024

%H Jia Huang, <a href="https://arxiv.org/abs/1812.11010">Compositions with restricted parts</a>, arXiv:1812.11010 [math.CO], 2018.

%H Mengmeng Liu and Andrew Yezhou Wang, <a href="https://www.emis.de/journals/JIS/VOL23/Wang/wang61.html">The Number of Designated Parts in Compositions with Restricted Parts</a>, J. Int. Seq., Vol. 23 (2020), Article 20.1.8.

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

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

%F a(n) = ((n+4)*Fibonacci(n) + 2*n*Fibonacci(n-1))/5.

%F a(n+1) = Sum_{k=0..n} Sum_{j=0..floor(k/2)} binomial(n-j, j). - _Paul Barry_, Oct 23 2004

%F a(n) = A010049(n+1) + A152163(n+1). - _R. J. Mathar_, Dec 10 2011

%F a(n) = F(n) + Sum_{k=1..n-1} F(k)*F(n-k), where F=Fibonacci. - _Reinhard Zumkeller_, Nov 01 2013

%F a(n) = (1/5)*(n*A000032(n) + 4*A000045(n)). - _G. C. Greubel_, Apr 06 2022

%F a(n) = A001629(n+1) - A001629(n-1), where A001629 is the first convolution of the Fibonacci numbers. - _Gregory L. Simay_, Aug 30 2022

%F E.g.f.: exp(x/2)*(5*x*cosh(sqrt(5)*x/2) + sqrt(5)*(5*x + 8)*sinh(sqrt(5)*x/2))/25. - _Stefano Spezia_, Dec 04 2023

%e a(4)=8 because matchings of fan graph with edges {OA,OB,OC,AB,AC} are: {},{OA},{OB},{OC},{AB},{AC},{OA,BC},{OC,AB}.

%p with(combinat); A029907 := proc(n) options remember; if n <= 1 then n else procname(n-1)+procname(n-2)+fibonacci(n-1); fi; end;

%t CoefficientList[Series[x(1-x^2)/(1-x-x^2)^2, {x, 0, 37}], x] (* or *)

%t a[n_]:= a[n]= a[n-1] +a[n-2] +Fibonacci[n-1]; a[0]=0; a[1]=1; Array[a, 37] (* or *)

%t LinearRecurrence[{2,1,-2,-1}, {0,1,2,4}, 38] (* _Robert G. Wilson v_, Jun 22 2014 *)

%o (PARI) alias(F,fibonacci); a(n)=((n+4)*F(n)+2*n*F(n-1))/5;

%o (Haskell)

%o a029907 n = a029907_list !! n

%o a029907_list = 0 : 1 : zipWith (+) (tail a000045_list)

%o (zipWith (+) (tail a029907_list) a029907_list)

%o -- _Reinhard Zumkeller_, Nov 01 2013

%o (Magma) [((n+4)*Fibonacci(n)+2*n*Fibonacci(n-1))/5: n in [0..40]]; // _Vincenzo Librandi_, Feb 25 2018

%o (SageMath)

%o def A029907(n): return (1/5)*(n*lucas_number2(n, 1, -1) + 4*fibonacci(n))

%o [A029907(n) for n in (0..40)] # _G. C. Greubel_, Apr 06 2022

%Y Cf. A000032, A000045, A001629, A010049, A054450, A152163, A240847.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_

%E Additional formula from _Wolfdieter Lang_, May 02 2000

%E Additional comments from _Michael Somos_, Jul 23 2002