

A176732


a(n) = (n+5)*a(n1) + (n1)*a(n2), a(1)=0, a(0)=1.


6



1, 6, 43, 356, 3333, 34754, 398959, 4996032, 67741129, 988344062, 15434831091, 256840738076, 4536075689293, 84731451264186, 1668866557980343, 34563571477305464, 750867999393119889, 17072113130285524982, 405423357986250112699, 10037458628015142154452, 258639509502117306002581
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

a(n) enumerates the possibilities for distributing n beads, n>=1, labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and k=6 indistinguishable, ordered, fixed cords, each allowed to have any number of beads. Beadless necklaces as well as beadless cords contribute a factor 1 in the counting, e.g., a(0):= 1*1 =1. See A000255 for the description of a fixed cord with beads. This produces for a(n) the exponential (aka binomial) convolution of the subfactorial sequence {A000166(n)} and the sequence {A001725(n+5) = (n+5)!/5!}. See the necklaces and cords problem comment in A000153. Therefore the recurrence with inputs 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).


LINKS

Table of n, a(n) for n=0..20.


FORMULA

E.g.f. (exp(x)/(1x))*(1/(1x)^6) = exp(x)/(1x)^7, equivalent to the recurrence.
a(n) = A086764(n+6,6).
a(n) = A090010(n), n>0.  R. J. Mathar, Jul 22 2010
a(n) = (1)^n*hypergeom([n,7],[],1).  Peter Luschny, Apr 25 2015


EXAMPLE

Necklaces and 6 cords problem. For n=4 one considers the following weak 2part 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 !4*1,binomial(4,3)*!3*c6(1), (binomial(4,2)*2)*c6(2), and 1*c6(4) with the subfactorials !n:=A000166(n) (see the necklace comment there) and the c6(n):=A001725(n+5) numbers for the pure 6cord problem (see the remark on the e.g.f. for the kcord problem in A000153; here for k=6: 1/(1x)^6). This adds up as 9 + 4*2*6 + (6*1)*42 + 3024 = 3333 = a(4).


MAPLE

a := n > hypergeom([n, 7], [], 1)*(1)^n:
seq(simplify(a(n)), n=0..9); # Peter Luschny, Apr 25 2015


MATHEMATICA

Rest[RecurrenceTable[{a[0]==1, a[1]==0, a[n]==(n+5)a[n1]+(n1)a[n2]}, a, {n, 20}]] (* Harvey P. Dale, Oct 01 2012 *)


CROSSREFS

Cf. A000153, A000261, A001909, A001910 (necklaces and k=5 cords), A176732.
Sequence in context: A240653 A220097 A090010 * A062266 A217485 A290783
Adjacent sequences: A176729 A176730 A176731 * A176733 A176734 A176735


KEYWORD

nonn,easy


AUTHOR

Wolfdieter Lang, Jul 14 2010


STATUS

approved



