cp's OEIS Frontend

A259698 Triangle read by rows: T(n,k) = number of permutations without overlaps having k increasing runs.

%I A259698 #30 Oct 06 2019 18:20:15
%S A259698 1,1,1,1,2,1,1,4,4,1,1,6,10,6,1,1,10,23,22,9,1,1,14,44,61,41,12,1,1,
%T A259698 22,87,158,148,71,16,1,1,30,151,352,436,301,114,20,1,1,46,280,791,
%U A259698 1210,1092,589,175,25,1,1,62,464,1592,2969,3317,2408,1038,256,30,1
%N A259698 Triangle read by rows: T(n,k) = number of permutations without overlaps having k increasing runs.
%C A259698 The sums s(n) = Sum_k k*T(n,k) give A259700.
%C A259698 Albert Sade in Sur les Chevauchements des Permutation (published by the author in French in 1949) gave the following example for determining the number of increasing runs in a permutation: 176852943 has 3 runs: 123 (left to right), 34567 (right to left), 789 (right to left).
%H A259698 Albert Sade, <a href="/A000108/a000108_17.pdf">Sur les Chevauchements des Permutations</a>, published by the author, Marseille, 1949. [Annotated scanned copy]
%e A259698 Triangle begins:
%e A259698   1;
%e A259698   1,  1;
%e A259698   1,  2,   1;
%e A259698   1,  4,   4,    1;
%e A259698   1,  6,  10,    6,    1;
%e A259698   1, 10,  23,   22,    9,    1;
%e A259698   1, 14,  44,   61,   41,   12,    1;
%e A259698   1, 22,  87,  158,  148,   71,   16,    1;
%e A259698   1, 30, 151,  352,  436,  301,  114,   20,   1;
%e A259698   1, 46, 280,  791, 1210, 1092,  589,  175,  25,  1;
%e A259698   1, 62, 464, 1592, 2969, 3377, 2408, 1038, 256, 30, 1;
%e A259698   ...
%o A259698 (PARI)
%o A259698 Overlapfree(v)={for(i=1, #v, for(j=i+1, v[i]-1, if(v[j]>v[i], return(0)))); 1}
%o A259698 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 A259698 Runs(v)={my(u=vector(#v), s=1); for(i=1, #v, u[v[i]]=i); for(i=2, #u-1, if(sign(u[i]-u[i-1])==sign(u[i]-u[i+1]), s++)); s}
%o A259698 row(n)={my(r=vector(n-1)); if(n>=2, forperm(n, v, if(v[1]<>1, break); if(Overlapfree(Chords(v)), r[Runs(v)]++))); r}
%o A259698 for(n=2, 8, print(row(n))) \\ _Andrew Howroyd_, Dec 07 2018
%Y A259698 Row sums give A000682.
%Y A259698 Cf. A259700.
%K A259698 nonn,tabl
%O A259698 2,5
%A A259698 _N. J. A. Sloane_, Jul 05 2015
%E A259698 Corrected and extended by _Roger Ford_, Jul 06 2016