login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

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. 24
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; 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 2xn 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

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.

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.

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.

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-3x-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 25 do a[n]:=3*a[n-1]+a[n-2]-a[n-3] od: seq(a[n], n=0..25); # 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, 20}] (* Eric W. Weisstein, Oct 03 2017 *)

CoefficientList[Series[(1 - x)/(1 - 3 x - x^2 + x^3), {x, 0, 20}], 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

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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 18 06:35 EST 2018. Contains 318215 sequences. (Running on oeis4.)