A285357 -id:A285357 - cp's OEIS frontend

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.

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

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

A116694 Array read by antidiagonals: number of ways of dividing an n X m rectangle into integer-sided rectangles.

Original entry on oeis.org

1, 2, 2, 4, 8, 4, 8, 34, 34, 8, 16, 148, 322, 148, 16, 32, 650, 3164, 3164, 650, 32, 64, 2864, 31484, 70878, 31484, 2864, 64, 128, 12634, 314662, 1613060, 1613060, 314662, 12634, 128, 256, 55756, 3149674, 36911922, 84231996, 36911922, 3149674, 55756, 256

Offset: 1

Helena Verrill (verrill(AT)math.lsu.edu), Feb 23 2006

			Array begins:
   1,    2,      4,        8,         16,           32, ...
   2,    8,     34,      148,        650,         2864, ...
   4,   34,    322,     3164,      31484,       314662, ...
   8,  148,   3164,    70878,    1613060,     36911922, ...
  16,  650,  31484,  1613060,   84231996,   4427635270, ...
  32, 2864, 314662, 36911922, 4427635270, 535236230270, ...

Alois P. Heinz, Antidiagonals n = 1..20, flattened
David A. Klarner and Spyros S. Magliveras, The number of tilings of a block with blocks, European Journal of Combinatorics 9 (1988), 317-330.
Joshua Smith and Helena Verrill, On dividing rectangles into rectangles

Columns (or rows) 1-10 give: A011782, A034999, A208215, A220297, A220298, A220299, A220300, A220301, A220302, A220303.
Main diagonal gives A182275.
For irreducible or "tight" pavings, see also A285357.
Triangular version: A333476.
A(2n,n) gives A333495.

M:= proc(n) option remember; local k; k:= 2^(n-2);
      `if`(n=1, Matrix([2]), Matrix(2*k, (i, j)->`if`(i<=k,
      `if`(j<=k, M(n-1)[i, j], B(n-1)[i, j-k]),
      `if`(j<=k, B(n-1)[i-k, j], 2*M(n-1)[i-k, j-k]))))
    end:
B:= proc(n) option remember; local k; k:=2^(n-2);
      `if`(n=1, Matrix([1]), Matrix(2*k, (i,j)->`if`(i<=k,
      `if`(j<=k, B(n-1)[i, j], B(n-1)[i, j-k]),
      `if`(j<=k, B(n-1)[i-k, j], M(n-1)[i-k, j-k]))))
    end:
A:= proc(n, m) option remember; `if`(n=0 or m=0, 1, `if`(m>n, A(m, n),
      add(i, i=map(rhs, [op(op(2, M(m)^(n-1)))]))))
    end:
seq(seq(A(n, 1+d-n), n=1..d), d=1..12);  # Alois P. Heinz, Dec 13 2012

M[n_] := M[n] = Module[{k = 2^(n-2)}, If[n == 1, {{2}}, Table[If[i <= k, If[j <= k, M[n-1][[i, j]], B[n-1][[i, j-k]]], If[j <= k, B[n-1][[i-k, j]], 2*M[n-1][[i-k, j-k]]]], {i, 1, 2k}, {j, 1, 2k}]]]; B[n_] := B[n] = Module[{k = 2^(n-2)}, If[n == 1, {{1}}, Table[If[i <= k, If[j <= k, B[n-1][[i, j]], B[n-1][[i, j-k]]], If[j <= k, B[n-1][[i-k, j]], M[n-1][[i-k, j-k]]]], {i, 1, 2k}, {j, 1, 2k}]]]; A[0, 0] = 1; A[n_ , m_ ] /; m>n := A[m, n]; A[n_ , m_ ] :=MatrixPower[M[m], n-1] // Flatten // Total; Table[Table[A[n, 1+d-n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Feb 23 2015, after Alois P. Heinz *)

