|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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}
|
|
CROSSREFS
|
Row sums excluding the first column give A259702.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|