Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #7 Mar 27 2015 23:11:27
%S 1,10,111,1352,17909,256134,3931555,64441684,1123029513,20730064706,
%T 403978495031,8286870547680,178468044946621,4025739435397822,
%U 94912091598455979,2334250550458513004,59779945135439664785,1591626582328767492474,43990176790179196598143,1260374228606935319612536
%N a(n) = (n+9)*a(n-1) + (n-1)*a(n-2), a(-1)=0, a(0)=1.
%C 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=10 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 {A049398(n) = (n+9)!/9!}. 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).
%F E.g.f. (exp(-x)/(1-x))*(1/(1-x)^10) = exp(-x)/(1-x)^11, equivalent to the given recurrence.
%F a(n) = A086764(n+10,10).
%e Necklaces and 10 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 !4*1,binomial(4,3)*!3*c10(1), (binomial(4,2)*! 2)*c10(2), and 1*c10(4) with the subfactorials !n:=A000166(n) (see the necklace comment there) and the c10(n):=A049398(n) numbers for the pure 10-cord problem (see the remark on the e.g.f. for the k-cord problem in A000153; here for k=10: 1/(1-x)^10). This adds up as 9 + 4*2*10 + (6*1)*110 + 17160 = 17909 = a(4).
%Y Cf. A176735 (necklaces and k=9 cords).
%K nonn,easy
%O 0,2
%A _Wolfdieter Lang_, Jul 14 2010