|
%I M3576 N1450 #48 Jul 17 2018 13:54:42
%S 0,1,4,21,134,1001,8544,81901,870274,10146321,128718044,1764651461,
%T 25992300894,409295679481,6860638482424,121951698034461,
%U 2291179503374234,45361686034627361,943892592746534964,20592893110265899381,470033715095287415734
%N a(n) = n*a(n-1) + (n-4)*a(n-2), a(2) = 0, a(3) = 1.
%C With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=4 and n zeros not on a line. This is a special case of Theorem 2.3 of Seok-Zun Song et al. Extremes of permanents of (0,1)-matrices, pp. 201-202. - _Jaap Spies_, Dec 12 2003
%C a(n+3)=:b(n), n>=1, enumerates the ways to distribute n beads labeled differently from 1 to n, over a set of (unordered) necklaces, excluding necklaces with exactly one bead, and four indistinguishable, ordered, fixed cords, each allowed to have any number of beads. Beadless necklaces as well as a beadless cords contribute each a factor 1 in the counting, e.g., b(0):= 1*1 =1. See A000255 for the description of a fixed cord with beads.
%C This produces for b(n) the exponential (aka binomial) convolution of the subfactorial sequence {A000166(n)} and the sequence {A001715 (n+3)}. See the necklaces and cords problem comment in A000153. Therefore also the recurrence b(n) = (n+3)*b(n-1) + (n-1)*b(n-2) with b(-1)=0 and b(0)=1 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). - _Wolfdieter Lang_, Jun 02 2010
%D Brualdi, Richard A. and Ryser, Herbert J., Combinatorial Matrix Theory, Cambridge NY (1991), Chapter 7.
%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 188.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A001909/b001909.txt">Table of n, a(n) for n = 2..100</a>
%H Roland Bacher, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p7">Counting Packings of Generic Subsets in Finite Groups</a>, Electr. J. Combinatorics, 19 (2012), #P7. - From _N. J. A. Sloane_, Feb 06 2013
%H Seok-Zun Song et al., <a href="http://dx.doi.org/10.1016/S0024-3795(03)00382-3">Extremes of permanents of (0,1)-matrices</a>, Special issue on the Combinatorial Matrix Theory Conference (Pohang, 2002). Linear Algebra Appl. 373 (2003), pp. 197-210.
%F a(n) = A086764(n+1,4), n>=2.
%F E.g.f.: exp(-x) / (1 - x)^5 = Sum_{k>=0} a(k+3) * x^k / k!. - _Michael Somos_, Feb 19 2003
%F G.f.: x*hypergeom([1,5],[],x/(x+1))/(x+1). - _Mark van Hoeij_, Nov 07 2011
%F a(n) = hypergeom([5,-n+3],[],1))*(-1)^(n+1) for n>=3. - _Peter Luschny_, Sep 20 2014
%e Necklaces and four 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 sf(4)*1, binomial(4,3)*sf(3)*c4(1), (binomial(4,2)*sf(2))*c4(2), and 1*c4(4) with the subfactorials sf(n):=A000166(n) (see the necklace comment there) and the c4(n):=A001715(n+3) = (n+3)!/3! numbers for the pure 4 cord problem (see the remark on the e.g.f. for the k cords problem in A000153; here for k=4: 1/(1-x)^4). This adds up as 9 + 4*2*4 + (6*1)*20 + 840 = 1001 = b(4) = A001909(7). - _Wolfdieter Lang_, Jun 02 2010
%e x^3 + 4*x^4 + 21*x^5 + 134*x^6 + 1001*x^7 + 8544*x^8 + 81901*x^9 + 870274*x^10 + ...
%p a := n -> `if`(n<4,n-2,hypergeom([5,-n+3],[],1))*(-1)^(n+1);
%p seq(round(evalf(a(n), 100)), n=2..22); # _Peter Luschny_, Sep 20 2014
%t t = {0, 1}; Do[AppendTo[t, n*t[[-1]] + (n-4)*t[[-2]]], {n, 4, 20}]; t (* _T. D. Noe_, Aug 17 2012 *)
%t nxt[{n_,a_,b_}]:={n+1,b,b(n+1)+a(n-3)}; NestList[nxt,{3,0,1},20][[All,2]] (* _Harvey P. Dale_, Jul 17 2018 *)
%o (PARI) {a(n) = if( n<2, 0, -contfracpnqn( matrix(2, n, i, j, j - 4*(i==1))) [1, 1])} /* _Michael Somos_, Feb 19 2003 */
%Y Cf. A000255, A000153, A000261, A001910, A090010, A055790, A090012-A090016, A086764. A000261 (necklaces and three cords).
%K nonn
%O 2,3
%A _N. J. A. Sloane_
|
