login
a(n) = (n+1)*(a(n-1)/n + a(n-2)), with a(0)=1, a(1)=2.
10

%I #43 Jul 06 2023 07:02:01

%S 1,2,6,16,50,156,532,1856,6876,26200,104456,428352,1821976,7959056,

%T 35857200,165592576,785514512,3812387616,18948962656,96194028800,

%U 498931946016,2638959243712,14234346694976

%N a(n) = (n+1)*(a(n-1)/n + a(n-2)), with a(0)=1, a(1)=2.

%C a(n) is also the number of fixed points in all involutions (= self-inverse permutations) of {1,2,...,n+1}. Example: a(2)=6 because the involutions of {1,2,3} are 1'2'3', 1'32, 32'1, and 213', containing 6 fixed points (marked). - _Emeric Deutsch_, May 28 2009

%C a(n) is also the number of adjacent transpositions in all involutions (= self-inverse permutations) of {1,2,...,n+2}. Example: a(2)=6 because the involutions of {1,2,3,4} are 1234, 124*3, 13*24, 1432, 2*134, 2*14*3, 3214, 3412, 4231, and 43*21, containing 6 adjacent transpositions (marked with *). - _Emeric Deutsch_, Jun 08 2009

%C It might be more natural to shift the index by 1 and prefix a(0)=0, then this would be exactly the first differences of A000085, and satisfy a(n)=n for n<3, a(n)/n = a(n-1)/(n-1) - a(n-2). - _M. F. Hasler_, Dec 25 2010

%D rec.puzzles, Dec 10 1995

%H Vincenzo Librandi, <a href="/A013989/b013989.txt">Table of n, a(n) for n = 0..200</a>

%F E.g.f: (1+x+x^2)*exp((1+x/2)*x). - _Benoit Cloitre_, Apr 28 2005, corrected by _Vaclav Kotesovec_, Oct 07 2012

%F a(n) = A000085(n) * (n+1).

%F a(n) = A000085(n+2) - A000085(n+1). - _M. F. Hasler_, Dec 26 2010

%F a(n) ~ n*exp(sqrt(n)-n/2-1/4)*n^(n/2)/sqrt(2). - _Vaclav Kotesovec_, Oct 07 2012

%F E.g.f. simplifies to x*exp(x + x^2/2) if offset is 1. - _David Callan_, Nov 11 2012

%F G.f.: T(0)/x^2 - 1/x^2, where T(k) = 1 - (k+1)*x^2/( (k+1)*x^2 - (1-x)^2/T(k+1) ); (continued fraction). - _Sergei N. Gladkovskii_, Nov 03 2013

%F a(n) = (n+1) * (-i/sqrt(2))^n * H_n(i/sqrt(2)), where H_n(x) is the Hermite polynomial. - _Vladimir Reshetnikov_, Nov 12 2016

%F 0 = a(n)*(+a(n+1) - 2*a(n+2) - 2*a(n+3) + a(n+4)) + a(n+1)*(+3*a(n+2) + a(n+3) - a(n+4)) + a(n+2)*(-2*a(n+2) + a(n+3)) for all n in Z. - _Michael Somos_, Nov 12 2016

%F a(n) = A099020(n+1,1). - _R. J. Mathar_, Jul 06 2023

%e G.f. = 1 + 2*x + 6*x^2 + 16*x^3 + 50*x^4 + 156*x^5 + 532*x^6 + ...

%p A013989 := proc(n) option remember; if n <=1 then n+1; else (n+1)*(A013989(n-1)/n+A013989(n-2)); fi; end;

%t Table[n!*SeriesCoefficient[(1+x+x^2)*E^((1+x/2)*x),{x,0,n}],{n,0,20}] (* _Vaclav Kotesovec_, Oct 07 2012 *)

%t Table[(n + 1) (-I/Sqrt[2])^n HermiteH[n, I/Sqrt[2]], {n, 0, 30}] (* _Vladimir Reshetnikov_, Nov 12 2016 *)

%o (PARI) x='x+O('x^66); Vec(serlaplace((1+x+x^2)*exp((1+x/2)*x))) \\ _Joerg Arndt_, May 04 2013

%o (PARI) {a(n) = if( n<0, 0, n! * polcoeff( (1 + x + x^2) * exp( x * (1 + x/2 + O(x^n))), n))}; /* _Michael Somos_, Nov 12 2016 */

%Y First differences of A000085 (except for a missing leading zero).

%K nonn,easy

%O 0,2

%A _N. J. A. Sloane_, _Dan Hoey_, 1996