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

0, 1, 2, 7, 32, 181, 1214, 9403, 82508, 808393, 8743994, 103459471, 1328953592, 18414450877, 273749755382, 4345634192131, 73362643649444, 1312349454922513, 24796092486996338, 493435697986613143, 10315043624498196944

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=2 and n zeros not on a line. This is a special case of Theorem 2.3 of Seok-Zun Song et al. Extremes of permanents of (0,1)-matrices, pp. 201-202. - Jaap Spies, Dec 12 2003

Starting (1, 2, 7, 32, ...) = inverse binomial transform of A001710 starting (1, 3, 12, 60, 360, 2520, ...). - Gary W. Adamson, Dec 25 2008

This sequence appears in Euler's analysis of the divergent series 1 - 1! + 2! - 3! + 4! ..., see Sandifer. For information about this and related divergent series see A163940. - Johannes W. Meijer, Oct 16 2009

a(n+1)=:b(n), n>=1, enumerates the ways to distribute n beads labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and two indistinguishable, ordered, fixed cords, each allowed to have any number of beads. Beadless necklaces as well as beadless cords contribute each a factor 1 in the counting, e.g., b(0):= 1*1 = 1. See A000255 for the description of a fixed cord with beads.

This produces for b(n) the exponential (aka binomial) convolution of the subfactorial sequence {A000166(n)} and {(n+1)!}={A000042(n+1)}. This follows from the general problem with only k indistinguishable, ordered, fixed cords which has e.g.f. 1/(1-x)^k, and the pure necklace problem (no necklaces with one bead allowed) with e.g.f. for the subfactorials. Therefore also the recurrence b(n) = (n+1)*b(n-1) + (n-1)*b(n-2) with b(-1)=0 and b(0)=1 holds.

This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams (Feb 27 2010). - Wolfdieter Lang, Jun 02 2010

a(n) is a function of the subfactorials..sf... A000166(n) a(n) = (n*sf(n+1) - (n+1)*sf(n))/(2*n*(n-1)*(n+1)),n>1, with offset 1. - Gary Detlefs, Nov 06 2010

For even k the sequence a(n) (mod k) is purely periodic with exact period a divisor of k, while for odd k the sequence a(n) (mod k) is purely periodic with exact period a divisor of 2*k. See A047974. - Peter Bala, Dec 04 2017

Examples

			Necklaces and 2 cords problem. For n=4 one considers the following weak 2 part compositions of 4: (4,0), (3,1), (2,2), and (0,4), where (1,3) does not appear because there are no necklaces with 1 bead. These compositions contribute respectively sf(4)*1,binomial(4,3)*sf(3)*c2(1), (binomial(4,2)*sf(2))*c2(2), and 1*c2(4) with the subfactorials sf(n):=A000166(n) (see the necklace comment there) and the c2(n):=(n+1)! numbers for the pure 2 cord problem (see the above given remark on the e.g.f. for the k cords problem; here for k=2: 1/(1-x)^2). This adds up as 9 + 4*2*2 + (6*1)*6 + 120 = 181 = b(4) = A000153(5). - _Wolfdieter Lang_, Jun 02 2010
G.f. = x + 2*x^2 + 7*x^3 + 32*x^4 + 181*x^5 + 1214*x^6 + 9403*x^7 + 82508*x^8 + ...
		

References

• Brualdi, Richard A. and Ryser, Herbert J., Combinatorial Matrix Theory, Cambridge NY (1991), Chapter 7.
• J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 188.
• 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

• Reinhard Zumkeller, Table of n, a(n) for n = 0..250
• Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, 19 (2012), #P7. - From _N. J. A. Sloane_, Feb 06 2013
• Anders Claesson, Giulio Cerbai, Dana C. Ernst, and Hannah Golab, Pattern-avoiding Cayley permutations via combinatorial species, arXiv:2407.19583 [math.CO], 2024.
• Hannah Golab, Pattern avoidance in Cayley permutations, Master's Thesis, Northern Arizona Univ. (2024). See p. 41.
• Simon Plouffe, Exact formulas for integer sequences.
• Ed Sandifer, Divergent Series, How Euler Did It, MAA Online, June 2006. - From _Johannes W. Meijer_, Oct 16 2009
• Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, Special issue on the Combinatorial Matrix Theory Conference (Pohang, 2002). Linear Algebra Appl. 373 (2003), 197-210.

