|
| |
|
|
A324132
|
|
Number of permutations of [n] that avoid the shuffle pattern s-k-t, where s = 1 and t = 1234.
|
|
1
|
|
|
|
1, 1, 2, 6, 24, 120, 715, 4946, 38963, 344350, 3374300, 36309360, 425630742, 5398849407, 73675463140, 1076309968529, 16759420085633, 277094358530356, 4848092369455556, 89489787445905318, 1738016295746132796, 35427829798218756153, 756269443056959088424, 16871986369868627423375
(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) = 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).]
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)
|
|
|
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 = 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.
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)
|
|
|
CROSSREFS
|
Cf. A000142, A117158.
Sequence in context: A324135 A177531 A121987 * A177524 A223905 A164872
Adjacent sequences: A324129 A324130 A324131 * A324133 A324134 A324135
|
|
|
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
|
| |
|
|
