|
%I #95 Nov 20 2023 00:05:08
%S 1,5,4,9,11,20,29,49,76,125,199,324,521,845,1364,2209,3571,5780,9349,
%T 15129,24476,39605,64079,103684,167761,271445,439204,710649,1149851,
%U 1860500,3010349,4870849,7881196,12752045,20633239,33385284,54018521,87403805
%N a(n) = Lucas(n) + (-1)^n + 1.
%C Number of domino tilings of a 2 X n strip on a cylinder.
%C Number of domino tilings of a 2 X n rectangle = Fibonacci(n) - see A000045.
%C 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
%C For n >= 3, also the number of maximum independent edge sets (matchings) in the n-prism graph. - _Eric W. Weisstein_, Mar 30 2017
%C For n >= 4, also the number of minimum clique coverings in the n-prism graph. - _Eric W. Weisstein_, May 03 2017
%H Colin Barker, <a href="/A068397/b068397.txt">Table of n, a(n) for n = 1..1000</a> (corrected by Michel Marcus, Jan 19 2019)
%H Cate S. Anstöter, Nino Bašić, Patrick W. Fowler, and Tomaž Pisanski, <a href="https://arxiv.org/abs/2104.13290">Catacondensed Chemical Hexagonal Complexes: A Natural Generalisation of Benzenoids</a>, arXiv:2104.13290 [physics.chem-ph], 2021.
%H M. Baake, J. Hermisson, and P. Pleasants, <a href="http://dx.doi.org/10.1088/0305-4470/30/9/016">The torus parametrization of quasiperiodic LI-classes</a> J. Phys. A 30 (1997), no. 9, 3029-3056. See Table 3.
%H Sarah-Marie Belcastro, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL26/Belcastro/belcastro4.html">Domino Tilings of 2 X n Grids (or Perfect Matchings of Grid Graphs) on Surfaces</a>, J. Integer Seq. 26 (2023), Article 23.5.6.
%H H. Hosoya and F. Harary, <a href="http://dx.doi.org/10.1007/BF01164636">On the matching properties of three fence graphs</a>, J. Math. Chem., 12(1993), 211-218.
%H H. Hosoya and A. Motoyama, <a href="http://dx.doi.org/10.1063/1.526778">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</a>, J. Math. Physics 26 (1985) 157-167 (eq. (21) and Table IV).
%H B. Myers, <a href="http://doi.org/10.1109/TCT.1971.1083273">Number of spanning trees in a wheel</a>, IEE Trans. Circuit Theo. 18 (2) (1971) 280-282, Table 1.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CliqueCovering.html">Clique Covering</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching.html">Matching</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximumIndependentEdgeSet.html">Maximum Independent Edge Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimumEdgeCover.html">Minimum Edge Cover</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrismGraph.html">Prism Graph</a>
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (1,2,-1,-1).
%F 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.
%F 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
%F Recurrence: a(n) = a(n-1) + 2*a(n-2) - a(n-3) - a(n-4). - _Vladeta Jovovic_, Apr 08 2002
%F 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
%F a(1) = 1, a(2) = 5; a(n) = a(n-1) + a(n-2) - 2*(n mod 2). [Belcastro]
%F 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
%F a(n) = ((1 + sqrt(5))/2)^n + ((1 - sqrt(5))/2)^n + 1 + (-1)^n. [Hosoya/Harary]
%F E.g.f.: exp(-x/phi) + exp(phi*x) + 2*cosh(x) - 4, where phi is the golden ratio. - _Ilya Gutkovskiy_, Jun 16 2016
%e 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 + ...
%e 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'}.
%p 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
%p f:= n -> combinat:-fibonacci(n-1)+combinat:-fibonacci(n+1)+(-1)^n+1:
%p map(f, [$1..50]); # _Robert Israel_, May 03 2017
%t Table[LucasL[n] + (-1)^n + 1, {n, 1, 38}] (* _Jean-François Alcover_, Sep 01 2011 *)
%t LucasL[#] + (-1)^# + 1 &[Range[38]] (* _Eric W. Weisstein_, May 03 2017 *)
%t LinearRecurrence[{1, 2, -1, -1}, {1, 5, 4, 9}, 20] (* _Eric W. Weisstein_, Dec 31 2017 *)
%t CoefficientList[Series[(1 + 4 x - 3 x^2 - 4 x^3)/(1 - x - 2 x^2 + x^3 + x^4), {x, 0, 20}], x]
%o (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
%o (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
%Y Cf. A000032, A000045.
%Y Cf. also A102079, A102091, A252054.
%Y a(n) = A102079(n, n).
%K nonn,easy
%O 1,2
%A Sharon Sela (sharonsela(AT)hotmail.com), Mar 30 2002
%E More terms from _Vladeta Jovovic_, Apr 08 2002
%E 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
%E Edited by _N. J. A. Sloane_, Jan 10 2018 to incorporate information from a duplicate (but now dead) entry.
|
