login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A285357 Square array read by antidiagonals: T(m,n) = the number of tight m X n pavings (defined below). 9
1, 1, 1, 1, 4, 1, 1, 11, 11, 1, 1, 26, 64, 26, 1, 1, 57, 282, 282, 57, 1, 1, 120, 1071, 2072, 1071, 120, 1, 1, 247, 3729, 12279, 12279, 3729, 247, 1, 1, 502, 12310, 63858, 106738, 63858, 12310, 502, 1, 1, 1013, 39296, 305464, 781458, 781458, 305464, 39296, 1013, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

A tight m X n paving is a dissection of an m X n rectangle into m+n-1 rectangles, having m+1 distinct boundary lines in one dimension and n+1 distinct boundary lines in another.

There's another characterization of tight pavings (cf. the lemma in the solution reference).

The 2nd column are the Eulerian numbers A000295(n+1) = 2^(n+1) - n - 2. The 3rd column/diagonal is given in A285361. - M. F. Hasler, Jan 11 2018

Related to the dissection of rectangles into smaller rectangles, see Knuth's Stanford lecture video. Sequence A116694 gives the number of these dissections. - M. F. Hasler, Jan 22 2018

LINKS

Denis Roegel, Table of n, a(n) for n = 1..91 [Antidiagonals n = 1..13; a(51)=781458 corrected by Georg Fischer, Jul 30 2020]

M. F. Hasler, Illustration of initial terms.

M. F. Hasler, Interactive illustration of T(2,n). (Uses JavaScript).

D. E. Knuth (Proposer), Tight m-by-n pavings; Problem 12005, Amer. Math. Monthly 124 (No. 8, Oct. 2017), page 755. Solution in Amer. Math. Monthly 126 (No. 7, July 2019), page 660-664.

D. E. Knuth, A conjecture that had to be true, Stanford Lecture: Don Knuth's Christmas Tree Lecture 2017.

Konstantin Vladimirov, Generating things, Program naivepavings.cc to enumerate all tight pavings.

FORMULA

From M. F. Hasler, Jul 30 2020 (Start):

T(1,n) = 1.

T(2,n) = A000295(n+1) = 2^(n+1) - n - 2.

T(3,n) = A285361(n) = (3^(n+3) - 5*2^(n+4) + 4*n^2 + 26*n + 53)/4. (End)

From Roberto Tauraso, Aug 02 2020 (Start):

T(4,n) = A336732(n) = (4^(n+5) + (n-42)*3^(n+4) - 9*(2*n-27)*2^(n+5) - 36*n^3-486*n^2 - 2577*n - 5398)/36.

T(5,n) = A336734(n) = (5^(n+7) + (2*n-66)*4^(n+6) + (16*n^2-1432*n+13164)*3^(n+3) + (303*n-1505)*2^(n+10) + 576*n^4 + 13248*n^3 + 129936*n^2 + 646972*n + 1377903)/576. (End)

EXAMPLE

There are 1071 tight pavings when m = 3 and n = 5. Two of them have their seven rectangles in the trivial patterns 11111|22222|34567 and 12345|12346|12347; a more interesting example is 11122|34422|35667.

The array begins:

  1   1    1    1    1    1    1  ...

  1   4   11   26   57  120  ...

  1  11   64  282 1071  ...

  1  26  282 2072  ...

  1  57 1071  ...

  1 120  ...

  ...

PROG

(PARI) /* List all 2 X n tight pavings, where 0 = |, 1 = ┥, 2 = ┙, 3 = ┑ */ nxt=[[0, 1, 2, 3], [0], [1, 2, 3], [1, 2, 3]]; T2(n, a=0, d=a%10)={if(n>1, concat(apply(t->T2(n-1, a*10+t), nxt[d+1+(!d&&a)])), [a*10+(d>1||!a)])} \\ M. F. Hasler, Jan 20 2018

for(n=1, 20, print1(#T2(n), ", ")) \\ gives row T(2, n) - Georg Fischer, Jul 30 2020

CROSSREFS

Cf. A000295 (m=2), A116694, A285361 (m=3), A298362, A298432 (diagonal sums), A298433 (diagonal), A336732 (m=4), A336734 (m=5).

Sequence in context: A156534 A168287 A221987 * A174526 A008292 A174036

Adjacent sequences:  A285354 A285355 A285356 * A285358 A285359 A285360

KEYWORD

nonn,tabl,hard,changed

AUTHOR

Don Knuth, Apr 17 2017

EXTENSIONS

Edited by M. F. Hasler, Jan 13 2018 and by N. J. A. Sloane, Jan 14 2018

a(29)-a(55) from Hugo Pfoertner, Jan 19 2018

a(51) corrected by Hugo Pfoertner, Jul 29 2020

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 12 05:33 EDT 2020. Contains 336438 sequences. (Running on oeis4.)