A068921 Number of ways to tile a 2 X n room with 1x2 Tatami mats. At most 3 Tatami mats may meet at a point.

1, 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745, 4023, 5896, 8641, 12664, 18560, 27201, 39865, 58425, 85626, 125491, 183916, 269542, 395033, 578949, 848491, 1243524, 1822473, 2670964, 3914488, 5736961

Offset

0,3

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).

D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 10.

R. J. Mathar, Paving rectangular regions with rectangular tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 1.

Index entries for linear recurrences with constant coefficients, signature (1,0,1).

Formula

For n >= 3, a(n) = a(n-1) + a(n-3).

a(n) = A000930(n+1).

From Frank Ruskey, Jun 07 2009: (Start)

G.f.: (1+x^2)/(1-x-x^3).

a(n) = sum( binomial(n-2j+1,j), j=0..floor(n/2) ). (End)

G.f.: Q(0)*( 1+x^2 )/2, where Q(k) = 1 + 1/(1 - x*(4*k+1 + x^2)/( x*(4*k+3 + x^2) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 08 2013

Mathematica

LinearRecurrence[{1, 0, 1}, {1, 1, 2}, 42] (* Robert G. Wilson v, Jul 12 2014 *)

Prog

(PARI) my(x='x+O('x^50)); Vec((1+x^2)/(1-x-x^3)) \\ G. C. Greubel, Apr 26 2017

Crossrefs

Cf. A068927 for incongruent tilings, A068920 for more info.

Cf. A000930, A078012, first column of A272471.

Sequence in context: A247083 A159848 A017826 * A000930 A078012 A135851

Adjacent sequences: A068918 A068919 A068920 * A068922 A068923 A068924

Keyword

nonn,easy

Author

Dean Hickerson, Mar 11 2002

Status

approved