A272471 -id:A272471 - cp's OEIS frontend

A068921 Number of ways to tile a 2 X n room with 1 X 2 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

Dean Hickerson, Mar 11 2002

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).
Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 10.
Richard J. Mathar, Paving rectangular regions with rectangular tiles: Tatami and Non-Tatami Tilings, arXiv:1311.6135 [math.CO], 2013, Table 1.
Richard J. Mathar, Bivariate Generating Functions Enumerating Non-Bonding Dominoes on Rectangular Boards, arXiv:2404.18806 [math.CO], 2024. See p. 7.
Index entries for linear recurrences with constant coefficients, signature (1,0,1).

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

Cf. A000930, A078012, first column of A272471.

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

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

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_{j=0..floor(n/2)} binomial(n-2j+1, j). (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

A272472 Triangle T(n,m) by rows: The number of tatami tilings of a 3 by n grid with dimers and m monomers.

Original entry on oeis.org

0, 2, 0, 1, 3, 0, 9, 0, 1, 0, 10, 0, 12, 4, 0, 27, 0, 13, 0, 18, 0, 56, 0, 16, 6, 0, 75, 0, 97, 0, 18, 0, 38, 0, 198, 0, 152, 0, 18, 10, 0, 177, 0, 433, 0, 214, 0, 18, 0, 72, 0, 570, 0, 836, 0, 282, 0, 18, 16, 0, 393, 0, 1517, 0, 1442, 0, 354, 0, 18, 0, 136

Offset: 1

R. J. Mathar, Apr 30 2016

			The triangle starts in row n=1 and column m=0 as:
0,2,0,1;
3,0,9,0,1;
0,10,0,12;
4,0,27,0,13;
0,18,0,56,0,16;
6,0,75,0,97,0,18;
0,38,0,198,0,152,0,18;
10,0,177,0,433,0,214,0,18;
0,72,0,570,0,836,0,282,0,18;
16,0,393,0,1517,0,1442,0,354,0,18;
0,136,0,1478,0,3472,0,2292,0,426,0,18;
26,0,829,0,4571,0,7052,0,3410,0,498,0,18;
0,250,0,3554,0,12070,0,13076,0,4808,0,570,0,18;
42,0,1691,0,12479,0,28158,0,22480,0,6494,0,642,0,18;
0,454,0,8108,0,37222,0,59530,0,36308,0,8468,0,714,0,18;
68,0,3359,0,31729,0,97766,0,115948,0,55672,0,10730,0,786,0,18;
0,814,0,17768,0,105238,0,231622,0,210880,0,81708,0,13280,0,858,0,18;
110,0,6537,0,76483,0,306606,0,503348,0,361878,0,115568,0,16118,0,930,0,18;
0,1446,0,37736,0,278626,0,803060,0,1016880,0,590846,0,158404,0,19244,0,1002,0,18;
178,0,12511,0,176833,0,889916,0,1923278,0,1929730,0,924216,0,211368,0,22658,0,1074,0,18;
0,2548,0,78144,0,700670,0,2549216,0,4268026,0,3469042,0,1392996,0,275612,0,26360,0,1146,0,18;
288,0,23617,0,395387,0,2430464,0,6661414,0,8867630,0,5948792,0,2032802,0,352288,0,30350,0,1218,0,18;
0,4460,0,158492,0,1690478,0,7547920,0,16089358,0,17395888,0,9787628,0,2883858,0,442548,0,34628,0,1290,0,18;
466,0,44067,0,860069,0,6319840,0,21344172,0,36292416,0,32446518,0,15527142,0,3990996,0,547544,0,39194,0,1362,0,18;

A. Erickson, F. Ruskey, J. Woodcock, M. Schurch, Auspicious tatami mat arrangements, arXiv:1103.3309 (2011).

Cf. A180970 (row sums), A068922 (column m=0), A271786 (column m=1), A272471 (2 by n grid), A100245 (row reversed without tatami condition).

G.f. x *(x^4*y^3 +7*x*y^2 +3*x +2*y +y^3 +x^6*y +3*x^2*y -x^3*y^2 -6*x^4*y -x^2*y^5 +x^2*y^3 +y^3*x^6 -2*y^4*x^5 -2*x^3 -2*x^5 +y^5*x^4 -x^3*y^4 -x^5*y^2 +x^7) / (x^6 +x^5*y -2*x^4*y^2 -2*x^2 -x*y +1). - R. J. Mathar, May 01 2016

A180965 Number of tatami tilings of a 2 X n grid (with monomers allowed).

Original entry on oeis.org

1, 2, 6, 13, 29, 68, 156, 357, 821, 1886, 4330, 9945, 22841, 52456, 120472, 276681, 635433, 1459354, 3351598, 7697381, 17678037, 40599916, 93242996, 214144685, 491811165, 1129508406, 2594063186, 5957604017, 13682413681, 31423445328, 72168035504, 165743294353

Offset: 0

Frank Ruskey, Sep 29 2010

nonn

A tatami tiling consists of dimers (1 x 2) and monomers (1 x 1) where no four meet at a point.

Also, a(n) is the number of permutations of 1, ..., n+1 such that i can go to j only if |i-j| <= 2 and such that the pattern cdab (two consecutive pairs of elements swap position) is explicitly forbidden. - Jean M. Morales, Jun 02 2013

			Below we show the a(3) = 13 tatami tilings of a 2 X 3 rectangle where v = square of a vertical dimer, h = square of a horizontal dimer, m = monomer:
vvv vhh vmm vhh vmv vvm hhv hhm hhv mvv mhh mmv mvm
vvv vhh vhh vmm vmv vvm hhv mhh mmv mvv hhm hhv mvm

A.H.M. Smeets, Table of n, a(n) for n = 0..2770
A. Erickson, F. Ruskey, M. Schurch and J. Woodcock, Auspicious Tatami Mat Arrangements, The 16th Annual International Computing and Combinatorics Conference (COCOON 2010), July 19-21, Nha Trang, Vietnam. LNCS 6196 (2010) 288-297.
A. Erickson, F. Ruskey, M. Schurch and J. Woodcock, Monomer-Dimer Tatami Tilings of Rectangular Regions, Electronic Journal of Combinatorics, 18(1) (2011) P109.
Index entries for linear recurrences with constant coefficients, signature (2,0,2,-1).

Cf. A000045 (1 X n grid), A180970 (3 X n grid).

Row sums of A272471.

a:=[1,2,6,13];; for n in [5..35] do a[n]:=2*a[n-1]+2*a[n-3]-a[n-4]; od; a; # Muniru A Asiru, Sep 11 2018

I:=[1,2,6,13]; [n le 4 select I[n] else 2*Self(n-1)+2*Self(n-3)-Self(n-4): n in [1..35]]; // Vincenzo Librandi, Sep 11 2018

seq(coeff(series((1+2*x^2-x^3)/(x^4-2*x^3-2*x+1),x,n+1), x, n), n = 0 .. 35); # Muniru A Asiru, Sep 11 2018

CoefficientList[(1+2z^2-z^3)/(1-2z-2z^3+z^4) + O[z]^32, z] (* Jean-François Alcover, May 27 2015 *)
LinearRecurrence[{2,0,2,-1},{1,2,6,13},40] (* Harvey P. Dale, Jan 19 2023 *)

my(x='x+O('x^50)); Vec((1+2*x^2-x^3)/(1-2*x-2*x^3+x^4)) \\ Altug Alkan, Sep 10 2018

from math import log
print(0,1)
print(1,2)
print(2,6)
print(3,13)
n,a0,a1,a2,a3 = 3,13,6,2,1
while log(a0)/log(10) < 1000:
    n,a0,a1,a2,a3 = n+1,2*(a0+a2)-a3,a0,a1,a2
    print(n,a0) # A.H.M. Smeets, Sep 10 2018

def A180965_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1+2*x^2-x^3)/(1-2*x-2*x^3+x^4) ).list()
A180965_list(40) # G. C. Greubel, Apr 06 2021

G.f.: (1 + 2*x^2 - x^3)/(1 - 2*x - 2*x^3 + x^4).
Lim_{n -> inf} a(n)/a(n-1) = (sqrt(3) + 1)/2 + sqrt(sqrt(3)/2). - A.H.M. Smeets, Sep 10 2018
a(n) = 2*a(n-1) + 2*a(n-3) - a(n-4). - Muniru A Asiru, Sep 11 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A272472 Triangle T(n,m) by rows: The number of tatami tilings of a 3 by n grid with dimers and m monomers.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A180965 Number of tatami tilings of a 2 X n grid (with monomers allowed).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Python

Sage

Formula