A262494 Triangle read by rows: T(n,k) (n>=1, 0<=k<n) is the number of permutations of n things that require k stack-sorts.

1, 1, 1, 1, 4, 1, 1, 13, 8, 2, 1, 41, 49, 23, 6, 1, 131, 276, 198, 90, 24, 1, 428, 1509, 1556, 982, 444, 120, 1, 1429, 8184, 11812, 9678, 5856, 2640, 720, 1, 4861, 44473, 88566, 91959, 68820, 40800, 18360, 5040, 1, 16795, 243334, 662732, 863296, 775134, 555828, 325200, 146160, 40320

Offset

1,5

Comments

It appears that no recurrence or g.f. is known. - N. J. A. Sloane, Oct 13 2015

Links

Table of n, a(n) for n=1..55.

FindStat - Combinatorial Statistic Finder, The number of stack-sorts needed to sort a permutation

Julian West, Permutations with forbidden subsequences; and, stack-sortable permutations, Ph.D. thesis, Massachusetts Institute of Technology, Dept. of Mathematics, 1990. See p. 76.

Formula

T(n,0) = 1, T(n,1) = A000108(n) - 1. - Joerg Arndt, Sep 27 2015

Example

Triangle begins:
  1;
  1,    1;
  1,    4,     1;
  1,   13,     8,     2;
  1,   41,    49,    23,     6;
  1,  131,   276,   198,    90,    24;
  1,  428,  1509,  1556,   982,   444,   120;
  1, 1429,  8184, 11812,  9678,  5856,  2640,   720;
  1, 4861, 44473, 88566, 91959, 68820, 40800, 18360, 5040;
  ...

Crossrefs

Columns k=0-1 give: A000012, A001453.

Row sums give A000142.

Cf. A000108.

Sequence in context: A140070 A158815 A101275 * A039755 A247502 A047874

Adjacent sequences: A262491 A262492 A262493 * A262495 A262496 A262497

Keyword

nonn,tabl

Author

Christian Stump, Sep 24 2015

Extensions

Definition edited by N. J. A. Sloane, Oct 13 2015

More terms from Christian Stump, Oct 19 2015

Rows n=7-10 from Julian West's thesis added by Alois P. Heinz, Jun 27 2023

Status

approved