cp's OEIS Frontend

A176735 a(n) = (n+8)*a(n-1) + (n-1)*a(n-2), a(-1)=0, a(0)=1.

%I A176735 #15 May 27 2016 13:27:21
%S A176735 1,9,91,1019,12501,166589,2394751,36920799,607496041,10622799089,
%T A176735 196677847971,3843107102339,79025598374461,1705654851091749,
%U A176735 38551739502886471,910569176481673319,22431936328103456721,575367515026293191129,15340898308261381733611,424560869593530584247819
%N A176735 a(n) = (n+8)*a(n-1) + (n-1)*a(n-2), a(-1)=0, a(0)=1.
%C A176735 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 A176735 Harvey P. Dale, <a href="/A176735/b176735.txt">Table of n, a(n) for n = 0..400</a>
%F A176735 E.g.f. (exp(-x)/(1-x))*(1/(1-x)^9) = exp(-x)/(1-x)^10, equivalent to the given recurrence.
%F A176735 a(n) = A086764(n+9,9).
%F A176735 a(n) = (-1)^n*2F0(10,-n;;1). - _Benedict W. J. Irwin_, May 27 2016
%e A176735 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 A176735 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 A176735 Table[(-1)^n HypergeometricPFQ[{10, -n}, {}, 1], {n, 0, 20}] (* _Benedict W. J. Irwin_, May 27 2016 *)
%Y A176735 Cf. A176734 (necklaces and k=8 cords).
%K A176735 nonn,easy
%O A176735 0,2
%A A176735 _Wolfdieter Lang_, Jul 14 2010