%I A000255 M2905 N1166
%S A000255 1,1,3,11,53,309,2119,16687,148329,1468457,16019531,190899411,
%T A000255 2467007773,34361893981,513137616783,8178130767479,138547156531409,
%U A000255 2486151753313617,47106033220679059,939765362752547227
%N A000255 a(n) = n*a(n-1) + (n-1)*a(n-2), a(0) = 1, a(1) = 1.
%C A000255 a(n) counts permutations of [1,...,n+1] having no substring [k,k+1]. 
               - Len Smiley (smiley(AT)math.uaa.alaska.edu), Oct 13 2001
%C A000255 Also a(n-2) = !n/(n - 1) where !n is the subfactorial of n, A000166(n) 
               - Lekraj Beedassy (blekraj(AT)yahoo.com), Jun 18 2002
%C A000255 Also, for n>0, determinant of the tridiagonal n X n matrix M such that 
               M(i,i)=i and for i=1,..,n-1, M(i,i+1)=-1, M(i+1,i)=i. - Mario Catalani 
               (mario.catalani(AT)unito.it), Feb 04 2003
%C A000255 Also, for n>0, maximal permanent of a nonsingular n X n (0,1)-matrix, 
               which is achieved by the matrix with just n-1 0's, all on main diagonal. 
               - Edwin Clark (eclark(AT)math.usf.edu), Oct 28, 2003. For proof see 
               next line.
%C A000255 Proof from Richard Brualdi and Edwin Clark, Nov 15 2003: Let n >=4. Take 
               an n X n (0,1)-matrix A which is nonsingular. It has t >= n-1, 0's, 
               otherwise there will be two rows of all 1's. Let B be the matrix 
               obtained from A by replacing t-(n-1) of A's 0's with 1's. Let D be 
               the matrix with all 1's except for 0's in the first n-1 positions 
               on the diagonal. This matrix is easily seen to be non-singular. Now 
               we have per(A) < = per(B) < = per (D), where the first inequality 
               follows since replacing 0's by 1's cannot decrease the permanent 
               and the second from Corollary 4.4 in the Brualdi et al. reference, 
               which shows that per(D) is the maximum permanent of ANY n X n matrix 
               with n -1 0's. Corollary 4.4 requires n >=4. a(n) for n < 4 can be 
               computed directly.
%C A000255 With offset 1, permanent of (0,1)-matrix of size n X (n+d) with d=1 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, p. 201-202. 
               - Jaap Spies (j.spies(AT)hccnet.nl), Dec 12 2003
%C A000255 Number of fixed-point-free permutations of n+2 that begin with a 2, e.g. 
               for 1234, we have 2143, 2341, 2413, so a(2)=3. Also number of permutations 
               of 2,...,n+2 that have no agreements with 1,...,n+1. E.g. for 123 
               against permutations of 234, we have 234, 342 and 432. Compare A047920. 
               - Jon Perry (perry(AT)globalnet.co.uk), Jan 23 2004. [This can be 
               proved by the standard argument establishing that d(n+2) = (n+1)(d(n+1)+d(n)) 
               for derangements A000166 (n+1 choices of where 1 goes, then either 
               1 is in a transposition, or in a cycle of length at least 3, etc.). 
               - D. G. Rogers (drogers(AT)turing.une.edu.au), Aug 28 2006]
%C A000255 Stirling transform of A006252(n+1)=[1,1,2,4,14,38,...] is a(n)=[1,3,11,
               53,309,...]. - Michael Somos Mar 04 2004
%C A000255 A000255(n+1) is the sequence of numerators of the self-convergents to 
               1/(e-2); see A096654. - Clark Kimberling (ck6(AT)evansville.edu), 
               Jul 01 2004
%C A000255 Euler's interpretation was "fixedpoint-free permutations beginning with 
               2" and he listed the terms up to 148329 (although he was blind at 
               the time). - D. E. Knuth, Jan 25 2007
%C A000255 Equals Lim_{k->inf.} A153869^k [From Gary W. Adamson (qntmpkt(AT)yahoo.com), 
               Jan 03 2009]
%C A000255 Contribution from Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 17 2009: 
               (Start)
%C A000255 Connection to A002469 (game of mousetrap with n cards): A002469(n) =
%C A000255 (n-2)*A000255(n-1) + A000166(n). (Cf. triangle A159610). (End)
%C A000255 Hankel transform is A059332. [From Paul Barry (pbarry(AT)wit.ie), Apr 
               22 2009]
%C A000255 Contribution from Johannes W. Meijer (meijgia(AT)hotmail.com), Oct 16 
               2009: (Start)
%C A000255 This sequence appears in the analysis of Euler's divergent series 1 - 
               1! + 2! - 3! + 4! ... by Lacroix, see Hardy. For information about 
               this and related divergent series see A163940.
%C A000255 (End)
%D A000255 Brualdi, Richard A.; Goldwasser, John L.; and Michael, T. S., Maximum 
               permanents of matrices of zeros and ones. J. Combin. Theory Ser. 
               A 47 (1988), 207-245.
%D A000255 R. A. Brualdi and H. J. Ryser: Combinatorial Matrix Theory, Camb. Univ. 
               Press, 1991, Section 7.2, p. 202.
%D A000255 CRC Handbook of Combinatorial Designs, 1996, p. 104.
%D A000255 F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied 
               Tables, Cambridge, 1966, p. 263.
%D A000255 G. Kreweras, The number of more or less "regular" permutations, Fib. 
               Quart., 18 (1980), 226-229.
