

A324131


Number of permutations of [n] that avoid the shuffle pattern skt, where s = 1 and t = 123.


0



1, 1, 2, 6, 24, 116, 657, 4260, 31144, 253400, 2271250, 22234380, 236042879, 2700973070, 33139335352, 433996381926, 6042468288640, 89124117755852, 1388234052651161, 22771513253008320, 392354340340237176, 7084700602143004688, 133785708212530414358, 2636998678988431607188
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


LINKS



FORMULA

Let b(n) = A049774(n) = number of permutations avoiding a consecutive 123 pattern. Then a(n) = 2*a(n1)  b(n1) + Sum_{i = 1..n1} binomial(n1,i) * b(i) * a(n1i) for n >= 1 with a(0) = b(0) = 1. [See the recurrence for C_n on p. 220 of Kitaev (2005).]
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), then A'(x) = (1 + B(x)) * A(x)  B(x) with A(0) = B(0) = 1. [Theorem 16, p. 219, in Kitaev (2005)] (End)


EXAMPLE

In a permutation of [n] that contains the shuffle pattern skt, where s = 1 and t = 123, 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..4, all permutations of [n] avoid this shuffle pattern (since we need at least five numbers to get this pattern). Hence, a(n) = n! for n = 0..4.
For n = 5, the permutations of [n] that contain this shuffle pattern should have k = 5 and the last three numbers in these permutations (with pattern t) should be one of the choices 123, 124, 134, and 234. The corresponding permutations that contain this shuffle pattern are 45123, 35124, 25134, and 15234. Hence a(5) = 5!  4 = 116. (End)


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



