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