cp's OEIS Frontend

A324132 Number of permutations of [n] that avoid the shuffle pattern s-k-t, where s = 1 and t = 1234.

%I A324132 #26 Nov 01 2019 02:59:57
%S A324132 1,1,2,6,24,120,715,4946,38963,344350,3374300,36309360,425630742,
%T A324132 5398849407,73675463140,1076309968529,16759420085633,277094358530356,
%U A324132 4848092369455556,89489787445905318,1738016295746132796,35427829798218756153,756269443056959088424,16871986369868627423375
%N A324132 Number of permutations of [n] that avoid the shuffle pattern s-k-t, where s = 1 and t = 1234.
%H A324132 Sergey Kitaev, <a href="http://dx.doi.org/10.1016/j.disc.2004.03.017">Partially Ordered Generalized Patterns</a>, Discrete Math. 298 (2005), no. 1-3, 212-229.
%F A324132 From _Petros Hadjicostas_, Oct 30 2019: (Start)
%F A324132 Let b(n) = A117158(n) = number of permutations avoiding a consecutive 1234 pattern. Then a(n) = 2*a(n-1) - b(n-1) + Sum_{i = 1..n-1} binomial(n-1,i) * b(i) * a(n-1-i) for n >= 1 with a(0) = b(0) = 1. [See the recurrence for C_n on p. 220 of Kitaev (2005).]
%F A324132 E.g.f.: If A(x) is the e.g.f. of (a(n): n >= 0) and B(x) is the e.g.f. of (b(n): n >= 0) (i.e., B(x) = 2/(exp(-x) + cos(x) - sin(x))), then A'(x) = (1 + B(x)) * A(x) - B(x) with A(0) = B(0) = 1. [Theorem 16, p. 219, in Kitaev (2005)] (End)
%e A324132 From _Petros Hadjicostas_, Nov 01 2019: (Start)
%e A324132 In a permutation of [n] that contains the shuffle pattern s-k-t, where s = 1 and t = 1234, k should be greater than the numbers in pattern s and the numbers in pattern t. (The numbers in each of the patterns s and t should be contiguous.) Clearly, for n = 0..5, all permutations of [n] avoid this shuffle pattern (since we need at least six numbers to get this pattern). Hence, a(n) = n! for n = 0..5.
%e A324132 For n = 6, the permutations of [n] that contain this shuffle pattern should have k = 6 and the last four numbers in these permutations (with pattern t) should be one of the choices 1234, 1235, 1245, 1345, and 2345. The corresponding permutations that contain this shuffle pattern are 561234, 461235, 361245, 261345, and 162345. Hence a(6) = 6! - 5 = 715. (End)
%Y A324132 Cf. A000142, A117158.
%K A324132 nonn
%O A324132 0,3
%A A324132 _N. J. A. Sloane_, Feb 16 2019
%E A324132 More terms from _Petros Hadjicostas_, Oct 30 2019 using Kitaev's (2005) recurrence