login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001910 a(n) = n*a(n-1) + (n-5)*a(n-2).
(Formerly M3965 N1637)
24

%I M3965 N1637 #32 Feb 06 2015 19:39:19

%S 0,1,5,31,227,1909,18089,190435,2203319,27772873,378673901,5551390471,

%T 87057596075,1453986832381,25762467303377,482626240281739,

%U 9530573107600319,197850855756232465,4307357140602486869,98125321641110663023,2334414826276390013171

%N a(n) = n*a(n-1) + (n-5)*a(n-2).

%C With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=5 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+4)=: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 k=5 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 {A001720(n+4) = (n+4)!/4!}. See the necklaces and cords problem comment in A000153. Therefore also the recurrence b(n) = (n+4)*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="/A001910/b001910.txt">Table of n, a(n) for n = 3..100</a>

%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,5), n>=3.

%F E.g.f. with offset -1: (exp(-x)/(1-x))*(1-x)^5 = exp(-x)/(1-x)^6. - _Wolfdieter Lang_, Jun 02 2010

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

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

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

%p a := n -> `if`(n=3,0, hypergeom([6,-n+4],[],1))*(-1)^n;

%p seq(round(evalf(a(n),100)), n=3..20); # _Peter Luschny_, Sep 20 2014

%t t = {0, 1}; Do[AppendTo[t, n*t[[-1]] + (n - 5) t[[-2]]], {n, 5, 20}]; t (* _T. D. Noe_, Aug 17 2012 *)

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

%Y A001909 (necklaces and four cords).

%K nonn

%O 3,3

%A _N. J. A. Sloane_

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 05:48 EDT 2024. Contains 371265 sequences. (Running on oeis4.)