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

0, 1, 2, 4, 8, 15, 28, 51, 92, 164, 290, 509, 888, 1541, 2662, 4580, 7852, 13419, 22868, 38871, 65920, 111556, 188422, 317689, 534768, 898825, 1508618, 2528836, 4233872, 7080519, 11828620, 19741179, 32916068, 54835556, 91276202, 151814645, 252318312

Offset

0,3

Comments

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).

a(n+1) gives row sums of A054450. - Paul Barry, Oct 23 2004

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.

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

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

David Broadhurst, Zig-zag resistance and OEIS sequence A029907, Apr 11 2024

Jia Huang, Compositions with restricted parts, arXiv:1812.11010 [math.CO], 2018.

Mengmeng Liu and Andrew Yezhou Wang, The Number of Designated Parts in Compositions with Restricted Parts, J. Int. Seq., Vol. 23 (2020), Article 20.1.8.

Index entries for linear recurrences with constant coefficients, signature (2,1,-2,-1).

Formula

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

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

a(n+1) = Sum_{k=0..n} Sum_{j=0..floor(k/2)} binomial(n-j, j). - Paul Barry, Oct 23 2004

a(n) = A010049(n+1) + A152163(n+1). - R. J. Mathar, Dec 10 2011

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

a(n) = (1/5)*(n*A000032(n) + 4*A000045(n)). - G. C. Greubel, Apr 06 2022

a(n) = A001629(n+1) - A001629(n-1), where A001629 is the first convolution of the Fibonacci numbers. - Gregory L. Simay, Aug 30 2022

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

Example

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}.

Maple

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

Mathematica

CoefficientList[Series[x(1-x^2)/(1-x-x^2)^2, {x, 0, 37}], x] (* or *)
a[n_]:= a[n]= a[n-1] +a[n-2] +Fibonacci[n-1]; a[0]=0; a[1]=1; Array[a, 37] (* or *)
LinearRecurrence[{2, 1, -2, -1}, {0, 1, 2, 4}, 38] (* Robert G. Wilson v, Jun 22 2014 *)

Prog

(PARI) alias(F, fibonacci); a(n)=((n+4)*F(n)+2*n*F(n-1))/5;
(Haskell)
a029907 n = a029907_list !! n
a029907_list = 0 : 1 : zipWith (+) (tail a000045_list)
                      (zipWith (+) (tail a029907_list) a029907_list)
-- Reinhard Zumkeller, Nov 01 2013
(Magma) [((n+4)*Fibonacci(n)+2*n*Fibonacci(n-1))/5: n in [0..40]]; // Vincenzo Librandi, Feb 25 2018
(SageMath)
def A029907(n): return (1/5)*(n*lucas_number2(n, 1, -1) + 4*fibonacci(n))
[A029907(n) for n in (0..40)] # G. C. Greubel, Apr 06 2022

Crossrefs

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

Sequence in context: A182725 A334635 A358836 * A005682 A114833 A065617

Adjacent sequences: A029904 A029905 A029906 * A029908 A029909 A029910

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

Additional formula from Wolfdieter Lang, May 02 2000

Additional comments from Michael Somos, Jul 23 2002

Status

approved