A324916 Triangle read by rows: T(n,k) is the number of 3-stack-sortable permutations of [n] with k descents (0 <= k <= n-1).

1, 1, 1, 1, 4, 1, 1, 11, 11, 1, 1, 25, 62, 25, 1, 1, 50, 252, 252, 50, 1, 1, 91, 833, 1644, 833, 91, 1, 1, 154, 2375, 8183, 8183, 2375, 154, 1, 1, 246, 6045, 33655, 58007, 33655, 6045, 246, 1, 1, 375, 14049, 119737, 327269, 327269, 119737, 14049, 375, 1

Offset

1,5

Comments

Bona has proven that the polynomial Sum_{k=0..n-1} T(n,k)*x^k is always symmetric and unimodal. He has conjectured that it has only real roots.

Links

Colin Defant, Table of n, a(n) for n = 1..945

M. Bona, Symmetry and unimodality in t-stack-sortable permutations, J. Combin. Theory Ser. A, 98 (2002), 201-209.

M. Bona, A survey of stack-sorting disciplines, Electron. J. Combin., 9 (2003), Article #A1.

C. Defant, Counting 3-stack-sortable permutations, arXiv:1903.09138 [math.CO], 2019.

C. Defant, Preimages under the stack-sorting algorithm, arXiv:1511.05681 [math.CO], 2015-2018; Graphs Combin., 33 (2017), 103-122.

Formula

See the paper "Counting 3-Stack-Sortable Permutations" for a recurrence that generates this sequence.

Example

T(5,1)=25 because there are 25 3-stack-sortable permutations of {1,2,3,4,5} with exactly 1 descent.

Crossrefs

Row sums give A134664.

Sequence in context: A152970 A154986 A154983 * A156534 A168287 A221987

Adjacent sequences: A324913 A324914 A324915 * A324917 A324918 A324919

Keyword

nonn,tabl

Author

Colin Defant, Mar 18 2019

Status

approved