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

Author

Jay Pantone, Nov 05 2013

Keywords

• nonn

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

Examples

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

Links

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

Crossrefs

Cf. A111111, A230551-A230556.

Programs

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

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