A000261 - OEIS

%I M2949 N1189 #61 Jan 05 2025 04:44:35

%S 0,1,3,13,71,465,3539,30637,296967,3184129,37401155,477471021,

%T 6581134823,97388068753,1539794649171,25902759280525,461904032857319,

%U 8702813980639617,172743930157869827,3602826440828270029,78768746000235327495,1801366114380914335441

%N a(n) = n*a(n-1) + (n-3)*a(n-2), with a(1) = 0, a(2) = 1.

%C With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=3 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+2)=: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 three 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 {A001710(n+2)}. See the necklaces and cords problem comment in A000153. Therefore also the recurrence b(n) = (n+2)*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="/A000261/b000261.txt">Table of n, a(n) for n=1..102</a>

%H Roland Bacher, <a href="https://doi.org/10.37236/2522">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 E.g.f.: exp(-x)/(1-x)^4 for offset -1.

%F For offset -1: (1/6)*Sum_{k=0..n} (-1)^k*(n-k+1)*(n-k+2)*(n-k+3)*n!/k! = (1/6)*(A000166(n)+3*A000166(n+1)+3*A000166(n+2)+A000166(n+3)). - _Vladeta Jovovic_, Jan 07 2003

%F a(n+1) = round( GAMMA(n)*(n^3+6*n^2+8*n+1)*exp(-1)/6 ) for n>0. - _Mark van Hoeij_, Nov 11 2009

%F G.f.: x^2*hypergeom([1,4],[],x/(x+1))/(x+1). - _Mark van Hoeij_, Nov 07 2011

%F E.g.f. for offset -1: 1/(exp(x)*(1-x)^4) = 1/E(0) where E(k) = 1 - 4*x/(1 + 3*x/(2 - 3*x + 4*x/(3 - 2*x + 3*x/(4 - x - 4/(1 + x^3*(k+1)/E(k+1)))))); (continued fraction, 3rd kind, 6-step). - _Sergei N. Gladkovskii_, Sep 21 2012

%F a(n) = hypergeometric([4,-n+2],[],1)*(-1)^n for n>=2. - _Peter Luschny_, Sep 20 2014

%e Necklaces and 3 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)*c3(1), (binomial(4,2)*sf(2))*c3(2), and 1*c3(4) with the subfactorials sf(n):=A000166(n) (see the necklace comment there) and the c3(n):=A001710(n+2) = (n+2)!/2! numbers for the pure 3 cord problem (see the remark on the e.g.f. for the k cords problem in A000153; here for k=3: 1/(1-x)^3). This adds up as 9 + 4*2*3 + (6*1)*12 + 360 = 465 = b(4) = A000261(6). - _Wolfdieter Lang_, Jun 02 2010

%e G.f. = x^2 + 3*x^3 + 13*x^4 + 71*x^5 + 465*x^6 + 3539*x^7 + 30637*x^8 + ...

%p a:= proc(n) a(n):= `if`(n<3, n-1, n*a(n-1) +(n-3)*a(n-2)) end:

%p seq(a(n), n=1..30);  # _Alois P. Heinz_, Nov 03 2012

%p a := n -> `if`(n=1,0,hypergeom([4,-n+2],[],1))*(-1)^(n); seq(round(evalf(a(n), 100)), n=1..22); # _Peter Luschny_, Sep 20 2014

%t nn=20;Prepend[Range[0,nn]!CoefficientList[Series[Exp[-x]/ (1-x)^4, {x,0,nn}],x],0]  (* _Geoffrey Critzer_, Nov 03 2012 *)

%t a[ n_] := SeriesCoefficient[ x^2 HypergeometricPFQ[ {1, 4}, {}, x / (1 + x)] / (1 + x), {x, 0, n}]; (* _Michael Somos_, May 04 2014 *)

%t a[ n_] := If[ n < 2, 0, With[{m = n - 1}, Round[ Gamma[m] (m^3 + 6 m^2 + 8 m + 1) Exp[-1]/6]]]; (* _Michael Somos_, May 04 2014 *)

%Y Cf. A000255, A000153, A001909, A001910, A090010, A055790, A090012-A090016.

%Y Cf. A086764(n+1,3), n>=1.

%Y Cf. A000153 (necklaces and two cords). - _Wolfdieter Lang_, Jun 02 2010

%K nonn,changed

%O 1,3

%A _N. J. A. Sloane_

%E More terms from _Vladeta Jovovic_, Jan 07 2003