cp's OEIS Frontend

A259703 Triangle read by rows: T(n,k) = number of permutations without overlaps in which the first increasing run has length k.

%I A259703 #29 Dec 07 2018 16:43:15
%S A259703 1,1,1,2,1,1,5,2,2,1,12,5,4,2,1,33,13,12,4,3,1,87,35,30,12,6,3,1,252,
%T A259703 98,90,32,21,6,4,1,703,278,243,94,54,21,8,4,1,2105,812,745,270,175,57,
%U A259703 32,8,5,1,6099,2385,2108,808,485,181,84,32,10,5,1
%N A259703 Triangle read by rows: T(n,k) = number of permutations without overlaps in which the first increasing run has length k.
%C A259703 The 12th row of the triangle (as given in the reference) is definitely wrong, since the first column of this triangle is known (it is A000560). The row sums are also known - see A000682.
%C A259703 From _Roger Ford_, Jul 06 2016: (Start)
%C A259703 To determine the first increasing run of the permutation 176852943 start on the left and move to the right counting the consecutive integers.
%C A259703 (1)7685(2)94(3).  This permutation a has a first run of (3-1)=2. The permutation 123465 has a first run of (5-1)=4. (1)(2)(3)(4)6(5). (End)
%D A259703 A. Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949
%H A259703 Albert Sade, <a href="/A000108/a000108_17.pdf">Sur les Chevauchements des Permutations</a>, published by the author, Marseille, 1949. [Annotated scanned copy]
%e A259703 Triangle begins:
%e A259703      1;
%e A259703      1,    1;
%e A259703      2,    1,    1;
%e A259703      5,    2,    2,   1;
%e A259703     12,    5,    4,   2,   1;
%e A259703     33,   13,   12,   4,   3,   1;
%e A259703     87,   35,   30,  12,   6,   3,  1;
%e A259703    252,   98,   90,  32,  21,   6,  4,  1;
%e A259703    703,  278,  243,  94,  54,  21,  8,  4,  1;
%e A259703   2105,  812,  745, 270, 175,  57, 32,  8,  5, 1;
%e A259703   6099, 2385, 2108, 808, 485, 181, 84, 32, 10, 5, 1;
%e A259703   ...
%o A259703 (PARI)
%o A259703 Overlapfree(v)={for(i=1, #v, for(j=i+1, v[i]-1, if(v[j]>v[i], return(0)))); 1}
%o A259703 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 A259703 FirstRunLen(v)={my(e=1); for(i=1, #v, if(v[i]==e, e++)); e-2}
%o A259703 row(n)={my(r=vector(n-1)); if(n>=2, forperm(n, v, if(v[1]<>1, break); if(Overlapfree(Chords(v)), r[FirstRunLen(v)]++))); r}
%o A259703 for(n=2, 8, print(row(n))) \\ _Andrew Howroyd_, Dec 07 2018
%Y A259703 Row sums are A000682. First column is A000560.
%Y A259703 Cf. A259701.
%K A259703 nonn,tabl
%O A259703 2,4
%A A259703 _N. J. A. Sloane_, Jul 05 2015
%E A259703 Corrected and extended by _Roger Ford_, Jul 06 2016