login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000261 a(n) = n*a(n-1) + (n-3)*a(n-2), with a(1) = 0, a(2) = 1.
(Formerly M2949 N1189)
19
0, 1, 3, 13, 71, 465, 3539, 30637, 296967, 3184129, 37401155, 477471021, 6581134823, 97388068753, 1539794649171, 25902759280525, 461904032857319, 8702813980639617, 172743930157869827, 3602826440828270029, 78768746000235327495, 1801366114380914335441 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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

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.

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

REFERENCES

Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, 19 (2012), #P7. - From N. J. A. Sloane, Feb 06 2013

Brualdi, Richard A. and Ryser, Herbert J., Combinatorial Matrix Theory, Cambridge NY (1991), Chapter 7.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 188.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, Lin. Algebra and its Applic. 373 (2003), pp. 197-210.

LINKS

T. D. Noe, Table of n, a(n) for n=1..102

FORMULA

E.g.f.: exp(-x)/(1-x)^4 for offset -1.

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

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

G.f.: x^2*hypergeom([1,4],[],x/(x+1))/(x+1). - Mark van Hoeij, Nov 07 2011

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

a(n) = hypergeometric([4,-n+2],[],1)*(-1)^n for n>=2. - Peter Luschny, Sep 20 2014

EXAMPLE

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

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

MAPLE

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

seq(a(n), n=1..30);  # Alois P. Heinz, Nov 03 2012

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

MATHEMATICA

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

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

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 *)

CROSSREFS

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

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

Cf. A000153 (necklaces and two cords). - Wolfdieter Lang, Jun 02 2010

Sequence in context: A233824 A192239 A192936 * A111140 A137983 A059032

Adjacent sequences:  A000258 A000259 A000260 * A000262 A000263 A000264

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Vladeta Jovovic, Jan 07 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 29 13:14 EDT 2017. Contains 284270 sequences.