cp's OEIS Frontend

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

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