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

1, 0, 1, 2, 7, 30, 157, 972, 6961, 56660, 516901, 5225670, 57999271, 701216922, 9173819257, 129134686520, 1946194117057, 31268240559432, 533506283627401, 9634381345852650, 183586751854827751, 3681369418442407670, 77492344539145388821, 1708512949279640961732

Offset: 0

Author

N. J. A. Sloane, R. K. Guy

Keywords

• easy
• nonn
• nice

Comments

Denominator of continued fraction given by C(n) = [ 1; 2,3,4,...n ]. Cf. A001040. - Amarnath Murthy, May 02 2001

If initial 1 is omitted, CONTINUANT transform of 0, 1, 2, 3, 4, 5, ...

Number of deco polyominoes of height n having no 1-cell columns. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. Example: a(2)=1 because the vertical and horizontal dominoes are the deco polyominoes of height 2, of which only the vertical domino does not have 1-cell columns. a(n)=A121554(n,0). - Emeric Deutsch, Aug 16 2006

For positive n, a(n) equals the permanent of the n X n tridiagonal matrix with 1's along the superdiagonal and the subdiagonal, and consecutive integers from 0 to n-1 along the main diagonal (see Mathematica code below). - John M. Campbell, Jul 08 2011

Conjecture: 2*n!*a(n) is the number of open tours by a rook on an (n X 2) chessboard which starts and ends at the same line of length n. - Mikhail Kurkov, Nov 19 2019

Examples

			G.f. = 1 + x^2 + 2*x^3 + 7*x^4 + 30*x^5 + 157*x^6 + 972*x^7 + 6961*x^8 + ...
a(5) = 4*a(4) + a(3) = 4*7+2 = 30.
See A058279 and A058307 for similar recurrences and e.g.f.s. - _Wolfdieter Lang_, May 19 2010
		

References

• Archimedeans Problems Drive, Eureka, 20 (1957), 15.
• M. E. Larsen, Summa Summarum, A. K. Peters, Wellesley, MA, 2007; see p. 35. [From N. J. A. Sloane, Jan 29 2009]
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• T. D. Noe, Table of n, a(n) for n = 0..100
• E. Barcucci, A. Del Lungo and R. Pinzani, "Deco" polyominoes, permutations and random generation, Theoretical Computer Science, 159, 1996, 29-42.
• S. B. Ekhad, Problem 10356, Amer. Math. Monthly, 101 (1994), 75. [From _N. J. A. Sloane_, Jan 29 2009]
• N. J. A. Sloane, Transforms
• Eric Weisstein's World of Mathematics, Continued Fraction Constants
• Eric Weisstein's World of Mathematics, Generalized Continued Fraction

Crossrefs

A column of A058294.

The square roots of the terms of A144656.

See also the constant in A060997.

Cf. A121554, A001040. A058798

Programs

GAP

a:=[0,1];; for n in [3..25] do a[n]:=(n-1)*a[n-1]+a[n-2]; od; Concatenation([1], a); # G. C. Greubel, Sep 20 2019

Haskell

a001053 n = a001053_list !! n
a001053_list = 1 : 0 :
   zipWith (+) a001053_list (zipWith (*) [1..] $ tail a001053_list)
-- Reinhard Zumkeller, Nov 02 2011

Magma

I:=[0,1]; [1] cat [n le 2 select I[n] else (n-1)*Self(n-1) + Self(n-2): n in [1..25]]; // G. C. Greubel, Sep 20 2019

Maple

a[0]:=1: a[1]:=0: for n from 2 to 23 do a[n]:=(n-1)*a[n-1]+a[n-2] od: seq(a[n],n=0..23); # Emeric Deutsch, Aug 16 2006

Mathematica

a[0]=1; a[1] =0; a[n_]:= (n-1)*a[n-1] + a[n-2]; Table[a[n], {n, 0, 21}] (* Robert G. Wilson v, Feb 24 2005 *)
a[0] = 1; a[1] = 0; a[n_] := Permanent[SparseArray[{{i_, i_} :> i-1, Band[{2, 1}] -> 1, Band[{1, 2}] -> 1}, {n, n}]]; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 20}] (* John M. Campbell, Jul 08 2011, updated by Jean-François Alcover, Nov 14 2016 *)
RecurrenceTable[{a[0]==1,a[1]==0,a[n]==(n-1)a[n-1]+a[n-2]},a,{n,30}] (* Harvey P. Dale, Jan 31 2013 *)
a[ n_] := With[ {m = Abs@n}, If[ m < 2, Boole[m == 0],
Gamma[m] HypergeometricPFQ[{3/2 - m/2, 1 - m/2}, {2, 2 - m, 1 - m}, 4]]]; (* Michael Somos, Nov 30 2018 *)

PARI

{a(n) = contfracpnqn(vector(abs(n), i, i))[2, 2]}; /* Michael Somos, Sep 25 2005 */

Sage

def A001053(n):
    if n < 3: return 1 if n != 1 else 0
    return gamma(n)*hypergeometric([3/2-n/2,1-n/2], [2,2-n,1-n], 4)
[round(A001053(n).n(100)) for n in (0..23)] # Peter Luschny, Sep 11 2014

Formula

a(n) = a(-n). for all n in Z. - Michael Somos, Sep 25 2005

E.g.f.: -Pi*(BesselI(1,2)*BesselY(0, 2*I*sqrt(1-x)) + I*BesselY(1, 2*I)*BesselI(0, 2*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

a(n) = 2*K_1(2)*I_n(-2)+2*I_1(2)*K_n(2), where In(z) is the modified Bessel function of the first kind and Kn(x) is the modified Bessel function of the second kind. - Alexander R. Povolotsky, Jan 26 2011

Limit_{n->infinity} a(n)/(n-1)! = BesselI(1,2) = 1.590636854637329... (A096789). - Vaclav Kotesovec, Jan 05 2013, corrected Mar 02 2013

a(n+1) = Sum_{k = 0..floor((n-1)/2)} (n-2*k-1)!*binomial(n-k-1,k) * binomial(n-k,k+1). Cf. A058798. - Peter Bala, Aug 01 2013

a(n) = Gamma(n)*hypergeometric([3/2-n/2, 1-n/2], [2, 2-n, 1-n], 4) for n >= 3. - Peter Luschny, Sep 11 2014

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, Feb 09 2017

Observed: a(n) = A096789*(n-1)!*(1 + 1/(n-1) + 1/(2*(n-1)^2) + O((n-1)^-3)). - A.H.M. Smeets, Aug 19 2018

Extensions

More terms from James Sellers, Sep 19 2000