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

Author

N. J. A. Sloane, Jul 05 2015

Keywords

• nonn
• tabl

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

Examples

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

Links

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

Crossrefs

Row sums give A000682.

Cf. A259700.

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}
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

Extensions

Corrected and extended by Roger Ford, Jul 06 2016