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,3

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n=1..200 from Vincenzo Librandi)

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

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

Example

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

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

Prog

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

Crossrefs

Cf. A000108, A047891.

Sequence in context: A245233 A228907 A209625 * A134664 A324133 A171448

Adjacent sequences: A054869 A054870 A054871 * A054873 A054874 A054875

Keyword

nonn

Author

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

Extensions

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

Status

approved