A116694(m,n)=#fill(m,n) \\ where fill() below computes all tilings. - M. F. Hasler, Jan 22 2018
fill(m,n,A=matrix(m,n),i=1,X=1,Y=1)={while((Y>n&&X++&&!Y=0)||A[X,Y], X>m&&return([A]); Y++); my(N=n,L=[]); for(x=X,m, A[x,Y]&&break; for(y=Y,N, if(A[x,y],for(j=y,N,for(k=X,x-1,A[k,j]=0));N=y-1;break); for(j=X,x,A[j,y]=i); L=concat(L,fill(m,n,A,i+1,X,y+1))); x

Edited and more terms from Alois P. Heinz, Dec 09 2012

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

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

A298636 Square array T(m,n) = number of ways to draw m-1 horizontal lines [a(i),b(i)] with 0 <= a(i) < b(i) <= n such that if two lines start or end on the same coordinate, no intermediate line crosses this coordinate (see comments); m, n >= 1.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 6, 9, 1, 1, 10, 36, 23, 1, 1, 15, 100, 181, 53, 1, 1, 21, 225, 845, 775, 115, 1, 1, 28, 441, 2890, 5957, 2956, 241, 1, 1, 36, 784, 8036, 30862, 36148, 10426, 495, 1, 1, 45, 1296, 19278, 122276, 278530, 195934, 34899, 1005, 1, 1, 55, 2025, 41406, 398874, 1560118

Offset: 1

M. F. Hasler, Jan 23 2018

Following the OEIS standard, the array is read by falling antidiagonals, i.e., T(1,1), T(1,2), T(2,1), T(1,3), ....
"Horizontal line [a(i),b(i)]" means a line from (a(i),i) to (b(i),i). "No intermediate line crosses..." means that, if {a(i),b(i)} and {a(j),b(j)} have x in common for some j > i, then for all i < k < j, either a(k) >= x or b(k) <= x.
Equivalently, number of (m-1) X n binary (0,1) matrices where each row has exactly one run of 1's and any two of these runs may not start or end at the same column border, unless no run in the intermediate rows crosses (= extends to both sides of) this border.
This construction is relevant for enumerating the tight pavings defined by Knuth in A285357, see his Christmas Tree Lecture video there.

			The table starts (cf. "table" link):
  1   1    1     1     1      1     1 ...
  1   3    6    10    15     21    28 ...  (= A000217 = n -> n(n+1)/2)
  1   9   36   100   225    441   784 ...  (= A000537 = A000217^2)
  1  23  181   845  2890   8036 19278...
  1  53  775  5957 30862 122276  ...
  1 115 2956 36148  ...
  ...
Column 2 is A183155.
The T(2,3) = 6 drawings are { [0-1], [0-2], [0-3], [1-2], [1-3], [2-3] }.
The T(3,2) = 9 drawings are { [0-1; 0-1], [0-1; 0-2], [0-1; 1-2], [0-2; 0-1], [0-2, 0-2], [0-2; 1-2], [1-2; 0-1], [1-2; 0-2], [1-2; 1-2] }.
The "no line crosses" condition becomes effective only for m > 3. For m = 4, it excludes drawings like, e.g., [0-1; 0-2; 0-1], [0-1; 0-2; 1-2], ...
Therefore, T(4,2) is less than 3*3*3 = 27: The T(4,2) = 23 drawings are:
{ [0-1; 0-1; 0-1], [0-1; 0-1; 0-2], [0-1; 0-2; 0-2], [0-2; 0-1; 0-1],
  [0-2; 0-1; 0-2], [0-2; 0-2; 0-1], [0-2; 0-2; 0-2], [0-1; 0-1; 1-2],
  [0-2; 0-1; 1-2], [0-2; 0-2; 1-2], [0-1; 1-2; 0-1], [0-1; 1-2; 0-2],
  [0-2; 1-2; 0-1], [0-2; 1-2; 0-2], [0-1; 1-2; 1-2], [0-2; 1-2; 1-2],
  [1-2; 0-1; 0-1], [1-2; 0-1; 0-2], [1-2; 0-2; 0-2], [1-2; 0-1; 1-2],
  [1-2; 1-2; 0-1], [1-2; 1-2; 0-2], [1-2; 1-2; 1-2] }

Cf. A285357.

Cf. A183155, A000537, A000217.

A298636(m, n, show=0, c=0)={ my(S, N, u=vector(m-1,i,1)); forvec(a=vector(m-1, i, [0, n-1]), S=Set(a); N=vector(n-1); for(i=1,#a, a[i] && N[a[i]]=if(N[a[i]],concat(N[a[i]],i),i)); forvec(b=vector(m-1, j, [a[j]+1, n]), S=N; for(i=1,#b, b[i]i || b[r]

cp's OEIS Frontend

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

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

A116694 Array read by antidiagonals: number of ways of dividing an n X m rectangle into integer-sided rectangles.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A285361 The number of tight 3 X n pavings.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

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

A298636 Square array T(m,n) = number of ways to draw m-1 horizontal lines [a(i),b(i)] with 0 <= a(i) < b(i) <= n such that if two lines start or end on the same coordinate, no intermediate line crosses this coordinate (see comments); m, n >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI