A079472 Number of perfect matchings on an n X n L-shaped graph.

0, 2, 4, 12, 30, 80, 208, 546, 1428, 3740, 9790, 25632, 67104, 175682, 459940, 1204140, 3152478, 8253296, 21607408, 56568930, 148099380, 387729212, 1015088254, 2657535552, 6957518400, 18215019650, 47687540548, 124847601996, 326855265438, 855718194320

Offset: 1

Author

Helen King (h.king(AT)uea.ac.uk), Jan 15 2003

Keywords

• easy
• nonn

Comments

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

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

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

Examples

			a(7) = 2*13*8 = 208 = number of matchings. F(7) = 13 F(6) = 8
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
G.f. = 2*x^2 + 4*x^3 + 12*x^4 + 30*x^5 + 80*x^6 + 208*x^7 + 546*x^8 + ...
		

References

• Daniele Corradetti, La Metafisica del Numero, 2008.
• G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. pp. 178, 255.

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1..1000
• P. F. F. Espinosa, J. F. González, J. P. Herrán, A. M. Cañadas, and J. L. Ramírez, On some relationships between snake graphs and Brauer configuration algebras, Algebra Disc. Math. (2022) Vol. 33, No. 2, 29-59.
• I. Gutman and S. J. Cyvin, A result on 1-factors related to Fibonacci numbers, The Fibonacci Quarterly, 28 (1990), pp. 81-84.
• C.-A. Laisant, Observations sur les triangles rectangles en nombres entiers et les suites de Fibonacci, Nouvelles Annales de Math. (1919, in French) Series 4, Vol. 19, 391-397.
• Index entries for linear recurrences with constant coefficients, signature (2,2,-1).

Crossrefs

Cf. A001654, A121646.

Programs

GAP

List([1..30], n -> 2*Fibonacci(n-1)*Fibonacci(n)); # G. C. Greubel, Jan 07 2019

Magma

[2*Fibonacci(n)*Fibonacci(n-1): n in [1..30]]; // Vincenzo Librandi, Jun 29 2014

Maple

with(combinat,fibonacci):seq(2*fibonacci(n)*fibonacci(n-1),n=1..30);

Mathematica

LinearRecurrence[{2,2,-1}, {0,2,4}, 30] (* Arkadiusz Wesolowski, Sep 15 2012 *)
Table[(2*Fibonacci[n]*Fibonacci[n-1]), {n,30}] (* Vincenzo Librandi, Jun 29 2014 *)

PARI

{a(n) = 2 * fibonacci(n) * fibonacci(n-1)}; \\ Michael Somos, Jun 28 2014

PARI

concat(0, Vec(2*x^2/((x+1)*(x^2-3*x+1)) + O(x^40))) \\ Colin Barker, Sep 27 2016

Sage

[2*fibonacci(n-1)*fibonacci(n) for n in (1..30)] # G. C. Greubel, Jan 07 2019

Formula

a(n) = 2*F(n)*F(n-1) where F(n) are the Fibonacci numbers (A000045).

From Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Jan 18 2003: (Start)

a(n) = 2*A001654(n) = F(2*n) - F(n)^2 = A001906(n) - A007598(n).

a(n) = (F(n+1)^2 - F(n-2)^2)/2 = (A007598(n+1) - A007598(n-2))/2.

a(n) = 2*(L(2*n-1) + (-1)^n)/5 = (2/5)*(A002878(n-1) + A033999(n)), where L(n) = A000032(n).

a(n+1) = a(n) + 2*F(n)^2.

G.f.: 2*x^2/((1+x)*(1-3*x+x^2)). (End)

a(n) = Im( (F(n) + i*F(n+1))^2 ) (cf. A121646). - Daniele Corradetti (d.corradetti(AT)gmail.com), May 02 2008

From Michael Somos, Jun 28 2014: (Start)

a(n) = F(n+1)^2 - F(n)^2 - F(n-1)^2.

a(1 - n) = -a(n). (End)

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

From Rigoberto Florez, May 06 2020: (Start)

a(n) = F(2n-2) + F(n-1)^2, where F(n) is the n-th Fibonacci number.

a(n) = M^(n+1)[2,1], for n>0 where M=[0,0,1;0,1,2;1,1,1]. (End)

a(n) = F(n)^2 + F(n-1)^2 - F(n-2)^2. - Michael Somos, Mar 02 2023

Extensions

More terms from Benoit Cloitre and Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Jan 18 2003