login
a(n+1) = n*a(n) + a(n-1) with a(0)=0, a(1)=1.
(Formerly M2863 N1151)
44

%I M2863 N1151 #132 Apr 25 2024 14:57:52

%S 0,1,1,3,10,43,225,1393,9976,81201,740785,7489051,83120346,1004933203,

%T 13147251985,185066460993,2789144166880,44811373131073,

%U 764582487395121,13807296146243251,263103209266016890,5275871481466581051,111056404320064218961,2448516766522879398193

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

%C If the initial 0 and 1 are omitted, CONTINUANT transform of 1, 2, 3, 4, 5, ...

%C a(n+1) is the numerator of the continued fraction given by C(n) = [n, n-1,...,3,2,1], e.g., [1] = 1, [2,1]=3, [3,2,1] = 10/3, [4,3,2,1] = 43/10 etc. Cf. A001053. - _Amarnath Murthy_, May 02 2001

%C Along those lines, a(n) is the denominator of the continued fraction [n,n-1,...3,2,1] and is the numerator of the continued fraction [1,2,3,...,n-1]. - _Greg Dresden_, Feb 20 2020

%C Starting (1, 3, 10, 43, ...) = eigensequence of triangle A127701. - _Gary W. Adamson_, Dec 29 2008

%C For n >=2, a(n) equals the permanent of the (n-1) X (n-1) tridiagonal matrix with 1's along the superdiagonal and the subdiagonal, and consecutive integers from 1 to n along the main diagonal (see Mathematica program below). - _John M. Campbell_, Jul 08 2011

%C Generally, solution of the recurrence a(n+1) = n*a(n) + a(n-1) is a(n) = BesselI(n,-2)*(2*a(0)*BesselK(1,2)-2*a(1)*BesselK(0,2)) + (2*a(0)*BesselI(1,2)+2*a(1)*BesselI(0,2))*BesselK(n,2), and asymptotic is a(n) ~ (a(0)*BesselI(1,2)+a(1)*BesselI(0,2)) * (n-1)!. - _Vaclav Kotesovec_, Jan 05 2013

%C For n > 0: a(n) = A058294(n,n) = A102473(n,n) = A102472(n,1). - _Reinhard Zumkeller_, Sep 14 2014

%C Conjecture: 2*n!*a(n) is the number of open tours by a rook on an (n X 2) chessboard which ends at the opposite line of length n. - _Mikhail Kurkov_, Nov 19 2019

%D Archimedeans Problems Drive, Eureka, 22 (1959), 15.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A001040/b001040.txt">Table of n, a(n) for n = 0..450</a> (first 101 terms from T. D. Noe)

%H C. Cannings, <a href="http://dx.doi.org/10.4236/am.2013.45105">The Stationary Distributions of a Class of Markov Chains</a>, Applied Mathematics, Vol. 4 No. 5, 2013, pp. 769-773. doi: 10.4236/am.2013.45105. See Table 1.

%H T. Doslic and R. Sharafdini, <a href="https://www.researchgate.net/publication/272355505">Hosoya index of splices, bridges and necklaces</a>, Research Gate, 2015.

%H Tomislav Doslic and R. Sharafdini, <a href="https://doi.org/10.1007/978-3-319-31584-3_10">Hosoya Index of Splices, Bridges, and Necklaces</a>, in Distance, Symmetry, and Topology in Carbon Nanomaterials, 2016, pp 147-156. Part of the Carbon Materials: Chemistry and Physics book series (CMCP, volume 9), doi:10.1007/978-3-319-31584-3_10.

%H R. K. Guy, <a href="/A002186/a002186.pdf">Letters to N. J. A. Sloane, June-August 1968</a>

%H S. Janson, <a href="https://hal.inria.fr/hal-00990430/">A divergent generating function that can be summed and analysed analytically</a>, Discrete Mathematics and Theoretical Computer Science; 2010, Vol. 12, No. 2, 1-22.

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ContinuedFractionConstants.html">Continued Fraction Constants</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GeneralizedContinuedFraction.html">Generalized Continued Fraction</a>

%F Generalized Fibonacci sequence for (unsigned) Laguerre triangle A021009. a(n+1) = sum{k=0..floor(n/2), C(n-k, k)(n-k)!/k!}. - _Paul Barry_, May 10 2004

