login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
Colin Barker, Table of n, a(n) for n = 1..1000 (corrected by Michel Marcus, Jan 19 2019)
Cate S. Anstöter, Nino Bašić, Patrick W. Fowler, and Tomaž Pisanski, Catacondensed Chemical Hexagonal Complexes: A Natural Generalisation of Benzenoids, arXiv:2104.13290 [physics.chem-ph], 2021.
M. Baake, J. Hermisson, and P. Pleasants, The torus parametrization of quasiperiodic LI-classes J. Phys. A 30 (1997), no. 9, 3029-3056. See Table 3.
Sarah-Marie Belcastro, Domino Tilings of 2 X n Grids (or Perfect Matchings of Grid Graphs) on Surfaces, J. Integer Seq. 26 (2023), Article 23.5.6.
H. Hosoya and F. Harary, On the matching properties of three fence graphs, J. Math. Chem., 12(1993), 211-218.
B. Myers, Number of spanning trees in a wheel, IEE Trans. Circuit Theo. 18 (2) (1971) 280-282, Table 1.
Eric Weisstein's World of Mathematics, Clique Covering
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set
Eric Weisstein's World of Mathematics, Minimum Edge Cover
Eric Weisstein's World of Mathematics, Prism Graph
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:
map(f, [$1..50]); # Robert Israel, May 03 2017
MATHEMATICA
Table[LucasL[n] + (-1)^n + 1, {n, 1, 38}] (* Jean-François Alcover, Sep 01 2011 *)
LucasL[#] + (-1)^# + 1 &[Range[38]] (* Eric W. Weisstein, May 03 2017 *)
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
(PARI) Vec(x*(1+4*x-3*x^2-4*x^3)/(1-x-2*x^2+x^3+x^4) + O(x^40)) \\ Colin Barker, Jan 28 2017; Michel Marcus, Jan 19 2019
CROSSREFS
Cf. also A102079, A102091, A252054.
a(n) = A102079(n, n).
Sequence in context: A234356 A338502 A102081 * A236405 A022344 A046588
KEYWORD
nonn,easy
AUTHOR
Sharon Sela (sharonsela(AT)hotmail.com), Mar 30 2002
EXTENSIONS
More terms from Vladeta Jovovic, Apr 08 2002
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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:56 EDT 2024. Contains 370952 sequences. (Running on oeis4.)