login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%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