login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A068397 a(n) = Lucas(n) + (-1)^n + 1. 11
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

REFERENCES

S.-M. Belcastro, Tilings of 2 x n Grids on Surfaces, preprint. [Unpublished as of June 2016]

LINKS

Colin Barker, Table of n, a(n) for n = 2..1000

H. Hosoya and F. Harary, On the matching properties of three fence graphs, J. Math. Chem., 12(1993), 211-218.

H. Hosoya and A. Motoyama, An effective algorithm for obtaining polynomials for dimer statistics. Application of operator technique on the topological index to two- and three-dimensional rectangular and torus lattices, J. Math. Physics 26 (1985) 157-167 (eq. (21) and Table IV).

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

Index entries for linear recurrences with constant coefficients, signature (1,2,-1,-1)

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 Mod[n, 2]. (From 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

((1 + Sqrt(5))/2)^n + ((1 - Sqrt(5))/2)^n + 1 + (-1)^n. (from 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^2*(5-x-5*x^2-x^3) / ((1-x)*(1+x)*(1-x-x^2)) + O(x^30)) \\ Colin Barker, Jan 28 2017

CROSSREFS

Cf. A000032, A000045.

Cf. also A102079, A102091, A252054.

a(n) = A102079(n, n).

Sequence in context: A110617 A234356 A102081 * A236405 A022344 A046588

Adjacent sequences:  A068394 A068395 A068396 * A068398 A068399 A068400

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 18 01:20 EST 2018. Contains 317279 sequences. (Running on oeis4.)