|
%I #28 Sep 08 2022 08:45:55
%S 0,0,1,2,5,12,33,94,293,952,3297,11866,44837,175364,713409,2993142,
%T 12980869,57878000,265571905,1249497906,6029792197,29770252412,
%U 150366096353,775541397006,4083595516773,21921047647912,119927340050465,667953531248266,3786064372560357
%N a(0)=0, a(1)=0; for n>1, a(n) = a(n-1) + (n-2)*a(n-2) + 1.
%C 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
%D D. E. Knuth, The Art of Computer Programming, Volume 4A, Addison-Wesley, 2011, pages 719-720.
%H Vincenzo Librandi, <a href="/A186739/b186739.txt">Table of n, a(n) for n = 0..200</a>
%F 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
%F 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
%F 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
%t 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 *)
%o (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
%Y Cf. A000085.
%K nonn
%O 0,4
%A _Olivier Gérard_, Nov 02 2012
%E More terms from _Vincenzo Librandi_, Dec 24 2012
%E Edited by _Bruno Berselli_, Dec 24 2012
|
