A259701 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.

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, 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, 6099, 280, 1296, 63, 215, 6, 27, 0, 2, 0, 0

Offset: 2

Author

N. J. A. Sloane, Jul 05 2015

Keywords

• nonn
• tabl
• more

Comments

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).

Examples

			Triangle begins:
     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,  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;
  ...
		

References

• A. Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949

Links

• Albert Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949. [Annotated scanned copy]

Crossrefs

Row sums excluding the first column give A259702.

First column is A000560.

Cf. A259703.

Programs

PARI

Overlapfree(v)={for(i=1, #v, for(j=i+1, v[i]-1, if(v[j]>v[i], return(0)))); 1}
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}
FirstRunLen(v)={my(e=1); for(i=1, #v, if(v[i]==e, e++)); e-2}
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}
for(n=2, 8, print(row(n))) \\ Andrew Howroyd, Dec 07 2018

Extensions

a(49) corrected and a(57)-a(67) from Andrew Howroyd, Dec 07 2018