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 #15 May 27 2016 13:27:21
%S 1,9,91,1019,12501,166589,2394751,36920799,607496041,10622799089,
%T 196677847971,3843107102339,79025598374461,1705654851091749,
%U 38551739502886471,910569176481673319,22431936328103456721,575367515026293191129,15340898308261381733611,424560869593530584247819
%N a(n) = (n+8)*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=9 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 {A049389(n) = (n+8)!/8!}. 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).
%H Harvey P. Dale, <a href="/A176735/b176735.txt">Table of n, a(n) for n = 0..400</a>
%F E.g.f. (exp(-x)/(1-x))*(1/(1-x)^9) = exp(-x)/(1-x)^10, equivalent to the given recurrence.
%F a(n) = A086764(n+9,9).
%F a(n) = (-1)^n*2F0(10,-n;;1). - _Benedict W. J. Irwin_, May 27 2016
%e Necklaces and 9 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*c9(1), (binomial(4,2)*! 2)*c9(2), and 1*c9(4) with the subfactorials !n:=A000166(n) (see the necklace comment there) and the c9(n):=A049389(n) numbers for the pure 9-cord problem (see the remark on the e.g.f. for the k-cord problem in A000153; here for k=9: 1/(1-x)^9). This adds up as 9 + 4*2*9 + (6*1)*90 + 11880 = 12501 = a(4).
%t RecurrenceTable[{a[0]==1,a[1]==9,a[n]==(n+8)a[n-1]+(n-1)a[n-2]},a[n],{n,20}] (* _Harvey P. Dale_, Oct 20 2011 *)
%t Table[(-1)^n HypergeometricPFQ[{10, -n}, {}, 1], {n, 0, 20}] (* _Benedict W. J. Irwin_, May 27 2016 *)
%Y Cf. A176734 (necklaces and k=8 cords).
%K nonn,easy
%O 0,2
%A _Wolfdieter Lang_, Jul 14 2010