A285361 -id:A285361 - 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

A298362 Number of tight m X n pavings as defined in Knuth's A285357 written as triangle T(m,n), m >= 1, 1 <= n <= m.

Original entry on oeis.org

1, 1, 4, 1, 11, 64, 1, 26, 282, 2072, 1, 57, 1071, 12279, 106738, 1, 120, 3729, 63858, 781458, 7743880, 1, 247, 12310, 305464, 5111986, 66679398, 735490024, 1, 502, 39296, 1382648, 30980370, 521083252, 7216122740, 87138728592, 1, 1013, 122773, 6029325, 178047831, 3802292847, 65106398091

Offset: 1

Hugo Pfoertner, Jan 17 2018

See A285357.

For m < n, one has A285357(m,n) = T(n,m). Thus, row and column n of A285357 start with the n terms of row n, then go on downwards in column n: e.g., the full row/column 2 is (1, 4, 11, 26, ...) = A000295 (without initial 0); row/column 3 is (1, 11, 64, 282, 1071, ...) = A285361. - M. F. Hasler, Jan 20 2018

			The triangle starts:
================================================================================
m \ n| 1    2      3        4         5           6           7           8    9
-----|--------------------------------------------------------------------------
.  1 | 1
.  2 | 1    4
.  3 | 1   11     64
.  4 | 1   26    282     2072
.  5 | 1   57   1071    12279    106738
.  6 | 1  120   3729    63858    781458     7743880
.  7 | 1  247  12310   305464   5111986    66679398   735490024
.  8 | 1  502  39296  1382648  30980370   521083252  7216122740 87138728592
.  9 | 1 1013 122773  6029325 178047831  3802292847 65106398091      ?         ?
. 10 | 1 2036 378279 25628762 985621119 26409556208         ...

Roberto Tauraso, Problem 12005, Proposed solution.
Konstantin Vladimirov, Generating things, Program naivepavings.cc to enumerate all tight pavings.

Cf. A000295, A285357, A285361, A336732, A336734.

Added a number of values in the example table, Denis Roegel, Feb 24 2018

Extended using data from Denis Roegel by Hugo Pfoertner, Mar 12 2018

A336732 The number of tight 4 X n pavings.

Original entry on oeis.org

0, 1, 26, 282, 2072, 12279, 63858, 305464, 1382648, 6029325, 25628762, 107026662, 441439944, 1804904755, 7334032754, 29669499492, 119647095176, 481400350185, 1933747745850, 7758556171570, 31102292517560, 124605486285231, 498987240470066, 1997573938402512

Offset: 0

Roberto Tauraso, Aug 02 2020

This is row (or column) m=4 of the array T in A285357.

D. E. Knuth (Proposer), Problem 12005, Amer. Math. Monthly 124 (No. 8, Oct. 2017), page 755. For the 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 (18,-139,604,-1627,2818,-3141,2176,-852,144).

Cf. A000295 (m=2), A285357, A285361 (m=3), A336734 (m=5).

seq((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,n=0..20);

num=(x+8*x^2-47*x^3+6*x^4+104*x^5); den=((1-x)^4*(1-2*x)^2*(1-3*x)^2*(1-4*x)); CoefficientList[Series[num/den,{x,0,20}],x]

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

G.f.: (x+8*x^2-47*x^3+6*x^4+104*x^5)/((1-x)^4*(1-2*x)^2*(1-3*x)^2*(1-4*x)).

A336734 The number of tight 5 X n pavings.

Original entry on oeis.org

0, 1, 57, 1071, 12279, 106738, 781458, 5111986, 30980370, 178047831, 985621119, 5311715977, 28075774881, 146309927344, 754544640000, 3861338821620, 19646614600164, 99532074868285, 502608221035605, 2531829420822835, 12730273358124315, 63919766245452606

Offset: 0

Roberto Tauraso, Aug 02 2020

This is row (or column) m=5 of the array T in A285357.

D. E. Knuth (Proposer), Problem 12005, Amer. Math. Monthly 124 (No. 8, Oct. 2017), page 755. For the 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 (31,-432,3580,-19666,75558,-208736,419600,-613605,644771,-473432,230220,-66528,8640).

Cf. A000295 (m=2), A285357, A285361 (m=3), A336732 (m=4).

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

G.f.: (x +26*x^2 -264*x^3 +122*x^4 +4367*x^5 -11668*x^6 +3000*x^7 +11168*x^8 +160*x^9) / ((1-x)^5*(1-2*x)^2*(1-3*x)^3*(1-4*x)^2*(1-5*x)).

A298564 a(n) = (3^(n+2)+11)/2 - 52^(n+1) + 2n.

Original entry on oeis.org

0, 1, 10, 53, 218, 789, 2658, 8581, 26986, 83477, 255506, 776709, 2350554, 7092565, 21359554, 64242437, 193054922, 579820053, 1740770802, 5224933765, 15680044090, 47050617941, 141172825250, 423560418693, 1270765142058, 3812463198229, 11437725138898, 34313846505221, 102942881692826

Offset: 0

M. F. Hasler, Jan 21 2018

Partial sums of A281773; first differences of A285361.

Index entries for linear recurrences with constant coefficients, signature (7,-17,17,-6)

Cf. A281773, A285361.

Array[(3^(# + 2) + 11)/2 - 5*2^(# + 1) + 2 # &, 29, 0] (* or *)
CoefficientList[Series[x (1 + 3 x)/((3 x - 1) (2 x - 1) (x - 1)^2), {x, 0, 28}], x] (* Michael De Vlieger, Jan 21 2018 *)

PARI
```
A298564(n)=2*n-5<<(n+1)+3^(n+2)\2+5
```

def A298564list(n):
    def generator():
        a, b, c = 5, 3, 0
        while True:
            yield c
            a *= 2
            b *= 3
            c += 2 - a + b
    a = generator()
    return [next(a) for _ in range(n)]
print(A298564list(29)) # Peter Luschny, Jan 22 2018

G.f.: x*(1+3*x) / ( (3*x-1)*(2*x-1)*(x-1)^2 ). - R. J. Mathar, Jan 21 2018

a(n) = A249999(n-1) +3*A249999(n-2). - R. J. Mathar, 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

A298362 Number of tight m X n pavings as defined in Knuth's A285357 written as triangle T(m,n), m >= 1, 1 <= n <= m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A336732 The number of tight 4 X n pavings.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A336734 The number of tight 5 X n pavings.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A298564 a(n) = (3^(n+2)+11)/2 - 5*2^(n+1) + 2*n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

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

A298564 a(n) = (3^(n+2)+11)/2 - 52^(n+1) + 2n.