|
%I #12 Sep 14 2018 14:32:22
%S 1,2,6,22,88,364,1522,6374,26640,110980,460716,1906172,7862416,
%T 32341144,132707626,543376774,2220650656,9060011284,36908739316,
%U 150159618964,610186287376,2476912674664,10044874544116,40700948789212,164788263075808,666716080038824
%N Number of permutations pi of [n] such that s(pi) avoids the patterns 132 and 321, where s is West's stack-sorting map.
%C a(n) is the number of permutations of [n] that avoid the patterns 1342, 34251, 35241, and 45231 and also avoid any 3142 pattern that is not part of a 34152 pattern or a 35142 pattern.
%H Colin Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-sorting preimages of permutation classes</a>, arXiv:1809.03123 [math.CO], 2018.
%F G.f.: c(x) - 1 + x^3*(c'(x))^2, where c(x) is the generating function of the Catalan numbers.
%F n*(n + 1)*a(n) - 4*n*(3*n - 2)*a(n-1) + 4*(2*n - 3)*(6*n - 5)*a(n-2) - 16*(2*n - 5)*(2*n - 3)*a(n-3) = 0 with n > 3. - _Bruno Berselli_, Sep 14 2018
%t Rest[CoefficientList[Series[(1 - Sqrt[1 - 4 x] - 5 x + 3 x*Sqrt[1 - 4 x] + 5 x^2)/(x - 4 x^2), {x, 0, 10}], x]]
%t RecurrenceTable[{n (n + 1) a[n] - 4 n (3 n - 2) a[n - 1] + 4 (2 n - 3) (6 n - 5) a[n - 2] - 16 (2 n - 5) (2 n - 3) a[n - 3] == 0, a[1] == 1, a[2] == 2, a[3] == 6}, a, {n, 1, 30}] (* _Bruno Berselli_, Sep 14 2018 *)
%Y Cf. A000108. Row sums of triangles A319029 and A319030.
%K easy,nonn
%O 1,2
%A _Colin Defant_, Sep 10 2018
|
