login
Number of (12345, 13245, 21345, 23145, 31245, 32145)-avoiding permutations.
6

%I #59 Jul 24 2024 09:20:36

%S 1,1,2,6,24,114,600,3372,19824,120426,749976,4762644,30723792,

%T 200778612,1326360048,8842981848,59425117152,402092408346,

%U 2737156004376,18732169337604,128806616999184,889479590046108,6165939982059600,42891532191557736,299307319060137504

%N Number of (12345, 13245, 21345, 23145, 31245, 32145)-avoiding permutations.

%C Hankel transform is A083667, the number of different antisymmetric relations on n labeled points. - _Paul Barry_, Jun 26 2008

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

%C This conjecture has been proven. There are six sets of permutations avoiding six size five permutations including the two sets discussed in this sequence that are known to match this sequence. A further two are conjectured to match this sequence. - _Christian Bean_, Jul 23 2024

%H Alois P. Heinz, <a href="/A054872/b054872.txt">Table of n, a(n) for n = 0..1000</a> (terms n=1..200 from Vincenzo Librandi)

%H Michael H. Albert, Christian Bean, Anders Claesson, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, <a href="https://permpal.com/perms/search_params/?we_type=cfs&amp;wilf_equivalence=01234%2C+01243%2C+01324%2C+01342%2C+01423%2C+01432">PermPAL database</a>.

%H Elena Barcucci, Alberto Del Lungo, Elisa Pergola, and Renzo Pinzani, <a href="https://hal.inria.fr/hal-00958943">Permutations avoiding an increasing number of length-increasing forbidden subsequences</a>, Discrete Mathematics and Theoretical Computer Science 4, 2000, 31-44.

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LegendrePolynomial.html">Legendre Polynomial</a>.

%F G.f.: 1 + x*(2 - 2*x - (1 - 8*x + 4*x^2)^(1/2)). - corrected by _Vaclav Kotesovec_, Oct 11 2012

%F a(n) = 2*A047891(n-1), n>=2. - _Philippe Deléham_, Aug 17 2007

%F Recurrence: (n-1)*a(n) = 4*(2*n-5)*a(n-1) - 4*(n-4)*a(n-2). - _Vaclav Kotesovec_, Oct 11 2012

%F a(n) ~ sqrt(26*sqrt(3)-45)*(4+2*sqrt(3))^n/(sqrt(8*Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 11 2012

%F From _Vladimir Reshetnikov_, Nov 01 2015: (Start)

%F a(n) = 2^(n-1)*(LegendreP_{n-1}(2) - LegendreP_{n-3}(2))/(2*n-3).

%F For n > 2, a(n) = 6*hypergeom([2-n,3-n], [2], 3).

%F (End)

%F G.f. satisfies: A(x) = x * Sum_{n>=0} ( A(x)/x + 4*x + x/A(x) )^n / (2*4^n). - _Paul D. Hanna_, Mar 24 2016

%F G.f. satisfies: A(x) = x * Sum_{n>=0} ( A(x)/x + 4*x - x/A(x) )^n / 4^n. - _Paul D. Hanna_, Mar 24 2016

%e G.f. = 1 + x + 2*x^2 + 6*x^3 + 24*x^4 + 114*x^5 + 600*x^6 + 3372*x^7 + 19824*x^8 + ...

%p Set j=3 in the following: f := (x,j)->1-(j+1)*x- sqrt(1-2*(j+1)*x+(j-1)^2*x^2); t := (x,j)->sum(k!*x^k, k=1..(j-1)); s := (x,j)->x^(j-2)*(j-1)!*(f(x,j))/(2)+ t(x,j);

%t Table[SeriesCoefficient[x*(2-2*x-(1-8*x+4*x^2)^(1/2)),{x,0,n}],{n,1,20}] (* _Vaclav Kotesovec_, Oct 11 2012 *)

%t Table[2^(n-1) (LegendreP[n-1, 2] - LegendreP[n-3, 2])/(2n-3), {n, 1, 20}] (* _Vladimir Reshetnikov_, Nov 01 2015 *)

%o (PARI) x='x+O('x^50); Vec(x*(2-2*x-(1-8*x+4*x^2)^(1/2))) \\ _Altug Alkan_, Nov 02 2015

%Y Cf. A000108, A047891.

%K nonn

%O 0,3

%A Elisa Pergola (elisa(AT)dsi.unifi.it), May 26 2000

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