login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A324131 Number of permutations of [n] that avoid the shuffle pattern s-k-t, 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

Table of n, a(n) for n=0..23.

Sergey Kitaev, Partially Ordered Generalized Patterns, Discrete Math. 298 (2005), no. 1-3, 212-229.

FORMULA

From Petros Hadjicostas, Oct 30 2019: (Start)

Let b(n) = A049774(n) = number of permutations avoiding a consecutive 123 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).]

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

From Petros Hadjicostas, Nov 01 2019: (Start)

In a permutation of [n] that contains the shuffle pattern s-k-t, 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

Cf. A049774.

Sequence in context: A266332 A007405 A324130 * A221988 A329788 A177518

Adjacent sequences:  A324128 A324129 A324130 * A324132 A324133 A324134

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Feb 16 2019

EXTENSIONS

More terms from Petros Hadjicostas, Oct 30 2019 using Kitaev's (2005) recurrence

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 26 20:36 EDT 2020. Contains 337374 sequences. (Running on oeis4.)