|
%I #76 Nov 03 2023 17:01:09
%S 0,2,4,12,30,80,208,546,1428,3740,9790,25632,67104,175682,459940,
%T 1204140,3152478,8253296,21607408,56568930,148099380,387729212,
%U 1015088254,2657535552,6957518400,18215019650,47687540548,124847601996,326855265438,855718194320
%N Number of perfect matchings on an n X n L-shaped graph.
%C a(n+1) = 2*F(n)*F(n+1) appears as the second component of the square of [F(n), F(n+1), F(n+2), F(n+3)], for n >= 0, with F(n) = A000045(n), in the Clifford algebra Cl_2 over Euclidean 2-space. The whole quartet of sequences for this square is [-A248161(n), a(n+1), A059929(n), A121801(n+1)]. See the Oct 15 2014 comment in A147973 where also a reference is given. - _Wolfdieter Lang_, Nov 01 2014
%C a(n+1) is the numerator of the continued fraction [1,...,1,2,1,...,1] with n 1's to the left of the central 2, and n 1's to the right of the central 2. For the denominators, see A061646. - _Greg Dresden_ and Max Liu, Jun 25 2023
%C For n >= 3, a(n) equals the sum of the sides of the right triangle with side lengths [(F(n)*F(n-3), 2*F(n-1)*F(n-2), F(2*n-3)] (n = 4 corresponds to the 3-4-5 right triangle). - _Peter Bala_, Nov 03 2023
%D Daniele Corradetti, La Metafisica del Numero, 2008
%D G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. pp. 178, 255.
%H Vincenzo Librandi, <a href="/A079472/b079472.txt">Table of n, a(n) for n = 1..1000</a>
%H P. F. F. Espinosa, J. F. González, J. P. Herrán, A. M. Cañadas, and J. L. Ramírez, <a href="https://doi.org/10.12958/adm1663">On some relationships between snake graphs and Brauer configuration algebras</a>, Algebra Disc. Math. (2022) Vol. 33, No. 2, 29-59.
%H I. Gutman and S. J. Cyvin, <a href="http://www.fq.math.ca/Scanned/28-1/gutman.pdf">A result on 1-factors related to Fibonacci numbers</a>, The Fibonacci Quarterly, 28 (1990), pp. 81-84.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,2,-1).
%F a(n) = 2*F(n)*F(n-1) where F(n) are the Fibonacci numbers (A000045).
%F From Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Jan 18 2003: (Start)
%F a(n) = 2*A001654(n) = F(2*n) - F(n)^2 = A001906(n) - A007598(n).
%F a(n) = (F(n+1)^2 - F(n-2)^2)/2 = (A007598(n+1) - A007598(n-2))/2.
%F a(n) = 2*(L(2*n-1) + (-1)^n)/5 = (2/5)*(A002878(n-1) + A033999(n)), where L(n) = A000032(n).
%F a(n+1) = a(n) + 2*F(n)^2.
%F G.f.: 2*x^2/((1+x)*(1-3*x+x^2)). (End)
%F a(n) = Im( (F(n) + i*F(n+1))^2 ) (cf. A121646). - Daniele Corradetti (d.corradetti(AT)gmail.com), May 02 2008
%F From _Michael Somos_, Jun 28 2014: (Start)
%F a(n) = F(n+1)^2 - F(n)^2 - F(n-1)^2.
%F a(1 - n) = -a(n). (End)
%F a(n) = ( 2*(-1)^n - (1+sqrt(5))*((3-sqrt(5))/2)^n - (1-sqrt(5))*((3+sqrt(5))/2)^n )/5. - _Colin Barker_, Sep 27 2016
%F From _Rigoberto Florez_, May 06 2020: (Start)
%F a(n) = F(2n-2) + F(n-1)^2, where F(n) is the n-th Fibonacci number.
%F a(n) = M^(n+1)[2,1], for n>0 where M=[0,0,1;0,1,2;1,1,1]. (End)
%F a(n) = F(n)^2 + F(n-1)^2 - F(n-2)^2. - _Michael Somos_, Mar 02 2023
%e a(7) = 2*13*8 = 208 = number of matchings. F(7) = 13 F(6) = 8
%e a(3) = 4 because in the graph with vertex set {(0,0), (1,0), (2,0), (0,1), (1,1), (2,1), (0,2), (1,2)} and edge set {h(0,0), h(1,0), h(0,1), h(1,1), h(0,2), v(0,0), v(0,1), v(1,0), v(1,1), v(2,0)}, where h(i,j) (v(i,j)) is a horizontal (vertical) edge of unit length starting from vertex (i,j), we have the following four perfect matchings: {h(0,0), h(0,1), h(0,2), v(2,0)}, {h(0,0), v(0,1), v(1,1), v(2,0)}, {v(0,0), v(1,0), v(2,0), h(0,2)} and {v(0,0), h(1,0), h(1,1), h(0,2)}. - _Emeric Deutsch_, Dec 30 2004
%e G.f. = 2*x^2 + 4*x^3 + 12*x^4 + 30*x^5 + 80*x^6 + 208*x^7 + 546*x^8 + ...
%p with(combinat,fibonacci):seq(2*fibonacci(n)*fibonacci(n-1),n=1..30);
%t LinearRecurrence[{2,2,-1}, {0,2,4}, 30] (* _Arkadiusz Wesolowski_, Sep 15 2012 *)
%t Table[(2*Fibonacci[n]*Fibonacci[n-1]), {n,30}] (* _Vincenzo Librandi_, Jun 29 2014 *)
%o (PARI) {a(n) = 2 * fibonacci(n) * fibonacci(n-1)}; \\ _Michael Somos_, Jun 28 2014
%o (PARI) concat(0, Vec(2*x^2/((x+1)*(x^2-3*x+1)) + O(x^40))) \\ _Colin Barker_, Sep 27 2016
%o (Magma) [2*Fibonacci(n)*Fibonacci(n-1): n in [1..30]]; // _Vincenzo Librandi_, Jun 29 2014
%o (Sage) [2*fibonacci(n-1)*fibonacci(n) for n in (1..30)] # _G. C. Greubel_, Jan 07 2019
%o (GAP) List([1..30], n -> 2*Fibonacci(n-1)*Fibonacci(n)); # _G. C. Greubel_, Jan 07 2019
%Y Cf. A001654, A121646.
%K easy,nonn
%O 1,2
%A Helen King (h.king(AT)uea.ac.uk), Jan 15 2003
%E More terms from _Benoit Cloitre_ and Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Jan 18 2003
|
