cp's OEIS Frontend

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

%I A054872 #60 Feb 16 2025 08:32:42
%S A054872 1,1,2,6,24,114,600,3372,19824,120426,749976,4762644,30723792,
%T A054872 200778612,1326360048,8842981848,59425117152,402092408346,
%U A054872 2737156004376,18732169337604,128806616999184,889479590046108,6165939982059600,42891532191557736,299307319060137504
%N A054872 Number of (12345, 13245, 21345, 23145, 31245, 32145)-avoiding permutations.
%C A054872 Hankel transform is A083667, the number of different antisymmetric relations on n labeled points. - _Paul Barry_, Jun 26 2008
%C A054872 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 A054872 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 A054872 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 A054872 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 A054872 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 A054872 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 A054872 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 A054872 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 A054872 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LegendrePolynomial.html">Legendre Polynomial</a>.
%F A054872 G.f.: 1 + x*(2 - 2*x - (1 - 8*x + 4*x^2)^(1/2)). - corrected by _Vaclav Kotesovec_, Oct 11 2012
%F A054872 a(n) = 2*A047891(n-1), n>=2. - _Philippe Deléham_, Aug 17 2007
%F A054872 Recurrence: (n-1)*a(n) = 4*(2*n-5)*a(n-1) - 4*(n-4)*a(n-2). - _Vaclav Kotesovec_, Oct 11 2012
%F A054872 a(n) ~ sqrt(26*sqrt(3)-45)*(4+2*sqrt(3))^n/(sqrt(8*Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 11 2012
%F A054872 From _Vladimir Reshetnikov_, Nov 01 2015: (Start)
%F A054872 a(n) = 2^(n-1)*(LegendreP_{n-1}(2) - LegendreP_{n-3}(2))/(2*n-3).
%F A054872 For n > 2, a(n) = 6*hypergeom([2-n,3-n], [2], 3).
%F A054872 (End)
%F A054872 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 A054872 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 A054872 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 A054872 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 A054872 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 A054872 Table[2^(n-1) (LegendreP[n-1, 2] - LegendreP[n-3, 2])/(2n-3), {n, 1, 20}] (* _Vladimir Reshetnikov_, Nov 01 2015 *)
%o A054872 (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 A054872 Cf. A000108, A047891.
%K A054872 nonn
%O A054872 0,3
%A A054872 Elisa Pergola (elisa(AT)dsi.unifi.it), May 26 2000
%E A054872 a(0)=1 prepended by _Alois P. Heinz_, Dec 13 2020