login
This site is supported by donations to The OEIS Foundation.

 

Logo

"Email this user" was broken Aug 14 to 9am Aug 16. If you sent someone a message in this period, please send it again.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000153 a(n) = n*a(n-1) + (n-2)*a(n-2), with a(0) = 0, a(1) = 1.
(Formerly M1791 N0706)
24
0, 1, 2, 7, 32, 181, 1214, 9403, 82508, 808393, 8743994, 103459471, 1328953592, 18414450877, 273749755382, 4345634192131, 73362643649444, 1312349454922513, 24796092486996338, 493435697986613143, 10315043624498196944 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

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 a 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

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

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.

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, March 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

EXAMPLE

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 + ...

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(round(evalf(a(n), 100)), n=0..20); # Peter Luschny, Sep 20 2014

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 *)

PROG

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

(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

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

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

Sequence in context: A265165 A097900 A198891 * A006154 A000987 A006957

Adjacent sequences:  A000150 A000151 A000152 * A000154 A000155 A000156

KEYWORD

nonn,easy

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified August 20 17:05 EDT 2017. Contains 290836 sequences.