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