login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A285357 Square array read by antidiagonals: T(m,n) = the number of tight m X n pavings (defined below). 7
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, 781548, 305464, 39296, 1013, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

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.

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

REFERENCES

[I have just submitted a related problem to the American Math Monthly.]

[There's another characterization of tight pavings, to be revealed when the solution is published.]

LINKS

Denis Roegel, Antidiagonals n = 1..13, flattened

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.

D. E. Knuth, A conjecture that had to be true, Stanford Lecture: Don Knuth's Christmas Tree Lecture 2017.

Konstantin Vladimirov, Generating things, Program naivepavings.cc to enumerate all tight pavings.

EXAMPLE

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

  ...

PROG

(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->all(n-1, a*10+t), nxt[d+1+(!d&&a)])), [a*10+(d>1||!a)])} \\ M. F. Hasler, Jan 20 2018

CROSSREFS

Cf. A000295, A285361, A298362, A298432, A298433.

Sequence in context: A156534 A168287 A221987 * A174526 A008292 A174036

Adjacent sequences:  A285354 A285355 A285356 * A285358 A285359 A285360

KEYWORD

nonn,tabl,hard

AUTHOR

Don Knuth, Apr 17 2017

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 24 16:57 EDT 2018. Contains 304532 sequences. (Running on oeis4.)