%F a(-n) = a(n) for all n in Z. - _Michael Somos_, Sep 25 2005

%F E.g.f.: -I*Pi*(BesselY(1, 2*I)*BesselI(0, 2*sqrt(1-x)) - I*BesselI(1, 2)*BesselY(0, 2*I*sqrt(1-x))). Such e.g.f. computations were the result of an e-mail exchange with _Gary Detlefs_. After differentiation and putting x=0 one has to use simplifications. See the Abramowitz-Stegun handbook, p. 360, 9.1.16 and p. 375, 9.63. - _Wolfdieter Lang_, May 19 2010

%F Limit_{n->infinity} a(n)/(n-1)! = BesselI(0,2) = 2.279585302336... (see A070910). - _Vaclav Kotesovec_, Jan 05 2013

%F a(n) = 2*(BesselI(0,2)*BesselK(n,2) - BesselI(n,-2)*BesselK(0,2)). - _Vaclav Kotesovec_, Jan 05 2013

%F a(n) = (n-1)!*hypergeometric([1-n/2,1/2-n/2],[1,1-n,1-n], 4) for n >= 2. - _Peter Luschny_, Sep 10 2014

%F 0 = a(n)*(-a(n+2)) + a(n+1)*(+a(n+1) + a(n+2) - a(n+3)) + a(n+2)*(+a(n+2)) for all n in Z. - _Michael Somos_, Sep 13 2014

%F Observed: a(n) = A070910*(n-1)!*(1 + 1/(n-1) + 1/(2*(n-1)^2) + O((n-1)^-3)). - _A.H.M. Smeets_, Aug 19 2018

%F a(n) mod 2 = A166486(n). - _Alois P. Heinz_, Jul 03 2023

%e G.f. = x + x^2 + 3*x^3 + 10*x^4 + 43*x^5 + 225*x^6 + 1393*x^7 + 9976*x^8 + ...

%p A001040 := proc(n)

%p if n <= 1 then

%p n;

%p else

%p (n-1)*procname(n-1)+procname(n-2) ;

%p end if;

%p end proc: # _R. J. Mathar_, Mar 13 2015

%t Table[Permanent[Array[KroneckerDelta[#1, #2]*(#1) + KroneckerDelta[#1, #2 - 1] + KroneckerDelta[#1, #2 + 1] &, {n - 1, n - 1}]], {n, 2, 30}] (* _John M. Campbell_, Jul 08 2011 *)

%t Join[{0},RecurrenceTable[{a[0]==1,a[1]==1,a[n]==n a[n-1]+a[n-2]}, a[n], {n,30}]] (* _Harvey P. Dale_, Aug 14 2011 *)

%t FullSimplify[Table[2(-BesselI[n,-2]BesselK[0,2]+BesselI[0,2]BesselK[n,2]),{n,0,20}]] (* _Vaclav Kotesovec_, Jan 05 2013 *)

%o (PARI) {a(n) = contfracpnqn( vector(abs(n), i, i))[1, 2]}; /* _Michael Somos_, Sep 25 2005 */

%o (Haskell)

%o a001040 n = a001040_list !! n

%o a001040_list = 0 : 1 : zipWith (+)

%o a001040_list (zipWith (*) [1..] $ tail a001040_list)

%o -- _Reinhard Zumkeller_, Mar 05 2013

%o (Sage)

%o def A001040(n):

%o if n < 2: return n

%o return factorial(n-1)*hypergeometric([1-n/2,-n/2+1/2], [1,1-n,1-n], 4)

%o [round(A001040(n).n(100)) for n in (0..23)] # _Peter Luschny_, Sep 10 2014

%o (Magma) a:=[1,1]; [0] cat [n le 2 select a[n] else (n-1)*Self(n-1) + Self(n-2): n in [1..23]]; // _Marius A. Burtea_, Nov 19 2019

%Y A column of A058294. Cf. A001053.

%Y Cf. A127701. - _Gary W. Adamson_, Dec 29 2008

%Y Similar recurrences: A001053, A058279, A058307. - _Wolfdieter Lang_, May 19 2010

%Y Cf. A102472, A102473, A166486.

%K easy,nonn,nice,frac

%O 0,4

%A _N. J. A. Sloane_, _R. K. Guy_

%E Definition clarified by _A.H.M. Smeets_, Aug 19 2018