login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A230557 The number of 123-avoiding simple involutions of length n. 0
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 (list; graph; refs; listen; history; text; internal format)
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 Vince 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 * A024870 A147699 A250023

Adjacent sequences:  A230554 A230555 A230556 * A230558 A230559 A230560

KEYWORD

nonn

AUTHOR

Jay Pantone, Nov 05 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 21 06:25 EST 2018. Contains 299390 sequences. (Running on oeis4.)