|
| |
|
|
A030186
|
|
a(n) = 3a(n-1) + a(n-2) - a(n-3), n >= 3; a(0) = 1, a(1) = 2, a(2) = 7.
|
|
20
| |
|
|
1, 2, 7, 22, 71, 228, 733, 2356, 7573, 24342, 78243, 251498, 808395, 2598440, 8352217, 26846696, 86293865, 277376074, 891575391, 2865808382, 9211624463, 29609106380, 95173135221, 305916887580, 983314691581, 3160687827102
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| 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
Equals binomial transform of A156096 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Feb 03 2009]
|
|
|
REFERENCES
| 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.
|
|
|
LINKS
| 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
|
|
|
FORMULA
| G.f.: (1-t)/(1-3t-t^2+t^3).
|
|
|
MAPLE
| 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
|
|
|
PROG
| (Haskell)
a030186 n = a030186_list !! n
a030186_list = 1 : 2 : 7 : zipWith (-) (tail $
zipWith (+) a030186_list $ tail $ map (* 3) a030186_list) a030186_list
-- Reinhard Zumkeller, Oct 20 2011
|
|
|
CROSSREFS
| Partial sums give A033505.
Cf. A054894, A055518, A055519.
A156096 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Feb 03 2009]
Sequence in context: A106438 A109999 A092690 * A162770 A116387 A114495
Adjacent sequences: A030183 A030184 A030185 * A030187 A030188 A030189
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| Ottavio D'Antona (dantona(AT)dsi.unimi.it)
|
|
|
EXTENSIONS
| More terms from James A. Sellers (sellersj(AT)math.psu.edu)
Entry revised by N. J. A. Sloane (njas(AT)research.att.com), Feb 13, 2002.
|
| |
|
|
