A319030 Triangle read by rows: T(n,k) is the number of permutations pi of [n] such that pi has k+1 valleys and s(pi) avoids the patterns 132 and 321, where s is West's stack-sorting map (0 <= k <= floor((n-1)/2)).

1, 2, 4, 2, 8, 14, 16, 64, 8, 32, 240, 92, 64, 800, 624, 34, 128, 2464, 3248, 534, 256, 7168, 14336, 4736, 144, 512, 19968, 56448, 31200, 2852, 1024, 53760, 204288, 169920, 31120, 604, 2048, 140800, 692736, 808896, 247280, 14412

Offset

1,2

Comments

Row sums give A319028.

Links

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

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

Formula

G.f.: G(x,y) + x^3*y*((d/dx)G(x,y))^2, where G(x,y) = (1 - 2x - sqrt((1-2x)^2 - 4x^2*y))/(2x*y) is the generating function of A091894.

Example

Triangle begins:
    1,
    2,
    4,    2,
    8,   14,
   16,   64,    8,
   32,  240,   92,
   64,  800,  624,  34,
  128, 2464, 3248, 534,
  ...

Mathematica

DeleteCases[Flatten[CoefficientList[Series[(1 - 2 x - Sqrt[(1 - 2 x)^2 - 4 x^2 y])/(2 x*y) + x^3*y (D[(1 - 2 x - Sqrt[(1 - 2 x)^2 - 4 x^2 y])/(2 x*y), x])^2, {x, 0, 10}], {x, y}]], 0]

Crossrefs

Cf. A319028, A091894.

Sequence in context: A228890 A051288 A120434 * A285335 A187619 A008303

Adjacent sequences: A319027 A319028 A319029 * A319031 A319032 A319033

Keyword

easy,nonn,tabf

Author

Colin Defant, Sep 10 2018

Status

approved