|
%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,changed
%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
|
