The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A030186 a(n) = 3*a(n-1) + a(n-2) - a(n-3) for n >= 3, a(0)=1, a(1)=2, a(2)=7. 26
 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, 10159461285307, 32655756991442 (list; graph; refs; listen; history; text; 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, Jun 11 2003 Equivalently, ways of paving a 2 X n grid cells using only singletons and dominoes. - Lekraj Beedassy, 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, Oct 16 2006 Row sums of A046741. - Emeric Deutsch, Oct 16 2006 Equals binomial transform of A156096. - Gary W. Adamson, Feb 03 2009 a(n) = Lucas(2n) + Sum_{k=2..n-1} Fibonacci(2k-1)*a(n-k). This relationship can be proven by a visual proof using the idea of tiling a 2 X n board with only singletons and dominoes while conditioning on where the vertical dominoes first appear. If there are no vertical dominoes positioned at lengths 2 through n-1, there will be Lucas(2n) ways to tile the board since a complete tour around the board will be made possible. If the first vertical domino appears at length k (where 2 <= k <= n-1) there will be Fibonacci(2k-1)*a(n-k) ways to tile the board. - Rana Ürek, Jun 25 2018 REFERENCES Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 25. 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. LINKS Indranil Ghosh, Table of n, a(n) for n = 0..1968 (terms 0..200 from T. D. Noe) 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. Svenja Huntemann, Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019. INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 473 M. Katz, C. Stenson, Tiling a (2xn)-Board with Squares and Dominoes, JIS 12 (2009) 09.2.2, Table 1. David Friedhelm Kind, The Gunport Problem: An Evolutionary Approach, De Montfort University (Leicester, UK, 2020). Richard M. Low and Ardak Kapbasov, Non-Attacking Bishop and King Positions on Regular and Cylindrical Chessboards, Journal of Integer Sequences, Vol. 20 (2017), Article 17.6.1, Table 2. Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research report, No 12, 1996, Department of Math., Umea University, Sweden. Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998. R. B. McQuistan and S. J. Lichtman, Exact recursion relation for (2 × N) arrays of dumbbells, J. Math Phys. 11 (1970), 3095-3099. László Németh, Tilings of (2 X 2 X n)-board with colored cubes and bricks, arXiv:1909.11729 [math.CO], 2019. N. J. A. Sloane Notes on A030186 and A033505 Eric Weisstein's World of Mathematics, Independent Edge Set Eric Weisstein's World of Mathematics, Ladder Graph Eric Weisstein's World of Mathematics, Matching Yifan Zhang, George Grossman, A Combinatorial Proof for the Generating Function of Powers of a Second-Order Recurrence Sequence, J. Int. Seq. 21 (2018), #18.3.3. Index entries for linear recurrences with constant coefficients, signature (3,1,-1). FORMULA G.f.: (1-x)/(1-3*x-x^2+x^3). a(n) = ( (Sum_{k=0..n-1} a(k))^2 + (Sum_{k=0..n-1} a(k)^2) ) / a(n-1) for n>1 with a(0)=1, a(1)=2 (similar to A088016). - Paul D. Hanna, Nov 20 2012 MAPLE a[0]:=1: a[1]:=2: a[2]:=7: for n from 3 to 30 do a[n]:=3*a[n-1]+a[n-2]-a[n-3] od: seq(a[n], n=0..30); # Emeric Deutsch, Oct 16 2006 MATHEMATICA LinearRecurrence[{3, 1, -1}, {1, 2, 7}, 26] (* Robert G. Wilson v, Nov 20 2012 *) Table[RootSum[1 -# -3#^2 +#^3 &, 9#^n -10#^(n+1) +7#^(n+2) &]/74, {n, 0, 30}] (* Eric W. Weisstein, Oct 03 2017 *) CoefficientList[Series[(1-x)/(1-3x-x^2+x^3), {x, 0, 30}], x] (* Eric W. Weisstein, Oct 03 2017 *) 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 (PARI) {a(n)=if(n==0, 1, if(n==1, 2, (sum(k=0, n-1, a(k))^2+sum(k=0, n-1, a(k)^2))/a(n-1)))} \\ Paul D. Hanna, Nov 20 2012 (Sage) def A030186_list(prec):     P. = PowerSeriesRing(ZZ, prec)     return P((1-x)/(1-3*x-x^2+x^3)).list() A030186_list(30) # G. C. Greubel, Sep 27 2019 (GAP) a:=[1, 2, 7];; for n in [4..30] do a[n]:=3*a[n-1]+a[n-2]-a[n-3]; od; a; # G. C. Greubel, Sep 27 2019 CROSSREFS Partial sums give A033505. Column 2 of triangle A210662. Cf. A054894, A055518, A055519, A088016. Cf. A156096. - Gary W. Adamson, Feb 03 2009 Bisection (even part) gives A260033. Sequence in context: A291382 A109999 A092690 * A289592 A292230 A162770 Adjacent sequences:  A030183 A030184 A030185 * A030187 A030188 A030189 KEYWORD nonn,easy,nice,changed AUTHOR Ottavio D'Antona (dantona(AT)dsi.unimi.it) EXTENSIONS More terms from James A. Sellers Entry revised by N. J. A. Sloane, Feb 13 2002 STATUS approved

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

Last modified May 17 23:07 EDT 2022. Contains 353779 sequences. (Running on oeis4.)