A319031 Triangle read by rows: T(n,k) is the number of permutations pi of [k] such that s(pi) avoids the pattern 12...n, where s is West's stack-sorting map (1 <= k <= 2^(n-1)-1).

1, 1, 2, 1, 1, 2, 6, 10, 13, 10, 3, 1, 2, 6, 24, 78, 232, 631, 1498, 3017, 4934

Offset

2,3

Comments

We only consider k <= 2^(n-1)-1 because T(n,k) = 0 when k >= 2^(n-1).

It appears that the rows T(n,1), ..., T(n,2^(n-1)-1) are unimodal.

Links

Table of n, a(n) for n=2..22.

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

Example

The only permutation pi of [3] such that s(pi) does not contain the pattern 123 is 231, so T(3,3) = 1.
Triangle begins:
  1,
  1, 2, 1,
  1, 2, 6, 10, 13, 10, 3,
  1, 2, 6, 24, 78, 232, 631, 1498, 3017, 4934, ...
  (not all terms in the fourth row are known).

Crossrefs

Sequence in context: A007736 A107042 A134830 * A022874 A022873 A323739

Adjacent sequences: A319028 A319029 A319030 * A319032 A319033 A319034

Keyword

nonn,tabf,more

Author

Colin Defant, Sep 10 2018

Status

approved