0,2

Number of matchings in ladder graph L_n = P_2 X P_n

Cycle-path coverings of a family of digraphs.

a(n+1) = Fibonacci(n+1)^2 + Sum_{k=0..n} Fibonacci(k)^2*a(n-k) (with the offset convention Fibonacci(2)=2). - Barry Cipra (bcipra(AT)rconnect.com), Jun 11 2003

Equivalently, ways of paving a 2xn grid cells using only singletons and dominoes. - Lekraj Beedassy (blekraj(AT)yahoo.com), Mar 25 2005

It is easy to see that the g.f. for indecomposable tilings (pavings) i.e. those that cannot be split vertically into smaller tilings, is g=2x+3x^2+2x^3+2x^4+2x^5+...=x(2+x-x^2)/(1-x); then G.f.=1/(1-g)=(1-x)/(1-3x-x^2+x^3). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 16 2006

Row sums of A046741. - Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 16 2006

O. M. D'Antona and E. Munarini, The Cycle-path Indicator Polynomial of a Digraph, Advances in Applied Mathematics 25 (2000), 41-56.

R. C. Grimson, Exact formulas for 2 x n arrays of dumbbells, J. Math. Phys., 15 (1974), 214-216.

J. D. E. Konhauser et al., Which Way Did The Bicycle Go? Problem 140 "Count The Tilings" pp. 42; 180-1 Dolciani Math. Exp. No. 18 MAA Washington DC 1996.

Per Hakan Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research reports, No 12, 1996, Department of Mathematics, Umea University.

R. B. McQuistan and S. J. Lichtman, Exact recursion relation for 2 x N arrays of dumbbells, J. Math. Phys., 11 (1970), 3095-3099.

T. D. Noe, Table of n, a(n) for n=0..200

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 473

Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.

N. J. A. Sloane Notes on A030186 and A033505

G.f.: (1-t)/(1-3t-t^2+t^3).

a[0]:=1: a[1]:=2: a[2]:=7: for n from 3 to 25 do a[n]:=3*a[n-1]+a[n-2]-a[n-3] od: seq(a[n], n=0..25); - Emeric Deutsch (deutsch(AT)duke.poly.edu), Oct 16 2006

Partial sums give A033505.

Cf. A054894, A055518, A055519.

Adjacent sequences: A030183 A030184 A030185 this_sequence A030187 A030188 A030189

Sequence in context: A106438 A109999 A092690 this_sequence A116387 A114495 A137398

nonn,easy,nice

dantona(AT)dsi.unimi.it (Ottavio D'Antona)

More terms from James A. Sellers (sellersj(AT)math.psu.edu)

Entry revised by njas, Feb 13, 2002.