login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A029907 a(n+1) = a(n) + a(n-1) + Fibonacci(n). 29
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 (list; graph; refs; listen; history; text; internal format)
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

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

Mengmeng Liu, 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

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

CROSSREFS

Cf. A000045, A001629, A010049, A240847.

Sequence in context: A006727 A007673 A182725 * 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 13 06:22 EDT 2020. Contains 336442 sequences. (Running on oeis4.)