OFFSET
0,2
COMMENTS
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
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
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..200
Michael H. Albert, Christian Bean, Anders Claesson, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, PermPAL database.
Christian Bean, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding, The Electronic Journal of Combinatorics, Volume 31, Issue 3 (2024); arXiv preprint, arXiv:2312.07716 [math.CO], 2023.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao and Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
FORMULA
G.f. satisfies: A(x) = 1 + x*A(x)*(2 - A(x) + A(x)^2) + x^2*A(x)^2*(1 - A(x)).
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) ).
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
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
EXAMPLE
G.f.: A(x) = 1 + 2*x + 6*x^2 + 24*x^3 + 114*x^4 + 598*x^5 + 3336*x^6 +...
where g.f. A = A(x) satisfies the equivalent expressions:
A = 1 + x*(1-A^2)/(1-A) + x^2*(1-A^4)/(1-A) + x^3*(1-A^6)/(1-A) +...
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) +...
MATHEMATICA
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 *)
PROG
(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)}
for(n=0, 25, print1(a(n), ", "))
(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)}
for(n=0, 25, print1(a(n), ", "))
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Sep 08 2013
STATUS
approved