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,2

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

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]

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

Example

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

Crossrefs

Row sums give A000682.

Column k=2 is A260785.

Sequence in context: A232114 A038074 A059885 * A300413 A246707 A324339

Adjacent sequences: A259686 A259687 A259688 * A259690 A259691 A259692

Keyword

nonn,tabf

Author

N. J. A. Sloane, Jul 04 2015

Extensions

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

Status

approved