login
a(n) = n*a(n-1) + (n-2)*a(n-2), with a(0) = 0, a(1) = 1.
(Formerly M1791 N0706)
34

%I M1791 N0706 #119 Jul 30 2024 05:33:59

%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 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 Anders Claesson, Giulio Cerbai, Dana C. Ernst, and Hannah Golab, <a href="https://arxiv.org/abs/2407.19583">Pattern-avoiding Cayley permutations via combinatorial species</a>, arXiv:2407.19583 [math.CO], 2024.

%H Hannah Golab, <a href="http://danaernst.com/scholarship/GolabThesis.pdf">Pattern avoidance in Cayley permutations</a>, Master's Thesis, Northern Arizona Univ. (2024). See p. 41.

%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_