A285357 Square array read by antidiagonals: T(m,n) = the number of tight m X n pavings (defined below).

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

Offset: 1

Author

Don Knuth, Apr 17 2017

Keywords

• nonn
• tabl
• hard

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

Examples

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

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.
• Roberto Tauraso, Problem 12005, Proposed solution.
• Konstantin Vladimirov, Generating things, Program naivepavings.cc to enumerate all tight pavings.

Crossrefs

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

Programs

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

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)

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