|
%I M1791 N0706 #106 May 02 2023 06:23:48
%S 0,1,2,7,32,181,1214,9403,82508,808393,8743994,103459471,1328953592,
%T 18414450877,273749755382,4345634192131,73362643649444,
%U 1312349454922513,24796092486996338,493435697986613143,10315043624498196944
%N a(n) = n*a(n-1) + (n-2)*a(n-2), with a(0) = 0, a(1) = 1.
%C With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=2 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 Starting (1, 2, 7, 32, ...) = inverse binomial transform of A001710 starting (1, 3, 12, 60, 360, 2520, ...). - _Gary W. Adamson_, Dec 25 2008
%C This sequence appears in Euler's analysis of the divergent series 1 - 1! + 2! - 3! + 4! ..., see Sandifer. For information about this and related divergent series see A163940. - _Johannes W. Meijer_, Oct 16 2009
%C a(n+1)=: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 two 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 {(n+1)!}={A000042(n+1}. This follows from the general problem with only k indistinguishable, ordered, fixed cords which has e.g.f. 1/(1-x)^k, and the pure necklace problem (no necklaces with one bead allowed) with e.g.f. for the subfactorials. Therefore also the recurrence b(n) = (n+1)*b(n-1) + (n-1)*b(n-2) with b(-1)=0 and b(0)=1 holds.
%C 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
%C a(n) is a function of the subfactorials..sf... A000166(n) a(n) = (n*sf(n+1) - (n+1)*sf(n))/(2*n*(n-1)*(n+1)),n>1, with offset 1. - _Gary Detlefs_, Nov 06 2010
%C For even k the sequence a(n) (mod k) is purely periodic with exact period a divisor of k, while for odd k the sequence a(n) (mod k) is purely periodic with exact period a divisor of 2*k. See A047974. - _Peter Bala_, Dec 04 2017
%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 Reinhard Zumkeller, <a href="/A000153/b000153.txt">Table of n, a(n) for n = 0..250</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 Simon Plouffe, <a href="http://www.plouffe.fr/simon/exact.htm">Exact formulas for integer sequences.</a>
%H Ed Sandifer, <a href="https://www.maa.org/sites/default/files/pdf/editorial/euler/How%20Euler%20Did%20It%2032%20divergent%20series.pdf">Divergent Series</a>, How Euler Did It, MAA Online, June 2006. - From _Johannes W. Meijer_, Oct 16 2009
%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), 197-210.
%F E.g.f.: ( 1 - x )^(-3)*exp(-x), for offset 1.
%F a(n) = round(1/2*(n^2 + 3*n + 1)*n!/exp(1))/n , n>=1. - _Simon Plouffe_, March 1993
%F a(n) = (1/2) * A055790(n). - _Gary Detlefs_, Jul 12 2010
%F G.f.: hypergeom([1,3],[],x/(x+1))/(x+1). - _Mark van Hoeij_, Nov 07 2011
%F G.f.: (1+x)^2/(2*x*Q(0)) - 1/(2*x) - 1, where Q(k) = 1 - 2*k*x - x^2*(k + 1)^2/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, May 08 2013
%F G.f.: -1/G(0), where G(k) = 1 + 1/(1 - (1+x)/(1 + x*(k+1)/G(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Aug 01 2013
%F G.f.: x/Q(0), where Q(k) = 1 - 2*x*(k+1) - x^2*(k+1)*(k+3)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, Oct 02 2013
%F a(n) = hypergeom([3, -n+1], [], 1))*(-1)^(n+1) for n>=1. - _Peter Luschny_, Sep 20 2014
%F a(n) = KummerU(-n + 1, -n - 1, -1) for n >= 1. - _Peter Luschny_, May 10 2022
%F a(n) = (n^2 + 3*n + 1)*Gamma(n,-1)/(2*exp(1)) + (1 + n/2)*(-1)^n for n >= 1. - _Martin Clever_, Apr 06 2023
%e Necklaces and 2 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)*c2(1), (binomial(4,2)*sf(2))*c2(2), and 1*c2(4) with the subfactorials sf(n):=A000166(n) (see the necklace comment there) and the c2(n):=(n+1)! numbers for the pure 2 cord problem (see the above given remark on the e.g.f. for the k cords problem; here for k=2: 1/(1-x)^2). This adds up as 9 + 4*2*2 + (6*1)*6 + 120 = 181 = b(4) = A000153(5). - _Wolfdieter Lang_, Jun 02 2010
%e G.f. = x + 2*x^2 + 7*x^3 + 32*x^4 + 181*x^5 + 1214*x^6 + 9403*x^7 + 82508*x^8 + ...
%p f:= n-> floor(((n+1)!+1)/e): g:=n-> (n*f(n+1)-(n+1)*f(n))/(2*n*(n-1)*(n+1)):seq( g(n), n=2..20); # _Gary Detlefs_, Nov 06 2010
%p a := n -> `if`(n=0,0,hypergeom([3,-n+1],[],1))*(-1)^(n+1); seq(simplify(a(n)), n=0..20); # _Peter Luschny_, Sep 20 2014
%p 0, seq(simplify(KummerU(-n + 1, -n - 1, -1)), n = 1..20); # _Peter Luschny_, May 10 2022
%t nn = 20; Prepend[Range[0, nn]!CoefficientList[Series[Exp[-x]/(1 - x)^3, {x, 0, nn}], x], 0] (* _Geoffrey Critzer_, Oct 28 2012 *)
%t RecurrenceTable[{a[0]==0,a[1]==1,a[n]==n a[n-1]+(n-2)a[n-2]},a,{n,20}] (* _Harvey P. Dale_, May 08 2013 *)
%t a[ n_] := If[ n < 1, 0, (n - 1)! SeriesCoefficient[ Exp[ -x] / (1 - x)^3, {x, 0, n - 1}]]; (* _Michael Somos_, Jun 01 2013 *)
%t a[ n_] := SeriesCoefficient[ HypergeometricPFQ[ {1, 3}, {}, x / (x + 1)] x / (x + 1), {x, 0, n}]; (* _Michael Somos_, Jun 01 2013 *)
%o (Sage) it = sloane.A000153.gen(0,1,2); [next(it) for i in range(21)] # _Zerinvary Lajos_, May 15 2009
%o (Haskell)
%o a000153 n = a000153_list !! n
%o a000153_list = 0 : 1 : zipWith (+)
%o (zipWith (*) [0..] a000153_list) (zipWith (*) [2..] $ tail a000153_list)
%o -- _Reinhard Zumkeller_, Mar 05 2012
%o (PARI) x='x+O('x^66); concat([0],Vec(x*serlaplace(exp(-x)/(1-x)^3))) \\ _Joerg Arndt_, May 08 2013
%Y Cf. A000255, A000261, A001909, A001910, A090010, A055790, A090012-A090016.
%Y Cf. A001710. - _Gary W. Adamson_, Dec 25 2008
%Y a(n) = A086764(n + 1, 2). A000255 (necklaces with one cord). - _Wolfdieter Lang_, Jun 02 2010
%K nonn,easy
%O 0,3
%A _N. J. A. Sloane_
|
