|
|
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
|
Konstantin Vladimirov, Generating things, Program naivepavings.cc to enumerate all tight pavings.
|
|
FORMULA
|
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)
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
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|