A186739 a(0)=0, a(1)=0; for n>1, a(n) = a(n-1) + (n-2)*a(n-2) + 1.

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

Offset: 0

Author

Olivier Gérard, Nov 02 2012

Keywords

• nonn

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

Crossrefs

Cf. A000085.

Programs

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

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 *)
nxt[{n_,a_,b_}]:={n+1,b,b+a(n-1)+1}; NestList[nxt,{1,0,0},30][[;;,2]] (* Harvey P. Dale, Jul 22 2024 *)

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

Extensions

More terms from Vincenzo Librandi, Dec 24 2012

Edited by Bruno Berselli, Dec 24 2012