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

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A079472 Number of perfect matchings on an n X n L-shaped graph. 13
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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

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

I. Gutman and S. J. Cyvin, A result on 1-factors related to Fibonacci numbers, The Fibonacci Quarterly, 28 (1990), pp. 81-84.

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

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/((x+1)*(x^2-3*x+1)). (End)

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

a(n) = F(n+1)^2 - F(n)^2 - F(n-1)^2. a(1 - n) = -a(n). - Michael Somos, Jun 28 2014

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

EXAMPLE

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 + ...

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, 1, 50}] (* Vincenzo Librandi, Jun 29 2014 *)

PROG

(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

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

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

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

CROSSREFS

Cf. A001654, A121646.

Sequence in context: A048618 A083554 A059412 * A308556 A148186 A006948

Adjacent sequences:  A079469 A079470 A079471 * A079473 A079474 A079475

KEYWORD

easy,nonn

AUTHOR

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

EXTENSIONS

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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 22 10:25 EST 2020. Contains 331144 sequences. (Running on oeis4.)