|
%I #104 Mar 22 2024 11:21:26
%S 1,2,7,22,71,228,733,2356,7573,24342,78243,251498,808395,2598440,
%T 8352217,26846696,86293865,277376074,891575391,2865808382,9211624463,
%U 29609106380,95173135221,305916887580,983314691581,3160687827102,10159461285307,32655756991442
%N a(n) = 3*a(n-1) + a(n-2) - a(n-3) for n >= 3, a(0)=1, a(1)=2, a(2)=7.
%C Number of matchings in ladder graph L_n = P_2 X P_n.
%C Cycle-path coverings of a family of digraphs.
%C 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
%C Equivalently, ways of paving a 2 X n grid cells using only singletons and dominoes. - _Lekraj Beedassy_, Mar 25 2005
%C 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
%C Row sums of A046741. - _Emeric Deutsch_, Oct 16 2006
%C Equals binomial transform of A156096. - _Gary W. Adamson_, Feb 03 2009
%C 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
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 25.
%D 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.
%H Indranil Ghosh, <a href="/A030186/b030186.txt">Table of n, a(n) for n = 0..1968</a> (terms 0..200 from T. D. Noe)
%H Ottavio M. D'Antona and Emanuele Munarini, <a href="https://doi.org/10.1006/aama.2000.0689">The Cycle-path Indicator Polynomial of a Digraph</a>, Advances in Applied Mathematics 25 (2000), 41-56.
%H Roger C. Grimson, <a href="https://doi.org/10.1063/1.1666624">Exact formulas for 2 x n arrays of dumbbells</a>, J. Math. Phys., 15 (1974), 214-216.
%H Svenja Huntemann and Neil A. McKay, <a href="https://arxiv.org/abs/1909.12419">Counting Domineering Positions</a>, arXiv:1909.12419 [math.CO], 2019.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=473">Encyclopedia of Combinatorial Structures 473</a>
%H Matt Katz and Catherine Stenson, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Stenson/stenson8.html"> Tiling a (2xn)-Board with Squares and Dominoes</a>, JIS 12 (2009) 09.2.2, Table 1.
%H David Friedhelm Kind, <a href="https://doi.org/10.13140/RG.2.2.11182.54086">The Gunport Problem: An Evolutionary Approach</a>, De Montfort University (Leicester, UK, 2020).
%H Richard M. Low and Ardak Kapbasov, <a href="https://www.emis.de/journals/JIS/VOL20/Low/low2.html">Non-Attacking Bishop and King Positions on Regular and Cylindrical Chessboards</a>, Journal of Integer Sequences, Vol. 20 (2017), Article 17.6.1, Table 2.
%H Per Hakan Lundow, <a href="http://www.theophys.kth.se/~phl/Text/1factors.pdf">Computation of matching polynomials and the number of 1-factors in polygraphs</a>, Research report, No 12, 1996, Department of Math., Umea University, Sweden.
%H Per Hakan Lundow, <a href="http://www.theophys.kth.se/~phl/Text/1factors2.ps.gz">Enumeration of matchings in polygraphs</a>, 1998.
%H Richmond B. McQuistan and S. J. Lichtman, <a href="https://doi.org/10.1063/1.1665098">Exact recursion relation for (2 × N) arrays of dumbbells</a>, J. Math Phys. 11 (1970), 3095-3099.
%H László Németh, <a href="https://arxiv.org/abs/1909.11729">Tilings of (2 X 2 X n)-board with colored cubes and bricks</a>, arXiv:1909.11729 [math.CO], 2019.
%H László Németh, <a href="https://arxiv.org/abs/2403.12159">Walks on tiled boards</a>, arXiv:2403.12159 [math.CO], 2024. See pp. 1, 7.
%H N. J. A. Sloane <a href="/A030186/a030186.txt">Notes on A030186 and A033505</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentEdgeSet.html">Independent Edge Set</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LadderGraph.html">Ladder Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching.html">Matching</a>
%H Yifan Zhang and George Grossman, <a href="https://www.emis.de/journals/JIS/VOL21/Zhang/zhang44.html">A Combinatorial Proof for the Generating Function of Powers of a Second-Order Recurrence Sequence</a>, J. Int. Seq. 21 (2018), #18.3.3.
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,1,-1).
%F G.f.: (1-x)/(1-3*x-x^2+x^3).
%F 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
%p 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
%t LinearRecurrence[{3,1,-1}, {1,2,7}, 26] (* _Robert G. Wilson v_, Nov 20 2012 *)
%t Table[RootSum[1 -# -3#^2 +#^3 &, 9#^n -10#^(n+1) +7#^(n+2) &]/74, {n, 0, 30}] (* _Eric W. Weisstein_, Oct 03 2017 *)
%t CoefficientList[Series[(1-x)/(1-3x-x^2+x^3), {x,0,30}], x] (* _Eric W. Weisstein_, Oct 03 2017 *)
%o (Haskell)
%o a030186 n = a030186_list !! n
%o a030186_list = 1 : 2 : 7 : zipWith (-) (tail $
%o zipWith (+) a030186_list $ tail $ map (* 3) a030186_list) a030186_list
%o -- _Reinhard Zumkeller_, Oct 20 2011
%o (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
%o (Sage)
%o def A030186_list(prec):
%o P.<x> = PowerSeriesRing(ZZ, prec)
%o return P((1-x)/(1-3*x-x^2+x^3)).list()
%o A030186_list(30) # _G. C. Greubel_, Sep 27 2019
%o (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
%Y Partial sums give A033505.
%Y Column 2 of triangle A210662.
%Y Cf. A054894, A055518, A055519, A088016.
%Y Cf. A156096. - _Gary W. Adamson_, Feb 03 2009
%Y Bisection (even part) gives A260033.
%K nonn,easy,nice
%O 0,2
%A Ottavio D'Antona (dantona(AT)dsi.unimi.it)
%E More terms from _James A. Sellers_
%E Entry revised by _N. J. A. Sloane_, Feb 13 2002
| 