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

Author

N. J. A. Sloane

Keywords

• nonn
• easy

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

Examples

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

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
• Jean-Luc Baril and Nathanaël Hassler, Intervals in a family of Fibonacci lattices, Univ. de Bourgogne (France, 2024). See p. 5.
• 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).

Crossrefs

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

Programs

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

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

PARI

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

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

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

Extensions

Additional formula from Wolfdieter Lang, May 02 2000

Additional comments from Michael Somos, Jul 23 2002