cp's OEIS Frontend

A176734 a(n) = (n+7)*a(n-1) + (n-1)*a(n-2), a(-1)=0, a(0)=1.

%I A176734 #15 May 29 2016 09:20:28
%S A176734 1,8,73,746,8425,104084,1395217,20157542,312129649,5155334720,
%T A176734 90449857081,1679650774658,32908313146393,678322072223756,
%U A176734 14672571587601985,332293083938376254,7862829504396683617,194024597448534426872,4984283037788104293289,133083801736564331309210
%N A176734 a(n) = (n+7)*a(n-1) + (n-1)*a(n-2), a(-1)=0, a(0)=1.
%C A176734 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=8 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 {A049388(n) = (n+7)!/7!}. 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 A176734 E.g.f. (exp(-x)/(1-x))*(1/(1-x)^8) = exp(-x)/(1-x)^9, equivalent to the given recurrence.
%F A176734 a(n) = A086764(n+8,8).
%F A176734 a(n) = (-1)^n*2F0(9,-n;;1). - _Benedict W. J. Irwin_, May 29 2016
%e A176734 Necklaces and 8 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*c8(1), (binomial(4,2)*!2)*c8(2), and 1*c8(4) with the subfactorials !n:=A000166(n) (see the necklace comment there) and the c8(n):=A049388(n) numbers for the pure 8-cord problem (see the remark on the e.g.f. for the k cords problem in A000153; here for k=8: 1/(1-x)^8). This adds up as 9 + 4*2*8 + (6*1)*72 + 7920 = 8425 = a(4).
%t A176734 nxt[{n_,a_,b_}]:={n+1,b,(n+8)b+n*a}; Transpose[NestList[nxt,{1,1,8},20]][[2]] (* _Harvey P. Dale_, Mar 19 2013 *)
%t A176734 Table[(-1)^n HypergeometricPFQ[{9, -n}, {}, 1], {n, 0, 20}] (* _Benedict W. J. Irwin_, May 29 2016 *)
%Y A176734 Cf. A176733 (necklaces and k=7 cords).
%K A176734 nonn,easy
%O A176734 0,2
%A A176734 _Wolfdieter Lang_, Jul 14 2010