login
a(n) = (n+6)*a(n-1) + (n-1)*a(n-2), a(-1)=0, a(0)=1.
6

%I #11 May 29 2016 09:20:04

%S 1,7,57,527,5441,61959,770713,10391023,150869313,2346167879,

%T 38896509881,684702346767,12752503850497,250514001320647,

%U 5176062576469401,112204510124346479,2546140161382663553,60356495873790805383,1491840283714484609593,38382424018590349736719

%N a(n) = (n+6)*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=7 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 {A001730(n+6) = (n+6)!/6!}. 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)^7) = exp(-x)/(1-x)^8, equivalent to the given recurrence.

%F a(n) = A086764(n+7,7).

%F a(n) = (-1)^n*2F0(8,-n;;1). - _Benedict W. J. Irwin_, May 29 2016

%e Necklaces and 7 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*c7(1), (binomial(4,2)*!2)*c7(2), and 1*c7(4) with the subfactorials !n:=A000166(n) (see the necklace comment there) and the c7(n):=A001730(n+6) numbers for the pure 7-cord problem (see the remark on the e.g.f. for the k-cord problem in A000153; here for k=7: 1/(1-x)^7). This adds up as 9 + 4*2*7 + (6*1)*56 + 5040 = 5441 = a(4).

%t Table[(-1)^n HypergeometricPFQ[{8, -n}, {}, 1], {n, 0, 20}] (* _Benedict W. J. Irwin_, May 29 2016 *)

%Y Cf. A176732 (necklaces and k=6 cords).

%K nonn,easy

%O 0,2

%A _Wolfdieter Lang_, Jul 14 2010