login
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.
0

%I #38 Aug 01 2023 19:33:00

%S 1,1,1,1,4,1,1,13,8,2,1,41,49,23,6,1,131,276,198,90,24,1,428,1509,

%T 1556,982,444,120,1,1429,8184,11812,9678,5856,2640,720,1,4861,44473,

%U 88566,91959,68820,40800,18360,5040,1,16795,243334,662732,863296,775134,555828,325200,146160,40320

%N 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.

%C It appears that no recurrence or g.f. is known. - _N. J. A. Sloane_, Oct 13 2015

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000028">The number of stack-sorts needed to sort a permutation</a>

%H Julian West, <a href="https://dspace.mit.edu/handle/1721.1/13641">Permutations with forbidden subsequences; and, stack-sortable permutations</a>, Ph.D. thesis, Massachusetts Institute of Technology, Dept. of Mathematics, 1990. See p. 76.

%F T(n,0) = 1, T(n,1) = A000108(n) - 1. - _Joerg Arndt_, Sep 27 2015

%e Triangle begins:

%e 1;

%e 1, 1;

%e 1, 4, 1;

%e 1, 13, 8, 2;

%e 1, 41, 49, 23, 6;

%e 1, 131, 276, 198, 90, 24;

%e 1, 428, 1509, 1556, 982, 444, 120;

%e 1, 1429, 8184, 11812, 9678, 5856, 2640, 720;

%e 1, 4861, 44473, 88566, 91959, 68820, 40800, 18360, 5040;

%e ...

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

%Y Row sums give A000142.

%Y Cf. A000108.

%K nonn,tabl

%O 1,5

%A _Christian Stump_, Sep 24 2015

%E Definition edited by _N. J. A. Sloane_, Oct 13 2015

%E More terms from _Christian Stump_, Oct 19 2015

%E Rows n=7-10 from Julian West's thesis added by _Alois P. Heinz_, Jun 27 2023