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.

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

Offset: 0

Author

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

Keywords

• nonn
• easy
• nice

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).

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.

Programs

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

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

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 *)

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

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

Extensions

More terms from James Sellers

Entry revised by N. J. A. Sloane, Feb 13 2002