|
| |
|
|
A000153
|
|
a(n) = n*a(n-1) + (n-2)*a(n-2), with a(0) = 0, a(1) = 1.
(Formerly M1791 N0706)
|
|
22
| |
|
|
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; 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, p. 201-202. - Jaap Spies (j.spies(AT)hccnet.nl), Dec 12 2003
Starting (1, 2, 7, 32,...) = inverse binomial transform of A001710 starting (1, 3, 12, 60, 360, 2520,...). [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 25 2008]
Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), Oct 16 2009: (Start)
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.
(End)
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 ( Febr 27 2010) [From Wolfdieter Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de), Jun 02 2010]
a(n) = (1/2) * A055790(n) [From Gary Detlefs (gdetlefs(AT)aol.com), Jul 12 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 [From Gary Detlefs (gdetlefs(AT)aol.com), 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).
Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, Lin. Algebra and its Applic. 373 (2003), p. 197-210.
|
|
|
LINKS
| Simon Plouffe, Exact formulas for integer sequences.
Ed Sandifer, Divergent Series, How Euler Did It, MAA Online, June 2006. [From Johannes W. Meijer (meijgia(AT)hotmail.com), Oct 16 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, March 1993.
G.f.: hypergeom([1,3],[],x/(x+1))/(x+1) - Mark van Hoeij, Nov 07 2011
|
|
|
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) [From Wolfdieter Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de), Jun 02 2010]
|
|
|
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); [From Gary Detlefs (gdetlefs(AT)aol.com), Nov 06 2010]
|
|
|
PROG
| (Other) sage: it = sloane.A000153.gen(0, 1, 2) sage: [it.next() for i in range(21)] [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 15 2009]
|
|
|
CROSSREFS
| Cf. A000255, A000261, A001909, A001910, A090010, A055790, A090012-A090016.
Cf. A001710 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 25 2008]
a(n) = A086764(n+1,2). A000255 (necklaces with one cord). [From Wolfdieter Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de), Jun 02 2010]
Sequence in context: A121555 A097900 A198891 * A006154 A000987 A006957
Adjacent sequences: A000150 A000151 A000152 * A000154 A000155 A000156
|
|
|
KEYWORD
| nonn,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
