login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A317555 Triangle read by rows: T(n,k) is the number of preimages of the permutation 21345...n under West's stack-sorting map that have k+1 valleys (1 <= k <= floor((n-1)/2)). 0
1, 4, 12, 2, 32, 16, 80, 80, 5, 192, 320, 60, 448, 1120, 420, 14, 1024, 3584, 2240, 224, 2304, 10752, 10080, 2016, 42, 5120, 30720, 40320, 13440, 840, 11264, 84480, 147840, 73920, 9240, 132, 24576, 225280, 506880, 354816, 73920, 3168 (list; graph; refs; listen; history; text; internal format)
OFFSET

3,2

COMMENTS

If pi is any permutation of [n] with exactly 1 descent, then the number of preimages of pi under West's stack-sorting map that have k+1 valleys is at most T(n,k).

LINKS

Table of n, a(n) for n=3..44.

C. Defant, Preimages under the stack-sorting algorithm, arXiv:1511.05681 [math.CO], 2015-2018.

C. Defant, Preimages under the stack-sorting algorithm, Graphs Combin., 33 (2017), 103-122.

C. Defant, Stack-sorting preimages of permutation classes, arXiv:1809.03123 [math.CO], 2018.

FORMULA

T(n,k) = Sum_{i=1..n-2} Sum_{j=1..k} V(i,j) * V(n-1-i,m+1-j), where V(i,j) = 2^{i-2j+1} * (1/j) * binomial(i-1, 2j-2) * binomial(2j-2, j-1) are the numbers found in the triangle A091894.

EXAMPLE

Triangle begins:

    1;

    4;

   12,    2;

   32,   16;

   80,   80,   5;

  192,  320,  60;

  448, 1120, 420, 14;

  ...

T(1,1) = 1 because the permutation 213 has one preimage under West's stack-sorting map (namely, 231), and this permutation has 2 valleys.

MATHEMATICA

Flatten[Table[Table[Sum[Sum[(2^(i - 2 j + 1)) Binomial[i - 1, 2 j - 2]CatalanNumber[j - 1] (2^((n - 1 - i) - 2 (m + 1 - j) + 1)) Binomial[(n - 1 - i) - 1, 2 (m + 1 - j) - 2] CatalanNumber[(m + 1 - j) - 1], {j, 1, m}], {i, 1, n - 2}], {m, 1, Floor[(n - 1)/2]}], {n, 1, 10}]]

CROSSREFS

Row sums give A002057.

Sequence in context: A104063 A260430 A243347 * A213343 A308518 A307874

Adjacent sequences:  A317552 A317553 A317554 * A317556 A317557 A317558

KEYWORD

easy,nonn,tabf

AUTHOR

Colin Defant, Sep 14 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 9 19:34 EDT 2020. Contains 333362 sequences. (Running on oeis4.)