|
|
A165546
|
|
Number of permutations of length n that avoid the patterns 3412 and 2413.
|
|
2
|
|
|
1, 1, 2, 6, 22, 90, 395, 1823, 8741, 43193, 218704, 1129944, 5937728, 31656472, 170892498, 932625326, 5138618526, 28554124650, 159874462032, 901243508380, 5111776163584, 29155580007964, 167139065156182, 962618219420046
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {3>1, 3>4, 1>2, 4>2} of length 4. That is, the number of length n permutations having no subsequences of length 4 in which the third element is the largest and the second element is the smallest. - Sergey Kitaev, Dec 11 2020
|
|
LINKS
|
|
|
FORMULA
|
A(x*B(x)) = (B(x)-1)/(x*B(x)^2), where B(x) is the o.g.f. for A000257 and A(x) is the o.g.f. for A165546. This can be proven using the generating function equation at the end of section 3 of Miner and Pantone's paper. - Michael D. Weiner, Jul 02 2024
a(n) ~ 2^(5*n + 8) / (81 * sqrt(Pi) * n^(5/2) * 5^(n + 1/2)). - Vaclav Kotesovec, Jul 05 2024
G.f.: (x - F(x))/x^2, where F(x) is the compositional inverse of x*B(x) and B(x) is the o.g.f. for A000257. This follows from Michael Weiner's comment above. - Alexander Burstein, Aug 02 2024
|
|
EXAMPLE
|
There are 22 permutations of length 4 that avoid these two patterns, so a(4)=22.
|
|
MATHEMATICA
|
nmax = 30; A[_] = 0; Do[A[x_] = x^4*A[x]^3 + (5*x - 11)*x^2*A[x]^2 + (3*x + 10)*x*A[x] - 9*x + 1 + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x] (* Vaclav Kotesovec, Jul 05 2024 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(13)-a(14) (obtained by brute force enumeration) from Stephen DeSalvo, Sep 23 2015
|
|
STATUS
|
approved
|
|
|
|