%D A000255 A. N. Myers, Counting permutations by their rigid patterns, J. Combin. 
               Theory, A 99 (2002), 345-357.
%D A000255 J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 
               188.
%D A000255 D. P. Roselle, Permutations by number of rises and successions, Proc. 
               Amer. Math. Soc., 19 (1968), 8-16.
%D A000255 M. Rumney and E. J. F. Primrose, A sequence connected with the subfactorial 
               sequence, Note 3207, Math. Gaz. 52 (1968), 381-382.
%D A000255 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A000255 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A000255 Seok-Zun Song et al., Extremes of permanents of (0,1)-matrices, Lin. 
               Algebra and its Applic. 373 (2003), p. 197-210.
%D A000255 L. Euler, "Recherces sur une nouvelle espece des quarres magiques," Verhandelingen 
               uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen, 
               9 (1782), 85-239, on page 235 in section 152. This is paper E530 
               in Enestrom's index of Euler's works. The sequence appears on page 
               389 of Euler's Opera Omnia, series I, volume 7. [From D. E. Knuth]
%D A000255 Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, 
               Boca Raton, Florida, 2002, p. 179, Table 5.4.
%H A000255 T. D. Noe, <a href="b000255.txt">Table of n, a(n) for n=0..100</a>
%H A000255 F. Hivert, J.-C. Novelli and J.-Y. Thibon, <a href="http://arXiv.org/
               abs/math.CO/0605262">Commutative combinatorial Hopf algebras</a>
%H A000255 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/
               Publications/books.html">Analytic Combinatorics</a>, 2009; see page 
               373
%H A000255 G.H. Hardy, <a href="http://www.archive.org/texts/flipbook/flippy.php?id=divergentseries033523mbp">
               Divergent Series </a>, Oxford University Press, 1949. p. 29. [From 
               Johannes W. Meijer (meijgia(AT)hotmail.com), Oct 16 2009]
%F A000255 E.g.f.: exp(-x)/(1-x)^2.
%F A000255 a(n)=sum((-1)^k * (n-k+1) * n!/k!, k=0..n) - Len Smiley (smiley(AT)math.uaa.alaska.edu)
%F A000255 Inverse binomial transform of n!. - Robert A. Stump (bee_ess107(AT)yahoo.com), 
               Dec 09 2001
%F A000255 a(n) = floor((1/e)*n!*(n+2)+1/2) - Benoit Cloitre (benoit7848c(AT)orange.fr), 
               Jan 15 2004
%F A000255 Apparently lim n->inf ln(n) - ln(a(n))/n = 1 - Gerald McGarvey (Gerald.McGarvey(AT)comcast.net), 
               Jun 12 2004
%F A000255 a(n)=(n*(n+1)*an(n-1) +(-1)^n)/(n+1),n>=1, a(0)=1. See the Charalambides 
               reference.
%F A000255 a(n) = GAMMA(n+3,-1)*exp(-1)/(n+1) (incomplete Gamma function) [From 
               Mark van Hoeij (hoeij(AT)math.fsu.edu), Nov 11 2009]
%F A000255 a(n) = A000166(n) + A000166(n+1).
%F A000255 Cf. A000166.
%e A000255 a(3)=11: 1 3 2 4; 1 4 3 2; 2 1 4 3; 2 4 1 3; 3 2 1 4; 3 2 4 1; 4 1 3 
               2; 4 2 1 3; 4 3 2 1; 2 4 3 1; 3 1 4 2. The last two correspond to 
               (n-1)*a(n-2) since they contain a [j,n+1,j+1].
%t A000255 c = CoefficientList[Series[Exp[ -z]/(1 - z)^2, {z, 0, 30}], z] For[n 
               = 0, n < 31, n++; Print[c[[n]]*(n - 1)! ]]
%t A000255 Table[Subfactorial[n] + Subfactorial[n + 1], {n, 0, 20}] [From Zerinvary 
               Lajos (zerinvarylajos(AT)yahoo.com), Jul 09 2009]
%o A000255 (PARI) a(n)=if(n<0,0,contfracpnqn(matrix(2,n,i,j,j-(i==1)))[1,1])
%o A000255 (PARI) a(n)=if(n<0,0,n!*polcoeff(exp(-x+x*O(x^n))/(1-x)^2,n))
%o A000255 (Other) sage: from sage.combinat.sloane_functions import ExtremesOfPermanentsSequence2 
               sage: e = ExtremesOfPermanentsSequence2() sage: it = e.gen(1,1,1) 
               sage: [it.next() for i in range(20)] #5 rows.# [From Zerinvary Lajos 
               (zerinvarylajos(AT)yahoo.com), May 15 2009]
%Y A000255 Row sums of triangle in A046740. A diagonal of triangle in A068106.
%Y A000255 Cf. A000153, A000261, A001909, A001910, A090010, A055790, A090012-A090016.
%Y A000255 A052655 gives occurrence count for non-singular (0, 1)-matrices with 
               maximal permanent, A089475 number of different values of permanent, 
               A089480 occurrence counts for permanents all non-singular (0, 1)-matrices, 
               A087982, A087983.
%Y A000255 A diagonal in triangle A010027.
%Y A000255 A153869 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Jan 03 2009]
%Y A000255 A159610, A002469 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Apr 17 
               2009]
%Y A000255 Sequence in context: A039302 A074512 A005502 this_sequence A121580 A081367 
               A156171
%Y A000255 Adjacent sequences: A000252 A000253 A000254 this_sequence A000256 A000257 
               A000258
%K A000255 nonn,easy,nice,new
%O A000255 0,3
%A A000255 N. J. A. Sloane (njas(AT)research.att.com).