cp's OEIS Frontend

A324138 Number of permutations of [n] that avoid the shuffle pattern s-k-t, where s = 123 and t = 132.

%I A324138 #17 Nov 01 2019 03:00:46
%S A324138 1,1,2,6,24,120,720,5020,39755,351518,3425572,36419844,419026188,
%T A324138 5182797757,68535001302,964404124479,14383519018582,226579159065496,
%U A324138 3758349089828472,65466833442028670,1194655878120996337,22788580047064423474,453513206778006345040
%N A324138 Number of permutations of [n] that avoid the shuffle pattern s-k-t, where s = 123 and t = 132.
%H A324138 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 A324138 Let b(n) = A049774(n) = number of permutations of [n] that avoid consecutive pattern s = 123 and c(n) = A111004(n) = number of permutations of [n] that avoid consecutive pattern t = 132. Then a(n) = Sum_{i = 0..n-1} binomial(n-1,i) * (b(i)*a(n-1-i) + c(i)*a(n-1-i) - b(i)*c(n-1-i)) for n >= 1 with a(0) = b(0) = c(0) = 1. [This follows from the recurrence for C_n on p. 220 in Kitaev (2005).] - _Petros Hadjicostas_, Nov 01 2019
%e A324138 From _Petros Hadjicostas_, Nov 01 2019: (Start)
%e A324138 In a permutation of [n] that contains the shuffle pattern s-k-t, where s = 123 and t = 132, 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..6, all permutations of [n] avoid this shuffle pattern (since we need at least seven numbers to get this pattern). Hence, a(n) = n! for n = 0..6.
%e A324138 For n = 7, k should be equal to 7, and for the pattern s = 123 we have binomial(6,3) = 20 choices: 123, 124, 125, ..., 456. The corresponding permutations of [7] that contain this shuffle pattern are 1237465, 1247365, 1257364, ..., 4567132. Thus, a(7) = 7! - 20 = 5020. (End)
%Y A324138 Cf. A000142, A049774, A111004.
%K A324138 nonn
%O A324138 0,3
%A A324138 _N. J. A. Sloane_, Feb 16 2019
%E A324138 More terms from _Petros Hadjicostas_, Nov 01 2019