|
|
A068397
|
|
a(n) = Lucas(n) + (-1)^n + 1.
|
|
13
|
|
|
1, 5, 4, 9, 11, 20, 29, 49, 76, 125, 199, 324, 521, 845, 1364, 2209, 3571, 5780, 9349, 15129, 24476, 39605, 64079, 103684, 167761, 271445, 439204, 710649, 1149851, 1860500, 3010349, 4870849, 7881196, 12752045, 20633239, 33385284, 54018521, 87403805
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Number of domino tilings of a 2 X n strip on a cylinder.
Number of domino tilings of a 2 X n rectangle = Fibonacci(n) - see A000045.
Number of perfect matchings in the C_n X P_2 graph (C_n is the cycle graph on n vertices and P_2 is the path graph on 2 vertices). - Emeric Deutsch, Dec 29 2004
For n >= 3, also the number of maximum independent edge sets (matchings) in the n-prism graph. - Eric W. Weisstein, Mar 30 2017
For n >= 4, also the number of minimum clique coverings in the n-prism graph. - Eric W. Weisstein, May 03 2017
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Matching
|
|
FORMULA
|
a(n) = F(n+1) + F(n-1) + 2 if n is even, a(n) = F(n+1) + F(n-1) if n is odd, where F(n) is the n-th Fibonacci number - sequence A000045.
a(n) = 1 + (-1)^n + ((1 + sqrt(5))/2)^n + ((1 - sqrt(5))/2)^n = 1 + (-1)^n + A000032(n). - Vladeta Jovovic, Apr 08 2002
Recurrence: a(n) = a(n-1) + 2*a(n-2) - a(n-3) - a(n-4). - Vladeta Jovovic, Apr 08 2002
a(n+2) = a(n+1) + a(n) if n even, a(n+2) = a(n+1) + a(n) + 2 if n odd. - Michael Somos, Jan 28 2017
a(1) = 1, a(2) = 5; a(n) = a(n-1) + a(n-2) - 2*(n mod 2). [Belcastro]
G.f.: x*(1 + 4*x - 3*x^2 - 4*x^3)/(1 - x - 2*x^2 + x^3 + x^4). - Vladeta Jovovic, Apr 08 2002
a(n) = ((1 + sqrt(5))/2)^n + ((1 - sqrt(5))/2)^n + 1 + (-1)^n. [Hosoya/Harary]
E.g.f.: exp(-x/phi) + exp(phi*x) + 2*cosh(x) - 4, where phi is the golden ratio. - Ilya Gutkovskiy, Jun 16 2016
|
|
EXAMPLE
|
G.f. = 5*x^2 + 4*x^3 + 9*x^4 + 11*x^5 + 20*x^6 + 29*x^7 + 49*x^8 + 76*x^9 + ...
Example: a(3)=4 because in the graph with vertex set {A,B,C,A',B',C'} and edge set {AB,AC,BC, A'B',A'C',B'C',AA',BB',CC'} we have the following perfect matchings: {AA',BC,B'C'}, {BB',AC,A'C'}, {CC',AB,A'B'} and {AA',BB',CC'}.
|
|
MAPLE
|
a[2]:=5: a[3]:=4: a[4]:=9: a[5]:=11: for n from 6 to 45 do a[n]:=a[n-1]+2*a[n-2]-a[n-3]-a[n-4] od:seq(a[n], n=2..40); # Emeric Deutsch, Dec 29 2004
f:= n -> combinat:-fibonacci(n-1)+combinat:-fibonacci(n+1)+(-1)^n+1:
|
|
MATHEMATICA
|
LinearRecurrence[{1, 2, -1, -1}, {1, 5, 4, 9}, 20] (* Eric W. Weisstein, Dec 31 2017 *)
CoefficientList[Series[(1 + 4 x - 3 x^2 - 4 x^3)/(1 - x - 2 x^2 + x^3 + x^4), {x, 0, 20}], x]
|
|
PROG
|
(PARI) a(n)=([0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1; -1, -1, 2, 1]^(n-1)*[1; 5; 4; 9])[1, 1] \\ Charles R Greathouse IV, Jun 19 2016
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
Sharon Sela (sharonsela(AT)hotmail.com), Mar 30 2002
|
|
EXTENSIONS
|
Two initial terms added, third comment amended to be consonant with new initial terms, offset changed to be consonant with initial terms, two references added, two formulas added. - Sarah-Marie Belcastro, Jul 04 2009
Edited by N. J. A. Sloane, Jan 10 2018 to incorporate information from a duplicate (but now dead) entry.
|
|
STATUS
|
approved
|
|
|
|