The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

 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]i || b[r]

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

Last modified December 5 09:45 EST 2021. Contains 349543 sequences. (Running on oeis4.)