A259689 Irregular triangle read by rows: T(n,k) is the number of degree-n permutations without overlaps which furnish k new permutations without overlaps upon the addition of an (n+1)st element, 2 <= k <= 1 + floor(n/2).

1, 2, 2, 2, 6, 4, 10, 10, 4, 32, 26, 8, 68, 64, 34, 8, 220, 186, 82, 16, 528, 488, 276, 98, 16, 1724, 1484, 744, 226, 32, 4460, 4086, 2382, 980, 258, 32, 14664, 12752, 6822, 2498, 578, 64, 39908, 36384, 21616, 9576, 3088, 642, 64, 131944, 115508, 64264, 26040, 7552, 1410, 128

Offset: 2

Author

N. J. A. Sloane, Jul 04 2015

Keywords

• nonn
• tabf

Comments

See Sade for precise definition.

From Roger Ford, Dec 07 2018: (Start)

T(n,k) is the number of semi-meanders with n top arches, k top arch groupings and a rainbow of bottom arches.

Example: /\ /\

n=4 k=3 //\\ /\ /\, /\ /\ //\\ T(4,3) = 2

.

/\ /\

//\\ //\\

n=4 k=2 ///\\\ /\, /\ ///\\\ T(4,2) = 2. (End)

Stéphane Legendre's solutions for folding a strip of stamps with leaf 1 on top have the same numeric sequences and total solutions as Albert Sade's permutations without overlaps. Stéphane Legendre's "Illustration of initial terms" link in A000682 models the values for Albert Sade's array. - Roger Ford, Dec 24 2018

Examples

			Triangle begins, n >= 2, 2 <= k <= 1 + floor(n/2):
     1;
     2;
     2,    2;
     6,    4;
    10,   10,    4;
    32,   26,    8;
    68,   64,   34,   8;
   220,  186,   82,  16;
   528,  488,  276,  98,  16;
  1724, 1484,  744, 226,  32;
  4460, 4086, 2382, 980, 258, 32;
  ...
		

References

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

Links

• Andrew Howroyd, Table of n, a(n) for n = 2..170
• Albert Sade, Sur les Chevauchements des Permutations, published by the author, Marseille, 1949. [Annotated scanned copy]

Crossrefs

Row sums give A000682.

Column k=2 is A260785.

Formula

Sum_{k>=2} k*T(n,k) = A000682(n + 1). - Andrew Howroyd, Dec 07 2018

T(n, floor(n/2)) = 2^floor((n-1)/2)*(n-4)+2. - Roger Ford, Dec 04 2018

For n>2, T(n, floor((n+2)/2)) = 2^(floor((n-1)/2)). - Roger Ford, Aug 18 2023

Extensions

Terms a(22) and beyond from Andrew Howroyd, Dec 05 2018