login
A004695
a(n) = floor(Fibonacci(n)/2).
21
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,6
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
LINKS
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
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
EXAMPLE
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
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 *)
PROG
(PARI) a(n)=fibonacci(n)\2
(Magma) [Floor(Fibonacci(n)/2): n in [0..60]]; // Vincenzo Librandi, Apr 23 2011
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, Dec 11 1996
STATUS
approved