A298362 -id:A298362 - cp's OEIS frontend

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

Don Knuth, Apr 17 2017

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

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

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.

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

/* 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

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)

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

A285361 The number of tight 3 X n pavings.

Original entry on oeis.org

0, 1, 11, 64, 282, 1071, 3729, 12310, 39296, 122773, 378279, 1154988, 3505542, 10598107, 31957661, 96200098, 289255020, 869075073, 2609845875, 7834779640, 23514823730, 70565441671, 211738266921, 635298685614, 1906063827672, 5718527025901, 17156252164799, 51470098670020

Offset: 0

Don Knuth, Apr 17 2017

Also, zero together with the third row of the square array A285357.

			For n=2 the 11 solutions are 12|32|44, 12|13|44, 12|33|44, 11|22|34, 11|23|43, 12|13|43, 12|32|42, 12|13|14, 12|32|34, 11|23|24, 11|23|44.
(Use the "interactive illustration" link in A285357 (with n=3!) for a graphic display.)

Robert Israel, Table of n, a(n) for n = 0..2092
D. E. Knuth (Proposer), Problem 12005, Amer. Math. Monthly 124 (No. 8, Oct. 2017), page 755. For solution see op. cit., 126 (No. 7, 2019), 660-664.
Roberto Tauraso, Problem 12005, Proposed solution.
Index entries for linear recurrences with constant coefficients, signature (8,-24,34,-23,6).

Cf. A285357, A298362, A336732, A336734.

[(1/4)*(3^(n+3)-5*2^(n+4)+4*n^2+26*n+53): n in [0..30]]; // Vincenzo Librandi, Mar 16 2018

seq((1/4) * (3^(n+3) - 5*2^(n+4) + 4*n^2 + 26*n + 53),n=0..50); # Robert Israel, Mar 15 2018

LinearRecurrence[{8, -24, 34, -23, 6}, {0, 1, 11, 64, 282}, 30] (* Vincenzo Librandi, Mar 16 2018 *)

a(n) = (1/4) * (3^(n+3) - 5*2^(n+4) + 4*n^2 + 26*n + 53). - Hugo Pfoertner, Mar 14 2018

G.f.: (x+3*x^2)/((1-x)^3*(1-2*x)*(1-3*x)). - Robert Israel, Mar 15 2018

a(10) from Hugo Pfoertner, Jan 17 2018

More terms from M. F. Hasler, Jan 21 2018

A298432 a(n) = Sum_{k=0..n-1} T(n-k, k+1) where T(n, k) is the number of tight n X k pavings (defined in A285357).

Original entry on oeis.org

1, 2, 6, 24, 118, 680, 4456, 32512, 260080, 2254464, 20982768, 208142912, 2187336048, 24229170560

Offset: 1

Peter Luschny, Jan 19 2018

			These are the row sums of A285357 if A285357 is written as a triangle:
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;

D. E. Knuth (Proposer), Tight m-by-n 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.

Cf. A000295, A285357, A285361, A298362.

a(11) from Hugo Pfoertner, Jan 19 2018

a(12)-a(14) from Denis Roegel, Feb 24 2018

A298433 a(n) is the number of tight n X n pavings (defined in A285357).

Original entry on oeis.org

1, 4, 64, 2072, 106738, 7743880, 735490024, 87138728592

Offset: 1

Peter Luschny, Jan 19 2018

D. E. Knuth (Proposer), Tight m-by-n 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.

Cf. A000295, A285357, A285361, A298362.

a(n) = A285357(n,n).

a(6) from Hugo Pfoertner, Jan 19 2018
a(7) from Denis Roegel, Feb 23 2018
a(8) from Denis Roegel, Feb 24 2018

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A285361 The number of tight 3 X n pavings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

Extensions

A298432 a(n) = Sum_{k=0..n-1} T(n-k, k+1) where T(n, k) is the number of tight n X k pavings (defined in A285357).

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A298433 a(n) is the number of tight n X n pavings (defined in A285357).

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions