|
| |
|
|
A000261
|
|
a(n) = n*a(n-1) + (n-3)*a(n-2).
(Formerly M2949 N1189)
|
|
15
| |
|
|
0, 1, 3, 13, 71, 465, 3539, 30637, 296967, 3184129, 37401155, 477471021, 6581134823, 97388068753, 1539794649171, 25902759280525, 461904032857319, 8702813980639617, 172743930157869827, 3602826440828270029
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=3 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
a(n+2)=: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 three 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 the sequence {A001710(n+2)}. See the necklaces and cords problem comment in A000153. Therefore also the recurrence b(n) = (n+2)*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]
|
|
|
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
| T. D. Noe, Table of n, a(n) for n=1..102
|
|
|
FORMULA
| E.g.f.: e^(-x) (1 - x )^(-4), for offset -1.
For offset -1: (1/6)*Sum_{k=0..n} (-1)^k*(n-k+1)*(n-k+2)*(n-k+3)*n!/k! = (1/6)*(A000166(n)+3*A000166(n+1)+3*A000166(n+2)+A000166(n+3)) - Vladeta Jovovic (vladeta(AT)eunet.rs), Jan 07 2003
a(n) = round( GAMMA(n)*(n^3+6*n^2+8*n+1)*exp(-1)/6 ) for n>0 [From Mark van Hoeij (hoeij(AT)math.fsu.edu), Nov 11 2009]
G.f.: x*hypergeom([1,4],[],x/(x+1))/(x+1) - Mark van Hoeij, Nov 07 2011
|
|
|
EXAMPLE
| Necklaces and 3 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)*c3(1), (binomial(4,2)*sf(2))*c3(2), and 1*c3(4) with the subfactorials sf(n):=A000166(n) (see the necklace comment there) and the c3(n):=A001710(n+2) = (n+2)!/2! numbers for the pure 3 cord problem (see the remark on the e.g.f. for the k cords problem in A000153; here for k=3: 1/(1-x)^3). This adds up as 9 + 4*2*3 + (6*1)*12 + 360 = 465 = b(4) = A000261(6). [From Wolfdieter Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de), Jun 02 2010]
|
|
|
CROSSREFS
| Cf. A000255, A000153, A001909, A001910, A090010, A055790, A090012-A090016.
A086764(n+1,3), n>=1. A000153 (necklaces and two cords). [From Wolfdieter Lang (wolfdieter.lang(AT)physik.uni-karlsruhe.de), Jun 02 2010]
Sequence in context: A158882 A192239 A192936 * A111140 A137983 A059032
Adjacent sequences: A000258 A000259 A000260 * A000262 A000263 A000264
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from Vladeta Jovovic (vladeta(AT)eunet.rs), Jan 07 2003
|
| |
|
|
