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

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, 22, 87, 158, 148, 71, 16, 1, 1, 30, 151, 352, 436, 301, 114, 20, 1, 1, 46, 280, 791, 1210, 1092, 589, 175, 25, 1, 1, 62, 464, 1592, 2969, 3317, 2408, 1038, 256, 30, 1

Offset

2,5

Comments

The sums s(n) = Sum_k k*T(n,k) give A259700.

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

Links

Table of n, a(n) for n=2..67.

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

Example

Triangle begins:
  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, 22,  87,  158,  148,   71,   16,    1;
  1, 30, 151,  352,  436,  301,  114,   20,   1;
  1, 46, 280,  791, 1210, 1092,  589,  175,  25,  1;
  1, 62, 464, 1592, 2969, 3377, 2408, 1038, 256, 30, 1;
  ...

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}
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}
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}
for(n=2, 8, print(row(n))) \\ Andrew Howroyd, Dec 07 2018

Crossrefs

Row sums give A000682.

Cf. A259700.

Sequence in context: A132731 A128966 A055907 * A274643 A172991 A203906

Adjacent sequences: A259695 A259696 A259697 * A259699 A259700 A259701

Keyword

nonn,tabl

Author

N. J. A. Sloane, Jul 05 2015

Extensions

Corrected and extended by Roger Ford, Jul 06 2016

Status

approved