login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A079472 Number of perfect matchings on an n X n L-shaped graph. 13

%I

%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

%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 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/((x+1)*(x^2-3*x+1)). (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 a(n) = F(n+1)^2 - F(n)^2 - F(n-1)^2. a(1 - n) = -a(n). - _Michael Somos_, Jun 28 2014

%F a(n) = (2^(-n)*((-1)^n*2^(1+n) - (3-sqrt(5))^n*(1+sqrt(5)) + (-1+sqrt(5))*(3+sqrt(5))^n))/5. - _Colin Barker_, Sep 27 2016

%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, 1, 50}] (* _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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 19 22:04 EST 2020. Contains 332060 sequences. (Running on oeis4.)