A165546 - OEIS

%I #56 Aug 03 2024 07:16:21

%S 1,1,2,6,22,90,395,1823,8741,43193,218704,1129944,5937728,31656472,

%T 170892498,932625326,5138618526,28554124650,159874462032,901243508380,

%U 5111776163584,29155580007964,167139065156182,962618219420046

%N Number of permutations of length n that avoid the patterns 3412 and 2413.

%C 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

%H Daniel Birmajer, Juan B. Gil, and Michael D. Weiner, <a href="https://arxiv.org/abs/1803.07727">A family of Bell transformations</a>, arXiv:1803.07727 [math.CO], 2018.

%H Alice L. L. Gao, Sergey Kitaev, <a href="https://arxiv.org/abs/1903.08946">On partially ordered patterns of length 4 and 5 in permutations</a>, arXiv:1903.08946 [math.CO], 2019.

%H Alice L. L. Gao, Sergey Kitaev, <a href="https://doi.org/10.37236/8605">On partially ordered patterns of length 4 and 5 in permutations</a>, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.

%H Darla Kremer and Wai Chee Shiu, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00042-6">Finite transition matrices for permutations avoiding pairs of length four patterns</a>, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.

%H Samuel Miner, Jay Pantone, <a href="https://arxiv.org/abs/1802.00483">Completing the Structural Analysis of the 2x4 Permutation Classes</a>, arXiv:1802.00483 [math.CO], 2018.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Enumerations_of_specific_permutation_classes#Classes_avoiding_two_patterns_of_length_4">Permutation classes avoiding two patterns of length 4</a>.

%F 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

%F a(n) ~ 2^(5*n + 8) / (81 * sqrt(Pi) * n^(5/2) * 5^(n + 1/2)). - _Vaclav Kotesovec_, Jul 05 2024

%F 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

%e There are 22 permutations of length 4 that avoid these two patterns, so a(4)=22.

%t 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 *)

%Y Cf. A000257.

%K nonn,more

%O 0,3

%A _Vincent Vatter_, Sep 21 2009

%E a(13)-a(14) (obtained by brute force enumeration) from _Stephen DeSalvo_, Sep 23 2015

%E a(15)-a(23) from _David Bevan_, Oct 03 2015

%E a(0)=1 prepended by _Alois P. Heinz_, Dec 09 2015