A004695 a(n) = floor(Fibonacci(n)/2).

0, 0, 0, 1, 1, 2, 4, 6, 10, 17, 27, 44, 72, 116, 188, 305, 493, 798, 1292, 2090, 3382, 5473, 8855, 14328, 23184, 37512, 60696, 98209, 158905, 257114, 416020, 673134, 1089154, 1762289, 2851443, 4613732, 7465176, 12078908, 19544084, 31622993, 51167077, 82790070, 133957148

Offset: 0

Author

N. J. A. Sloane, Dec 11 1996

Keywords

• nonn
• easy

Comments

Column sums of:

1 1 2 3 5 8 13 21 34 55...

1 1 2 3 5 8 13...

1 1 2 3...

1...

---------------------------

1 1 2 4 6 10 17 27 44 72...

This sequence counts partially ordered partitions of (n-3) into parts no greater than 3, where the position of the 1's and 2's is important. Alternatively, the position of the 3's is unimportant. (see example below). - David Neil McGrath, Apr 26 2015

Also the matching and vertex cover number of the (n-2)-Fibonacci cube graph. - Eric W. Weisstein, Sep 06 2017

Examples

			Partial Order of 6 into parts (1,2,3) with position of 3 unimportant. a(9)=17 These are (33),(321=231=213),(312=132=123),(3111=1311=1131=1113),(222),(2211),(2121),(2112),(1212),(1122),(1221),(21111),(12111),(11211),(11121),(11112),(111111). - _David Neil McGrath_, Apr 26 2015
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• H. Matsui et al., Problem B-1019, Fibonacci Quarterly, Vol. 45, Number 2; 2007; p. 182. [A related sequence.]
• Eric Weisstein's World of Mathematics, Fibonacci Cube Graph
• Eric Weisstein's World of Mathematics, Matching Number
• Eric Weisstein's World of Mathematics, Vertex Cover Number
• Index entries for linear recurrences with constant coefficients, signature (1,1,1,-1,-1).

Crossrefs

Cf. A036605, A027976, A081410.

Programs

Magma

[Floor(Fibonacci(n)/2): n in [0..60]]; // Vincenzo Librandi, Apr 23 2011

Maple

seq(iquo(fibonacci(n),2),n=0..36); # Zerinvary Lajos, Apr 20 2008
f:=proc(n) option remember; local t1; if n <= 2 then RETURN(1); fi: if n mod 3 = 1 then t1:=1 else t1:=0; fi: f(n-1)+f(n-2)+t1; end; [seq(f(n), n=1..100)]; # N. J. A. Sloane, May 25 2008

Mathematica

CoefficientList[Series[x^3 / ((1 - x^3) (1 - x - x^2)), {x, 0, 50}], x] (* Vincenzo Librandi, Jun 08 2013 *)
Floor[Fibonacci[Range[0, 50]]/2] (* Harvey P. Dale, Feb 15 2015 *)
LinearRecurrence[{1, 1, 1, -1, -1}, {0, 0, 0, 1, 1}, 50] (* Harvey P. Dale, Feb 15 2015 *)
Floor[Fibonacci[Range[0, 20]]/2] (* Eric W. Weisstein, Sep 06 2017 *)

PARI

a(n)=fibonacci(n)\2

Formula

G.f.: x^3/((1-x^3)*(1-x-x^2)). - Ralf Stephan, Jul 22 2003, corrected by Paul Barry

a(n) = Fibonacci(n)/2 - (1-cos(2Pi*n/3))/3. - Paul Barry, Oct 06 2003

From Paul Barry, Jan 14 2005: (Start)

a(n+2) = Sum_{k=0..floor(n/3)} F(n-3*k).

a(n+2) = Sum_{k=0..n} if(mod(n-k, 3)=0, F(k), 0). (End)

a(n+2) = Sum_{k=0..n} F(k)*(cos(2*Pi*(n-k)/3+Pi/3)/3+sqrt(3)*sin(2*Pi*(n-k)/3+Pi/3)/3+1/3). - Paul Barry, Apr 16 2005

a(n) = a(n-1)+a(n-2)+1 if n mod 3 = 0, else a(n) = a(n-1)+a(n-2). - Gary Detlefs, Dec 05 2010

a(n) = Fibonacci(n-2)+floor(Fibonacci(n-3)/2). - Gary Detlefs, Mar 28 2011

a(n) = (A000045(n) - A011655(n))/2.

a(n) = a(n-1)+a(n-2)+a(n-3)-a(n-4)-a(n-5), a(0)=0, a(1)=0, a(2)=0, a(3)=1, a(4)=1. - Carl Najafi, May 06 2014