A228907 - OEIS

%I #35 Jul 24 2024 17:33:09

%S 1,2,6,24,114,598,3336,19402,116302,713368,4455650,28240942,181180912,

%T 1174280146,7677229718,50570040088,335289825874,2235856077798,

%U 14985808827416,100900119437082,682145490613118,4628755102582328,31514118237222850,215214456560655070

%N G.f. satisfies: A(x) = 1 + Sum_{n>=0} x^n * (1 - A(x)^(2*n))/(1 - A(x)).

%C Conjectured to be the number of permutations of length n+1 avoiding the partially ordered pattern (POP) {1>4, 1>5, 2>4, 2>5, 5>3} of length 5. That is, conjectured to be the number of length n+1 permutations having no subsequences of length 5 in which the first and second elements are larger than the elements in positions 4 and 5, and the fifth element is larger than the element in position 3.- _Sergey Kitaev_, Dec 13 2020

%C This conjecture has been proven. It can be restated as the number of size n permutations avoiding 45123, 45132, 45213, 54123, 54132, 54213. - _Christian Bean_, Jul 24 2024

%H Vincenzo Librandi, <a href="/A228907/b228907.txt">Table of n, a(n) for n = 0..200</a>

%H Michael H. Albert, Christian Bean, Anders Claesson, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, <a href="https://permpal.com/perms/basis/45123_45132_45213_54123_54132_54213/">PermPAL database</a>.

%H Christian Bean, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, <a href="https://doi.org/10.37236/12686">Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding</a>, The Electronic Journal of Combinatorics, Volume 31, Issue 3 (2024); <a href="https://arxiv.org/abs/2312.07716">arXiv preprint</a>, arXiv:2312.07716 [math.CO], 2023.

%H Alice L. L. Gao and 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 and 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.

%F G.f. satisfies: A(x) = 1 + x*A(x)*(2 - A(x) + A(x)^2) + x^2*A(x)^2*(1 - A(x)).

%F G.f.: (1/x)*Series_Reversion( x*(1+x+x^2 + sqrt(1-2*x-5*x^2-2*x^3+x^4)) / (2*(1+x)^2) ).

%F Recurrence: n*(2*n+1)*(7*n^2 - 35*n + 34)*a(n) = (126*n^4 - 742*n^3 + 1193*n^2 - 601*n + 78)*a(n-1) - (182*n^4 - 1253*n^3 + 2788*n^2 - 2293*n + 450)*a(n-2) + (56*n^4 - 434*n^3 + 1189*n^2 - 1273*n + 318)*a(n-3) + (n-4)*(2*n-5)*(7*n^2 - 21*n + 6)*a(n-4). - _Vaclav Kotesovec_, Sep 09 2013

%F a(n) ~ c*d^n/n^(3/2), where d = 8/3+14/3*cos(arctan(3*sqrt(3)/13)/3) = 7.29589694323977237... is the root of the equation 1 + 5*d - 8*d^2 + d^3 = 0 and c = sqrt(1/3 + sqrt(7)*cos((4*Pi + arccos(-1/(2*sqrt(7))))/3)/6) / sqrt(Pi) = 0.33910585091755684322274547... - _Vaclav Kotesovec_, Sep 09 2013, updated Mar 17 2024

%e G.f.: A(x) = 1 + 2*x + 6*x^2 + 24*x^3 + 114*x^4 + 598*x^5 + 3336*x^6 +...

%e where g.f. A = A(x) satisfies the equivalent expressions:

%e A = 1 + x*(1-A^2)/(1-A) + x^2*(1-A^4)/(1-A) + x^3*(1-A^6)/(1-A) +...

%e A = 1 + x*(1 + A) + x^2*(1 + A + A^2 + A^3) + x^3*(1 + A + A^2 + A^3 + A^4 + A^5) +...

%t nmax=20;aa=ConstantArray[0,nmax];aa[[1]]=2;Do[AGF=1+Sum[aa[[n]]*x^n,{n,1,j-1}]+koef*x^j;sol=Solve[Coefficient[1+x*AGF*(2-AGF+AGF^2)+x^2*AGF^2*(1-AGF)-AGF,x,j]==0,koef][[1]];aa[[j]]=koef/.sol[[1]],{j,2,nmax}];Flatten[{1,aa}] (* _Vaclav Kotesovec_, Sep 09 2013 *)

%o (PARI) {a(n) = my(A=1+x); for(i=1, n, A = 1 + sum(m=0, n, x^m*sum(k=0, 2*m-1, A^k) + x*O(x^n))); polcoeff(A, n)}

%o for(n=0,25,print1(a(n),", "))

%o (PARI) {a(n) = my(A=1+x); for(i=1, n, A = 1+x*A*(2-A+A^2)+x^2*A^2*(1-A)+x*O(x^n)); polcoeff(A, n)}

%o for(n=0,25,print1(a(n),", "))

%Y Cf. A199548.

%K nonn

%O 0,2

%A _Paul D. Hanna_, Sep 08 2013