cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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.

This page as a plain text file.
%I A298636 #16 Feb 13 2018 11:14:22
%S A298636 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,
%T A298636 115,1,1,28,441,2890,5957,2956,241,1,1,36,784,8036,30862,36148,10426,
%U A298636 495,1,1,45,1296,19278,122276,278530,195934,34899,1005,1,1,55,2025,41406,398874,1560118
%N 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.
%C A298636 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), ....
%C A298636 "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.
%C A298636 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.
%C A298636 This construction is relevant for enumerating the tight pavings defined by Knuth in A285357, see his Christmas Tree Lecture video there.
%e A298636 The table starts (cf. "table" link):
%e A298636   1   1    1     1     1      1     1 ...
%e A298636   1   3    6    10    15     21    28 ...  (= A000217 = n -> n(n+1)/2)
%e A298636   1   9   36   100   225    441   784 ...  (= A000537 = A000217^2)
%e A298636   1  23  181   845  2890   8036 19278...
%e A298636   1  53  775  5957 30862 122276  ...
%e A298636   1 115 2956 36148  ...
%e A298636   ...
%e A298636 Column 2 is A183155.
%e A298636 The T(2,3) = 6 drawings are { [0-1], [0-2], [0-3], [1-2], [1-3], [2-3] }.
%e A298636 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] }.
%e A298636 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], ...
%e A298636 Therefore, T(4,2) is less than 3*3*3 = 27: The T(4,2) = 23 drawings are:
%e A298636 { [0-1; 0-1; 0-1], [0-1; 0-1; 0-2], [0-1; 0-2; 0-2], [0-2; 0-1; 0-1],
%e A298636   [0-2; 0-1; 0-2], [0-2; 0-2; 0-1], [0-2; 0-2; 0-2], [0-1; 0-1; 1-2],
%e A298636   [0-2; 0-1; 1-2], [0-2; 0-2; 1-2], [0-1; 1-2; 0-1], [0-1; 1-2; 0-2],
%e A298636   [0-2; 1-2; 0-1], [0-2; 1-2; 0-2], [0-1; 1-2; 1-2], [0-2; 1-2; 1-2],
%e A298636   [1-2; 0-1; 0-1], [1-2; 0-1; 0-2], [1-2; 0-2; 0-2], [1-2; 0-1; 1-2],
%e A298636   [1-2; 1-2; 0-1], [1-2; 1-2; 0-2], [1-2; 1-2; 1-2] }
%o A298636 (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}
%Y A298636 Cf. A285357.
%Y A298636 Cf. A183155, A000537, A000217.
%K A298636 nonn,tabl,more
%O A298636 1,5
%A A298636 _M. F. Hasler_, Jan 23 2018