|
|
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
|
|
|
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 *)
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 *)
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|