A054894 -id:A054894 - cp's OEIS frontend

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

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

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

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.

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

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.

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

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

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

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

{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

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

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

More terms from James Sellers

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

A332862 Array read by antidiagonals: T(m,n) = number of placements of zero or more dominoes on the m X n grid where no two empty squares are horizontally adjacent.

Original entry on oeis.org

1, 1, 2, 2, 4, 3, 2, 11, 9, 5, 3, 25, 48, 25, 8, 4, 61, 172, 227, 64, 13, 5, 146, 731, 1427, 1054, 169, 21, 7, 351, 2976, 10388, 11134, 4921, 441, 34, 9, 844, 12039, 72751, 140555, 88733, 22944, 1156, 55, 12, 2028, 49401, 510779, 1693116, 1932067, 701926, 107017, 3025, 89

Offset: 1

Neil A. McKay, Feb 27 2020

By symmetry this is the same as the number of placements of zero or more dominoes on the n X m grid where no two empty squares are vertically adjacent.
The number of positions of m X n Domineering where horizontal (Right) has no moves, also called Right ends. Domineering is a game in which players take turns placing dominoes on a grid, one player placing vertically and the other horizontally until the player to place cannot place a domino.
All rows and columns are linear recurrences with constant coefficients. An upper bound on the order of the recurrence for columns is A005418(n+1), which is the number of binary words of length n up to reversal. An upper bound on the order of the recurrence for rows is A032120(m). This upper bound is exact for at least 1 <= m <= 6. - Andrew Howroyd, Feb 28 2020

			Table starts:
  ===================================================================
  m\n|  1    2      3       4         5           6             7
  ---|---------------------------------------------------------------
  1  |  1    1      2       2         3           4             5 ...
  2  |  2    4     11      25        61         146           351 ...
  3  |  3    9     48     172       731        2976         12039 ...
  4  |  5   25    227    1427     10388       72751        510779 ...
  5  |  8   64   1054   11134    140555     1693116      20414525 ...
  6  | 13  169   4921   88733   1932067    40008789     831347033 ...
  7  | 21  441  22944  701926  26425981   941088936   33656587715 ...
  8  | 34 1156 107017 5567467 362036629 22168654178 1365206879940 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..378
Bjorn Huntemann, Svenja Huntemann, Neil A. McKay, SageMath code for Counting Domineering Positions
Svenja Huntemann, Neil A. McKay, Counting Domineering Positions, arXiv:1909.12419 [math.CO], 2019.

Columns 1..3 are A000045, A007598, A054894.
Rows 1..2 are A000931(n + 5), A329707.
Main diagonal is A332865.
Cf. A288026 (the number of placements of dominoes on an m X n grid where no two empty squares are horizontally or vertically adjacent).
Cf. A005418, A032120.

\\ here R(n) is row 1 as vector.
R(n)={Vec((1+x+x^2)/(1-x^2-x^3)+O(x*x^n))}
F(b,r)={my(t=1); while(b, b=(b>>valuation(b,2))+1; my(s=valuation(b,2)); t*=r[s]; b>>=s+1); t}
step(v,f)={vector(#v, t, my(i=t-1); sum(j=0, #v-1, if(!bitand(i,j), v[1+j]*(f[#v-bitor(i,j)]))))}
T(m,n)={my(r=R(n), f=vector(2^n, i, F(i-1, r)), v=vector(2^n)); v[1]=1; for(k=2, m, v=step(v,f)); sum(j=0, #v-1, v[1+j]*f[#v-j])}
{for(m=1, 8, for(n=1, 8, print1(T(m,n), ", ")); print)} \\ Andrew Howroyd, Feb 28 2020

# See Bjorn Huntemann, Svenja Huntemann, Neil A. McKay link.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Haskell

Maple

Mathematica

PARI

Sage

Formula

Extensions

A055518 a_{k+1} = 6*a_k + 11*a_{k-1} - 19*a_{k-2} - 4*a_{k-3} + a_{k-4}, a_1=1, a_2=2, a_3=19, a_4=118, a_5=875.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A332862 Array read by antidiagonals: T(m,n) = number of placements of zero or more dominoes on the m X n grid where no two empty squares are horizontally adjacent.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Sage

A055519 a(n) = 9*a(n-1) + 33*a(n-2) - 76*a(n-3) - 33*a(n-4) + 9*a(n-5) + a(n-6), a(0)=a(1)=1, a(2)=2, a(3)=35, a(4)=312, a(5)=3779.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A055518 a_{k+1} = 6a_k + 11a_{k-1} - 19a_{k-2} - 4a_{k-3} + a_{k-4}, a_1=1, a_2=2, a_3=19, a_4=118, a_5=875.

A055519 a(n) = 9a(n-1) + 33a(n-2) - 76a(n-3) - 33a(n-4) + 9*a(n-5) + a(n-6), a(0)=a(1)=1, a(2)=2, a(3)=35, a(4)=312, a(5)=3779.