Crossrefs

Cf. A000255, A000261, A001909, A001910, A090010, A055790, A090012-A090016.

Cf. A001710. - Gary W. Adamson, Dec 25 2008

a(n) = A086764(n + 1, 2). A000255 (necklaces with one cord). - Wolfdieter Lang, Jun 02 2010

Programs

Haskell

a000153 n = a000153_list !! n
a000153_list = 0 : 1 : zipWith (+)
   (zipWith (*) [0..] a000153_list) (zipWith (*) [2..] $ tail a000153_list)
-- Reinhard Zumkeller, Mar 05 2012

Maple

f:= n-> floor(((n+1)!+1)/e): g:=n-> (n*f(n+1)-(n+1)*f(n))/(2*n*(n-1)*(n+1)):seq( g(n), n=2..20); # Gary Detlefs, Nov 06 2010
a := n -> `if`(n=0,0,hypergeom([3,-n+1],[],1))*(-1)^(n+1); seq(simplify(a(n)), n=0..20); # Peter Luschny, Sep 20 2014
0, seq(simplify(KummerU(-n + 1, -n - 1, -1)), n = 1..20); # Peter Luschny, May 10 2022

Mathematica

nn = 20; Prepend[Range[0, nn]!CoefficientList[Series[Exp[-x]/(1 - x)^3, {x, 0, nn}], x], 0]  (* Geoffrey Critzer, Oct 28 2012 *)
RecurrenceTable[{a[0]==0,a[1]==1,a[n]==n a[n-1]+(n-2)a[n-2]},a,{n,20}] (* Harvey P. Dale, May 08 2013 *)
a[ n_] := If[ n < 1, 0, (n - 1)! SeriesCoefficient[ Exp[ -x] / (1 - x)^3, {x, 0, n - 1}]]; (* Michael Somos, Jun 01 2013 *)
a[ n_] := SeriesCoefficient[ HypergeometricPFQ[ {1, 3}, {}, x / (x + 1)] x / (x + 1), {x, 0, n}]; (* Michael Somos, Jun 01 2013 *)

PARI

x='x+O('x^66); concat([0],Vec(x*serlaplace(exp(-x)/(1-x)^3)))  \\ Joerg Arndt, May 08 2013

Sage

it = sloane.A000153.gen(0,1,2); [next(it) for i in range(21)] # Zerinvary Lajos, May 15 2009

Formula

E.g.f.: ( 1 - x )^(-3)*exp(-x), for offset 1.

a(n) = round(1/2*(n^2 + 3*n + 1)*n!/exp(1))/n , n>=1. - Simon Plouffe, Mar 1993

a(n) = (1/2) * A055790(n). - Gary Detlefs, Jul 12 2010

G.f.: hypergeom([1,3],[],x/(x+1))/(x+1). - Mark van Hoeij, Nov 07 2011

G.f.: (1+x)^2/(2*x*Q(0)) - 1/(2*x) - 1, where Q(k) = 1 - 2*k*x - x^2*(k + 1)^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 08 2013

G.f.: -1/G(0), where G(k) = 1 + 1/(1 - (1+x)/(1 + x*(k+1)/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 01 2013

G.f.: x/Q(0), where Q(k) = 1 - 2*x*(k+1) - x^2*(k+1)*(k+3)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 02 2013

a(n) = hypergeom([3, -n+1], [], 1)*(-1)^(n+1) for n>=1. - Peter Luschny, Sep 20 2014

a(n) = KummerU(-n + 1, -n - 1, -1) for n >= 1. - Peter Luschny, May 10 2022

a(n) = (n^2 + 3*n + 1)*Gamma(n,-1)/(2*exp(1)) + (1 + n/2)*(-1)^n for n >= 1. - Martin Clever, Apr 06 2023