A230557 The number of 123-avoiding simple involutions of length n.

1, 2, 0, 0, 2, 3, 2, 5, 10, 17, 22, 44, 68, 127, 184, 356, 530, 1017, 1502, 2906, 4312, 8351, 12388, 24067, 35748, 69577, 103404, 201642, 299882, 585691, 871498, 1704509, 2537522, 4969153, 7400782, 14508938, 21617096, 42422023, 63226948, 124191257, 185155568, 363985681, 542815792, 1067892398, 1592969006

Offset

1,2

Comments

An interval in a permutation is a set of contiguous indices such that the set of values of these indices under the permutation is also contiguous. A permutation is simple if it has no proper intervals (those of length more than 1 and less than the whole permutation). - Charles R Greathouse IV, Nov 06 2013

Links

Table of n, a(n) for n=1..45.

Miklós Bóna, Cheyne Homberger, Jay Pantone, and Vincent Vatter, Pattern-avoiding involutions: exact and asymptotic enumeration, arxiv:1310.7003, 2013.

Formula

G.f.: x*(-1-2*x+x^6+2*x^3+6*x^5+2*x^7+4*x^5*(-3*x^4-2*x^2+1)^(1/2)+2*x^7*(-3*x^4-2*x^2+1)^(1/2)+x^4*(-3*x^4-2*x^2+1)^(1/2)+2*x^6*(-3*x^4-2*x^2+1)^(1/2)-2*x*(-3*x^4-2*x^2+1)^(1/2)-(-3*x^4-2*x^2+1)^(1/2)+x^2+3*x^4)/(3*x^6+2*x^6*(-3*x^4-2*x^2+1)^(1/2)+5*x^4+3*x^4*(-3*x^4-2*x^2+1)^(1/2)+x^2-1-(-3*x^4-2*x^2+1)^(1/2)).

a(n) ~ (2*sqrt(3)+3 + (-1)^n*(2*sqrt(3)-3)) * 3^(n/2) / (12 * sqrt(2*Pi*n)). - Vaclav Kotesovec, Jan 27 2015

Example

a(8) = 5 because there are 5 simple involutions of length 8 which avoid the pattern 123: 58371642, 64827153, 68375142, 75382614, and 75842613.

Prog

(PARI) x='x+O('x^66); Vec((-1-2*x+x^6+2*x^3+6*x^5+2*x^7+4*x^5*(-3*x^4-2*x^2+1)^(1/2)+2*x^7*(-3*x^4-2*x^2+1)^(1/2)+x^4*(-3*x^4-2*x^2+1)^(1/2)+2*x^6*(-3*x^4-2*x^2+1)^(1/2)-2*x*(-3*x^4-2*x^2+1)^(1/2)-(-3*x^4-2*x^2+1)^(1/2)+x^2+3*x^4)/(3*x^6+2*x^6*(-3*x^4-2*x^2+1)^(1/2)+5*x^4+3*x^4*(-3*x^4-2*x^2+1)^(1/2)+x^2-1-(-3*x^4-2*x^2+1)^(1/2))) \\ Joerg Arndt, Nov 05 2013

Crossrefs

Cf. A111111, A230551-A230556.

Sequence in context: A215889 A195022 A146095 * A327950 A364806 A024870

Adjacent sequences: A230554 A230555 A230556 * A230558 A230559 A230560

Keyword

nonn

Author

Jay Pantone, Nov 05 2013

Status

approved