login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 1
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
1,5
COMMENTS
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.
LINKS
EXAMPLE
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] }
PROG
(PARI) 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]<n && S[b[i]]=if(S[b[i]], concat(S[b[i]], i), i)); for(i=1, #S, #S[i]<2 && next; for(j=2, #T=Set(S[i]), T[j-1]==T[j]-1&&next; for(r=T[j-1]+1, T[j]-1, a[r]>i || b[r]<i || next(4)))); c++; show&&print1(Mat([a~, b~])", "))); c}
CROSSREFS
Cf. A285357.
Sequence in context: A046716 A371967 A202605 * A123354 A120247 A235113
KEYWORD
nonn,tabl,more
AUTHOR
M. F. Hasler, Jan 23 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 22 01:34 EDT 2024. Contains 371887 sequences. (Running on oeis4.)