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)
Ottavio M. D'Antona and Emanuele Munarini, The Cycle-path Indicator Polynomial of a Digraph, Advances in Applied Mathematics 25 (2000), 41-56.
Roger C. Grimson, Exact formulas for 2 x n arrays of dumbbells, J. Math. Phys., 15 (1974), 214-216.
Svenja Huntemann and Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 473
Matt Katz and Catherine 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.
Richmond 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.
László Németh, Walks on tiled boards, arXiv:2403.12159 [math.CO], 2024. See pp. 1, 7.
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 and 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
# second Maple program:
a:= n-> (<<0|1|0>, <0|0|1>, <-1|1|3>>^(n+1))[3, 2]:
seq(a(n), n=0..30); # Alois P. Heinz, Nov 07 2024
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.<x> = 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. A156096. - Gary W. Adamson, Feb 03 2009
Bisection (even part) gives A260033.
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