login
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.
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,4
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).
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]
EXAMPLE
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;
...
PROG
(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
CROSSREFS
Row sums excluding the first column give A259702.
First column is A000560.
Cf. A259703.
Sequence in context: A289088 A057611 A329959 * A147843 A094597 A202992
KEYWORD
nonn,tabl,more
AUTHOR
N. J. A. Sloane, Jul 05 2015
EXTENSIONS
a(49) corrected and a(57)-a(67) from Andrew Howroyd, Dec 07 2018
STATUS
approved