

A285357


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


7



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, 781548, 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+n1 rectangles, having m+1 distinct boundary lines in one dimension and n+1 distinct boundary lines in another.
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


REFERENCES

[I have just submitted a related problem to the American Math Monthly.]
[There's another characterization of tight pavings, to be revealed when the solution is published.]


LINKS

Table of n, a(n) for n=1..55.
M. F. Hasler, Illustration of initial terms.
M. F. Hasler, Interactive illustration of T(2,n). (Uses JavaScript).
D. E. Knuth (Proposer), Tight mbyn pavings; Problem 12005, Amer. Math. Monthly 124 (No. 8, Oct. 2017), page 755.
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.


EXAMPLE

There are 1071 tight pavings when m = 3 and n = 5. Two of them have their seven rectangles in the trivial patterns 111112222234567 and 123451234612347; a more interesting example is 111223442235667.
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>all(n1, a*10+t), nxt[d+1+(!d&&a)])), [a*10+(d>1!a)])} \\ M. F. Hasler, Jan 20 2018


CROSSREFS

Cf. A000295, A285361, A298362, A298432, A298433.
Sequence in context: A156534 A168287 A221987 * A174526 A008292 A174036
Adjacent sequences: A285354 A285355 A285356 * A285358 A285359 A285360


KEYWORD

nonn,tabl,hard


AUTHOR

Don Knuth, Apr 17 2017


EXTENSIONS

Edited by M. F. Hasler, Jan 13 2018 and by N. J. A. Sloane, Jan 14 2018
More terms from Hugo Pfoertner, Jan 19 2018


STATUS

approved



