A033505 Expansion of 1/(1 - 3*x - x^2 + x^3).

1, 3, 10, 32, 103, 331, 1064, 3420, 10993, 35335, 113578, 365076, 1173471, 3771911, 12124128, 38970824, 125264689, 402640763, 1294216154, 4160024536, 13371648999, 42980755379, 138153890600, 444070778180, 1427385469761, 4588073296863, 14747534582170

Offset: 0

Author

N. J. A. Sloane, Feb 13 2002

Keywords

• nonn
• easy

Comments

From Greg Dresden, Jun 25 2022: (Start)

a(n) is the number of ways to tile, with squares and dominoes, a 2 X n board with one extra space at the end. Here is the board for n=3:

___

|||_|_

|||_|_|

and here is one of the a(3)=32 possible tilings of this board:

___

| |||_

|||___|

(End)

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• 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 4.
• N. J. A. Sloane Notes on A030186 and A033505
• Index entries for linear recurrences with constant coefficients, signature (3,1,-1).

Crossrefs

Partial sums of A030186.

Programs

GAP

a:=[1,3,10];; for n in [4..30] do a[n]:=3*a[n-1]+a[n-2]-a[n-3]; od; a; # G. C. Greubel, Oct 14 2019

Magma

I:=[1,3,10]; [n le 3 select I[n] else 3*Self(n-1)+Self(n-2)-Self(n-3): n in [1..30]]; // Vincenzo Librandi, Aug 17 2018

Maple

seq(coeff(series(1/(1-3*x-x^2+x^3), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 14 2019

Mathematica

CoefficientList[Series[1/(1-3x-x^2+x^3), {x, 0, 30}], x] (* or *) LinearRecurrence[{3,1,-1}, {1,3,10}, 30] (* Vincenzo Librandi, Aug 17 2018 *)

PARI

my(x='x+O('x^30)); Vec(1/(1-3*x-x^2+x^3)) \\ G. C. Greubel, Oct 14 2019

Sage

def A033505_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P(1/(1-3*x-x^2+x^3)).list()
A033505_list(30) # G. C. Greubel, Oct 14 2019

Formula

a(n) = 3*a(n-1) + a(n-2) - a(n-3). - Greg Dresden, Aug 16 2018