This site is supported by donations to The OEIS Foundation.



Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

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

%I M3965 N1637

%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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 10 20:23 EST 2019. Contains 329909 sequences. (Running on oeis4.)