%I #12 Dec 07 2018 16:42:55
%S 0,1,0,2,0,0,5,0,1,0,12,0,2,0,0,33,1,7,0,1,0,87,2,17,0,2,0,0,252,11,
%T 55,2,9,0,1,0,703,26,145,4,22,0,2,0,0,2105,109,467,27,81,3,11,0,1,0,
%U 6099,280,1296,63,215,6,27,0,2,0,0
%N Triangle read by rows: T(n,k) = number of permutations without overlaps in which the first increasing run has length k and the second element is not 2.
%C The 12th row of the triangle given in the Sade reference is incorrect, since the first column of this triangle is known (it is A000560).
%D A. Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949
%H Albert Sade, <a href="/A000108/a000108_17.pdf">Sur les Chevauchements des Permutations</a>, published by the author, Marseille, 1949. [Annotated scanned copy]
%e Triangle begins:
%e 0;
%e 1, 0;
%e 2, 0, 0;
%e 5, 0, 1, 0;
%e 12, 0, 2, 0, 0;
%e 33, 1, 7, 0, 1, 0;
%e 87, 2, 17, 0, 2, 0, 0;
%e 252, 11, 55, 2, 9, 0, 1, 0;
%e 703, 26, 145, 4, 22, 0, 2, 0, 0;
%e 2105, 109, 467, 27, 81, 3, 11, 0, 1, 0;
%e ...
%o (PARI)
%o Overlapfree(v)={for(i=1, #v, for(j=i+1, v[i]-1, if(v[j]>v[i], return(0)))); 1}
%o Chords(u)={my(n=2*#u, v=vector(n), s=u[#u]); if(s%2==0, s=n+1-s); for(i=1, #u, my(t=n+1-s); s=u[i]; if(s%2==0, s=n+1-s); v[s]=t; v[t]=s); v}
%o FirstRunLen(v)={my(e=1); for(i=1, #v, if(v[i]==e, e++)); e-2}
%o row(n)={my(r=vector(n-1)); if(n>=2, forperm(n, v, if(v[1]<>1, break); if(v[2]<>2 && Overlapfree(Chords(v)), r[FirstRunLen(v)]++))); r}
%o for(n=2, 8, print(row(n))) \\ _Andrew Howroyd_, Dec 07 2018
%Y Row sums excluding the first column give A259702.
%Y First column is A000560.
%Y Cf. A259703.
%K nonn,tabl,more
%O 2,4
%A _N. J. A. Sloane_, Jul 05 2015
%E a(49) corrected and a(57)-a(67) from _Andrew Howroyd_, Dec 07 2018
|