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

%I #108 Mar 18 2023 14:49:30

%S 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,

%T 1071,120,1,1,247,3729,12279,12279,3729,247,1,1,502,12310,63858,

%U 106738,63858,12310,502,1,1,1013,39296,305464,781458,781458,305464,39296,1013,1

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

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

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

%C 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

%C 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

%H Denis Roegel, <a href="/A285357/b285357.txt">Table of n, a(n) for n = 1..91</a> [Antidiagonals n = 1..13; a(51)=781458 corrected by _Georg Fischer_, Jul 30 2020]

%H M. F. Hasler, <a href="/A285357/a285357.pdf">Illustration of initial terms</a>.

%H M. F. Hasler, <a href="/A285357/a285357_1.html">Interactive illustration of T(2,n)</a>. (Uses JavaScript.)

%H D. E. Knuth (Proposer), <a href="http://dx.doi.org/10.4169/amer.math.monthly.124.8.754">Tight m-by-n pavings; Problem 12005</a>, Amer. Math. Monthly 124 (No. 8, Oct. 2017), page 755. <a href="https://doi.org/10.1080/00029890.2019.1621132">Solution</a> in Amer. Math. Monthly 126 (No. 7, July 2019), page 660-664.

%H D. E. Knuth, <a href="https://www.youtube.com/watch?v=BxQw4CdxLr8">A conjecture that had to be true</a>, Stanford Lecture: Don Knuth's Christmas Tree Lecture 2017.

%H Roberto Tauraso, <a href="http://www.mat.uniroma2.it/~tauraso/AMM/AMM12005.pdf">Problem 12005, Proposed solution</a>.

%H Konstantin Vladimirov, <a href="https://github.com/tilir/generators">Generating things</a>, Program naivepavings.cc to enumerate all tight pavings.

%F From _M. F. Hasler_, Jul 30 2020: (Start)

%F T(1,n) = 1.

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

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

%F From _Roberto Tauraso_, Aug 02 2020: (Start)

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

%F 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)

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

%e The array begins:

%e 1 1 1 1 1 1 1 ...

%e 1 4 11 26 57 120 ...

%e 1 11 64 282 1071 ...

%e 1 26 282 2072 ...

%e 1 57 1071 ...

%e 1 120 ...

%e ...

%o (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

%o for(n=1, 20, print1(#T2(n),", ")) \\ gives row T(2,n) - _Georg Fischer_, Jul 30 2020

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

%K nonn,tabl,hard

%O 1,5

%A _Don Knuth_, Apr 17 2017

%E Edited by _M. F. Hasler_, Jan 13 2018 and by _N. J. A. Sloane_, Jan 14 2018

%E a(29)-a(55) from _Hugo Pfoertner_, Jan 19 2018

%E a(51) corrected by _Hugo Pfoertner_, Jul 29 2020