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

1, 1, 2, 6, 24, 114, 600, 3372, 19824, 120426, 749976, 4762644, 30723792, 200778612, 1326360048, 8842981848, 59425117152, 402092408346, 2737156004376, 18732169337604, 128806616999184, 889479590046108, 6165939982059600, 42891532191557736, 299307319060137504

Offset: 0

Author

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

Keywords

• nonn

Comments

Hankel transform is A083667, the number of different antisymmetric relations on n labeled points. - Paul Barry, Jun 26 2008

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

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

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n=1..200 from Vincenzo Librandi)
• Michael H. Albert, Christian Bean, Anders Claesson, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, PermPAL database.
• Elena Barcucci, Alberto Del Lungo, Elisa Pergola, and Renzo Pinzani, Permutations avoiding an increasing number of length-increasing forbidden subsequences, Discrete Mathematics and Theoretical Computer Science 4, 2000, 31-44.
• 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.
• Eric Weisstein's World of Mathematics, Legendre Polynomial.

Crossrefs

Cf. A000108, A047891.

Programs

Maple

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);

Mathematica

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 *)
Table[2^(n-1) (LegendreP[n-1, 2] - LegendreP[n-3, 2])/(2n-3), {n, 1, 20}] (* Vladimir Reshetnikov, Nov 01 2015 *)

PARI

x='x+O('x^50); Vec(x*(2-2*x-(1-8*x+4*x^2)^(1/2))) \\ Altug Alkan, Nov 02 2015

Formula

G.f.: 1 + x*(2 - 2*x - (1 - 8*x + 4*x^2)^(1/2)). - corrected by Vaclav Kotesovec, Oct 11 2012

a(n) = 2*A047891(n-1), n>=2. - Philippe Deléham, Aug 17 2007

Recurrence: (n-1)*a(n) = 4*(2*n-5)*a(n-1) - 4*(n-4)*a(n-2). - Vaclav Kotesovec, Oct 11 2012

a(n) ~ sqrt(26*sqrt(3)-45)*(4+2*sqrt(3))^n/(sqrt(8*Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 11 2012

From Vladimir Reshetnikov, Nov 01 2015: (Start)

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

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

(End)

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

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

Extensions

a(0)=1 prepended by Alois P. Heinz, Dec 13 2020