login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”).

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A186739 a(0)=0, a(1)=0; for n>1, a(n) = a(n-1) + (n-2)*a(n-2) + 1. 5
0, 0, 1, 2, 5, 12, 33, 94, 293, 952, 3297, 11866, 44837, 175364, 713409, 2993142, 12980869, 57878000, 265571905, 1249497906, 6029792197, 29770252412, 150366096353, 775541397006, 4083595516773, 21921047647912, 119927340050465, 667953531248266, 3786064372560357 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

a(n-1) is the number of times step Y5 is performed when the algorithm of exercise 7.2.1.2--101 in The Art of Computer Programming (volume 4A) is used to generate all involutions of order n. - Don Knuth, Feb 19 2015

REFERENCES

D. E. Knuth, The Art of Computer Programming, Volume 4A, Addison-Wesley, 2011, pages 719-720.

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..200

FORMULA

a(n) = 2*a(n-1)+(n-3)*a(n-2)-(n-3)*a(n-3) with a(0)=a(1)=0, a(2)=1. - Vincenzo Librandi, Dec 24 2012

a(n) ~ sqrt(Pi)/2 * n^(n/2-1/2)*exp(sqrt(n)-n/2-1/4) * (1-5/(24*sqrt(n))). - Vaclav Kotesovec, Dec 26 2012

Sum a(n-1)z^n/n! = exp(z+z^2) erf(z/sqrt(2)). Therefore the asymptotic value of a(n-1) is sqrt(Pi/2) times the asymptotic value of t(n), the number of involutions [sequence A000085], with exponentially small relative error. - Don Knuth, Feb 19 2015

MATHEMATICA

RecurrenceTable[{a[1] == 0, a[2] == 0, a[n] == a[n - 1] + (n - 2) a[n - 2] + 1}, a, {n, 30}] (* Bruno Berselli, Dec 24 2012; typo corrected by Don Knuth, Feb 19 2015 *)

PROG

(MAGMA) I:=[0, 0, 1, 2]; [n le 4 select I[n] else 2*Self(n-1)+(n-4)*Self(n-2)-(n-4)*Self(n-3): n in [1..30]]; // Vincenzo Librandi, Dec 24 2012

CROSSREFS

Cf. A000085.

Sequence in context: A221206 A281489 A225616 * A266292 A004114 A208957

Adjacent sequences:  A186736 A186737 A186738 * A186740 A186741 A186742

KEYWORD

nonn

AUTHOR

Olivier Gérard, Nov 02 2012

EXTENSIONS

More terms from Vincenzo Librandi, Dec 24 2012

Edited by Bruno Berselli, Dec 24 2012

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 2 10:40 EST 2021. Contains 349437 sequences. (Running on oeis4.)