

A001910


a(n) = n*a(n1) + (n5)*a(n2).
(Formerly M3965 N1637)


17



0, 1, 5, 31, 227, 1909, 18089, 190435, 2203319, 27772873, 378673901, 5551390471, 87057596075, 1453986832381, 25762467303377, 482626240281739, 9530573107600319, 197850855756232465, 4307357140602486869, 98125321641110663023, 2334414826276390013171
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

3,3


COMMENTS

With offset 1, permanent of (0,1)matrix of size n X (n+d) with d=5 and n zeros not on a line. This is a special case of Theorem 2.3 of SeokZun Song et al. Extremes of permanents of (0,1)matrices, p. 201202.  Jaap Spies, Dec 12 2003
a(n+4)=: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 k=5 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 {A001720(n+4) = (n+4)!/4!}. See the necklaces and cords problem comment in A000153. Therefore also the recurrence b(n) = (n+4)*b(n1) + (n1)*b(n2) 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, 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).
SeokZun Song et al., Extremes of permanents of (0,1)matrices, Lin. Algebra and its Applic. 373 (2003), p. 197210.


LINKS

T. D. Noe, Table of n, a(n) for n = 3..100


FORMULA

E.g.f. with offset 1: (exp(x)/(1x))*(1x)^5 = exp(x)/(1x)^6. [From Wolfdieter Lang, Jun 02 2010]
G.f.: x*hypergeom([1,6],[],x/(x+1))/(x+1)  Mark van Hoeij, Nov 07 2011


EXAMPLE

Necklaces and 5 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)*c5(1), (binomial(4,2)*sf(2))*c5(2), and 1*c5(4) with the subfactorials sf(n):=A000166(n) (see the necklace comment there) and the c5(n):=A001720(n+4) numbers for the pure 5 cord problem (see the remark on the e.g.f. for the k cords problem in A000153; here for k=5: 1/(1x)^5). This adds up as 9 + 4*2*5 + (6*1)*30 + 1680 = 1909 = b(4) = A001910(8). [From Wolfdieter Lang, Jun 02 2010]


MATHEMATICA

t = {0, 1}; Do[AppendTo[t, n*t[[1]] + (n  5) t[[2]]], {n, 5, 20}]; t (* T. D. Noe, Aug 17 2012 *)


CROSSREFS

Cf. A000255, A000153, A000261, A001909, A001910, A055790, A090012A090016.
a(n) = A086764(n+1,5), n>=3. A001909 (necklaces and four cords).
Sequence in context: A058309 A226924 A192950 * A052773 A062147 A213048
Adjacent sequences: A001907 A001908 A001909 * A001911 A001912 A001913


KEYWORD

nonn


AUTHOR

N. J. A. Sloane.


STATUS

approved



