

A000255


a(n) = n * a(n1) + (n1) * a(n2), a(0) = 1, a(1) = 1.
(Formerly M2905 N1166)


91



1, 1, 3, 11, 53, 309, 2119, 16687, 148329, 1468457, 16019531, 190899411, 2467007773, 34361893981, 513137616783, 8178130767479, 138547156531409, 2486151753313617, 47106033220679059, 939765362752547227, 19690321886243846661, 432292066866171724421
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

a(n) counts permutations of [1,...,n+1] having no substring [k,k+1].  Len Smiley, Oct 13 2001
Also a(n2) = !n/(n  1) where !n is the subfactorial of n, A000166(n).  Lekraj Beedassy, Jun 18 2002
Also, for n > 0, determinant of the tridiagonal n X n matrix M such that M(i,i)=i and for i=1..n1, M(i,i+1)=1, M(i+1,i)=i.  Mario Catalani (mario.catalani(AT)unito.it), Feb 04 2003
Also, for n > 0, maximal permanent of a nonsingular n X n (0,1)matrix, which is achieved by the matrix with just n1 0's, all on main diagonal. [For proof, see next entry.]  W. Edwin Clark, Oct 28 2003
Proof from Richard Brualdi and W. Edwin Clark, Nov 15 2003: Let n >= 4. Take an n X n (0,1)matrix A which is nonsingular. It has t >= n1, 0's, otherwise there will be two rows of all 1's. Let B be the matrix obtained from A by replacing t(n1) of A's 0's with 1's. Let D be the matrix with all 1's except for 0's in the first n1 positions on the diagonal. This matrix is easily seen to be nonsingular. 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.
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 SeokZun Song et al., Extremes of permanents of (0,1)matrices, pp. 201202.  Jaap Spies, Dec 12 2003
Number of fixedpointfree 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, 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, Aug 28 2006]
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
A000255(n+1) is the sequence of numerators of the selfconvergents to 1/(e2); see A096654.  Clark Kimberling, Jul 01 2004
Euler's interpretation was "fixedpointfree permutations beginning with 2" and he listed the terms up to 148329 (although he was blind at the time).  Don Knuth, Jan 25 2007
Equals lim_{k>inf} A153869^k.  Gary W. Adamson, Jan 03 2009
Connection to A002469 (game of mousetrap with n cards): A002469(n) = (n2)*A000255(n1) + A000166(n). (Cf. triangle A159610).  Gary W. Adamson, Apr 17 2009
Hankel transform is A059332.  Paul Barry, Apr 22 2009
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.  Johannes W. Meijer, Oct 16 2009
a(n), n >= 1, enumerates also 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 one open cord allowed to have any number of beads. Each beadless necklace as well as the beadless cord contributes a factor 1 in the counting, e.g., a(0):=1*1=1. There are k! possibilities for the cord with k>=0 beads, which means that the two ends of the cord should be considered as fixed, in short: a fixed cord. This produces for a(n) the exponential (aka binomial) convolution of the sequences {n!=A000142(n)} and the subfactorials {A000166(n)}.
See the formula below. Alternatively, the e.g.f. for this problem is seen to be (exp(x)/(1x))*(1/(1x)), namely the product of the e.g.f.s for the subfactorials (from the unordered necklace problem, without necklaces with exactly one bead) and the factorials (from the fixed cord problem). Therefore the recurrence with inputs holds also. a(0):=1. 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
a(n) = (n1)a(n1) + (n2)a(n2) gives the same sequence offset by a 1.  Jon Perry, Sep 20 2012
Also, number of reduced 2 X (n+2) Latin rectangles.  _A. H. M. Smeets_, Nov 03 2013
Second column of Euler's difference table (second diagonal in example of A068106).  Enrique Navarrete, Dec 13 2016
If we partition the permutations of [n+2] in A000166 according to their starting digit, we will get (n+1) equinumerous classes each of size a(n) (the class starting with the digit 1 is empty since no derangement starts with 1). Hence, A000166(n+2)=(n+1)*a(n), so a(n) is the size of each nonempty class of permutations of [n+2] in A000166. For example, for n=3 we have 44=4*11 (see link).  Enrique Navarrete, Jan 11 2017
For n >= 1, the number of circular permutations (in cycle notation) on [n+2] that avoid substrings (j,j+2), 1 <= j <= n. For example, for n=2, the 3 circular permutations in S4 that avoid substrings {13,24} are (1234),(1423),(1432). Note that each of these circular permutations represent 4 permutations in oneline notation (see link 2017).  Enrique Navarrete, Feb 15 2017
The sequence a(n) taken modulo a positive integer k is periodic with exact period dividing k when k is even and dividing 2*k when k is odd. This follows from the congruence a(n+k) = (1)^k*a(n) (mod k) holding for all n and k, which in turn is easily proved by induction making use of the given recurrences.  Peter Bala, Nov 21 2017


REFERENCES

R. A. Brualdi and H. J. Ryser: Combinatorial Matrix Theory, Camb. Univ. Press, 1991, Section 7.2, p. 202.
Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002, p. 179, Table 5.4 and p. 177 (5.1).
CRC Handbook of Combinatorial Designs, 1996, p. 104.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, pp. 263264. See Table 7.5.1, row 0; also Table 7.6.1, row 0.
L. Euler, "Recherches sur une nouvelle espece des quarres magiques," Verhandelingen uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen, 9 (1782), 85239, 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]
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).


LINKS

T. D. Noe, Table of n, a(n) for n=0..100
M. H. Albert, M. D. Atkinson, and Robert Brignall, Permutation Classes of Polynomial Growth, arXiv:math/0603315 [math.CO], 20062007; Annals of Combinatorics 11 (2007) 249264.
Roland Bacher, Counting Packings of Generic Subsets in Finite Groups, Electr. J. Combinatorics, 19 (2012), #P7.  From N. J. A. Sloane, Feb 06 2013
B. Balof, H. Jenne, Tilings, Continued Fractions, Derangements, Scramblings, and e, Journal of Integer Sequences, 17 (2014), #14.2.7.
Robert Brignall, Vít Jelínek, Jan Kynčl, David Marchant, Zeros of the Möbius function of permutations, arXiv:1810.05449 [math.CO], 2018.
Richard A. Brualdi, John L. Goldwasser, T. S. Michael, Maximum permanents of matrices of zeros and ones, J. Combin. Theory Ser. A 47 (1988), 207245.
Giulio Cerbai, Luca Ferrari, Permutation patterns in genome rearrangement problems, arXiv:1808.02653 [math.CO], 2018. See p. 126.
Uriel Feige, Tighter bounds for online bipartite matching, 2018.
Philip Feinsilver and John McSorley, Zeons, Permanents, the Johnson Scheme, and Generalized Derangements, International Journal of Combinatorics, Volume 2011, Article ID 539030, 29 pages; doi:10.1155/2011/539030.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 373
G. H. Hardy, Divergent Series, Oxford University Press, 1949. p. 29.
F. Hivert, J.C. Novelli and J.Y. Thibon, Commutative combinatorial Hopf algebras, arXiv:math/0605262 [math.CO], 2006.
H. K. Jenne, Proofs you can count on, Honors Thesis, Math. Dept., Whitman College, 2013.
G. Kreweras, The number of more or less "regular" permutations, Fib. Quart., 18 (1980), 226229.
Ajay Kumar, Chanchal Kumar, Monomial ideals induced by permutations avoiding patterns, 2018.
T. Mansour and M. Shattuck, Counting permutations by the number of successors within cycles, Discr. Math., 339 (2016), 13681376.
A. N. Myers, Counting permutations by their rigid patterns, J. Combin. Theory, A 99 (2002), 345357.
Enrique Navarrete, Forbidden Patterns and the Alternating Derangement Sequence, arXiv:1610.01987 [math.CO], 2016.
Enrique Navarrete, Forbidden Substrings in Circular KSuccessions, arXiv:1702.02637 [math.CO], 2017.
Luis Manuel Rivera, Integer sequences and kcommuting permutations, arXiv preprint arXiv:1406.3081 [math.CO], 2014.
D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 19 (1968), 816.
D. P. Roselle, Permutations by number of rises and successions, Proc. Amer. Math. Soc., 19 (1968), 816. [Annotated scanned copy]
M. Rumney and E. J. F. Primrose, A sequence connected with the subfactorial sequence, Note 3207, Math. Gaz. 52 (1968), 381382.
M. Rumney and E. J. F. Primrose, A sequence connected with the subfactorial sequence, Note 3207, Math. Gaz. 52 (1968), 381382. [Annotated scanned copy]
Isaac Sofair, Derangement revisited, Math. Gazette, 97 (No. 540, 2013), 435440.
SeokZun Song et al., Extremes of permanents of (0,1)matrices, Lin. Algebra and its Applic. 373 (2003), pp. 197210.


FORMULA

E.g.f.: exp(x)/(1x)^2.
a(n) = Sum_{k=0..n} (1)^k * (nk+1) * n!/k!.  Len Smiley
Inverse binomial transform of (n+1)!.  Robert A. Stump (bee_ess107(AT)yahoo.com), Dec 09 2001
a(n) = floor((1/e)*n!*(n+2)+1/2).  Benoit Cloitre, Jan 15 2004
a(n) = {(n+2)n!/e}, where {x} denotes the nearest integer. Proposed by Simon Plouffe, March 1993.
Apparently lim_{n>inf} log(n)  log(a(n))/n = 1.  Gerald McGarvey, Jun 12 2004
a(n) = (n*(n+2)*a(n1) + (1)^n)/(n+1) for n >= 1, a(0)=1. See the Charalambides reference.
a(n) = GAMMA(n+3,1)*exp(1)/(n+1) (incomplete Gamma function).  Mark van Hoeij, Nov 11 2009
a(n) = A000166(n) + A000166(n+1).
If we take b(n) = (1)^(n+1)*a(n) for n > 0, then for n > 1 the arithmetic mean of the first n terms is b(n1).  Franklin T. AdamsWatters, May 20 2010
a(n) = hypergeometric([2,n],[],1)*(1)^n = KummerU(2,3+n,1)*(1)^n. See the AbramowitzStegun handbook (for the reference see e.g. A103921) p. 504, 13.1.10, and for the recurrence p. 507, 13.4.16.  Wolfdieter Lang, May 20 2010
From Wolfdieter Lang, Jun 02 2010: (Start)
a(n) = n!*(1 + Sum_{k=0..n2} sf(nk)/(nk)!) with the subfactorials sf(n):= A000166(n) (this follows from the exponential convolution).
a(n) = sf(n+1) + sf(n), n >= 0, with sf(n):=A000166(n). (Observation in an email from Gary Detlefs.) (End)
a(n) = 1/(n+1)*floor(((n+1)!+1)/e).  Gary Detlefs, Jul 11 2010
a(n) = (Subfactorial(n+2))/(n+1).  Alexander R. Povolotsky, Jan 26 2011
G.f.: 1/(1x2x^2/(13x6x^2/(15x12x^2/(17x20x^2/(1.../(1(2n+1)x(n+1)(n+2)x^2/(1... (continued fraction).  Paul Barry, Apr 11 2011
G.f.: hypergeom([1,2],[],x/(x+1))/(x+1).  Mark van Hoeij, Nov 07 2011
From Sergei N. Gladkovskii, Sep 24 2012  Feb 05 2014: (Start)
Continued fractions:
E.g.f. 1/E(0) where E(k) = 1  2*x/(1 + x/(2  x  2/(1 + x*(k+1)/E(k+1)))).
G.f.: S(x)/x  1/x = Q(0)/x  1/x where S(x) = Sum_{k>=0} k!*(x/(1+x))^k, Q(k) = 1 + (2*k + 1)*x/(1 + x  2*x*(1+x)*(k+1)/(2*x*(k+1) + (1+x)/Q(k+1))).
G.f.: 1/Q(0) where Q(k) = 1 + x  x*(k+2)/(1  x*(k+1)/Q(k+1)).
G.f.: 1/x/Q(0) where Q(k) = 1/x  (2*k+1)  (k+2)*(k+1)/Q(k+1).
G.f.: (1+x)/(x*Q(0))  1/x where Q(k) = 1  2*k*x  x^2*(k + 1)^2/Q(k+1).
G.f.: 2/x/G(0)  1/x where G(k) = 1 + 1/(1  x*(2*k+2)/(x*(2*k+1)  1 + x*(2*k+2)/ G(k+1))).
G.f.: ((Sum_{k>=0} k!*(x/(1+x))^k)  1)/x = Q(0)/(2*x)  1/x where Q(k) = 1 + 1/(1  x*(k+1)/(x*(k+1) + (1+x)/Q(k+1))).
G.f.: W(0) where W(k) = 1  x*(k+1)/(x*(k+1)  1/(1  x*(k+2)/(x*(k+1)  1/W(k+1)))).
G.f.: G(0)/(1x) where G(k) = 1  x^2*(k+1)*(k+2)/(x^2*(k+1)*(k+2)  (1x*(1+2*k))*(1x*(3+2*k))/G(k+1)). (End)
From Peter Bala, Sep 20 2013: (Start)
The sequence b(n) := n!*(n + 2) satisfies the defining recurrence for a(n) but with the starting values b(0) = 2 and b(1) = 3. This leads to the finite continued fraction expansion a(n) = n!*(n+2)*( 1/(2 + 1/(1 + 1/(2 + 2/(3 + ... + (n1)/n)))) ), valid for n >= 2.
Also a(n) = n!*(n+2)*( Sum_{k = 0..n} (1)^k/(k+2)! ). Letting n > infinity gives the infinite continued fraction expansion 1/e = 1/(2 + 1/(1 + 1/(2 + 2/(3 + ... + (n1)/(n + ...)))) ) due to Euler. (End)
a(n) = round((n+2)!/e)/(n+1).  Thomas Ordowski, Nov 07 2013
0 = a(n)*(+a(n+1) + 2*a(n+2)  a(n+3)) + a(n+1)*(+2*a(n+2)  a(n+3)) + a(n+2)*(+a(n+2)) if n >= 0.  Michael Somos, May 06 2014
a(n3) = (n2)*A000757(n2) + (2*n5)*A000757(n3) + (n3)*A000757(n4), n >= 3.  Luis Manuel Rivera Martínez, Mar 14 2015
a(n) = A000240(n) + A000240(n+1), n >= 1. Let D(n) = A000240(n) be the permutations of [n] having no substring in {12,23,...,(n1)n,n1}. Let d(n) = a(n1) be the permutations of [n] having no substring in {12,23,...,(n1)n}. Let d_n1 = A000240(n1) be the permutations of [n] that have the substring n1 but no substring in {12,23,...,(n1)n}. Then the link "Forbidden Patterns" shows the bijection d_n1 ~ D(n1) and since dn = d_n1 U D(n), we get dn = D(n1) U D(n). Taking cardinalities we get the result for n1, i.e., a(n1) = A000240(n1) + A000240(n). For example, for n=4 in this last equation, we get a(4) = 11 = 3+8.  Enrique Navarrete, Jan 16 2017
a(n) = (n+1)!*hypergeom([n], [n1], 1).  Peter Luschny, Nov 02 2018


EXAMPLE

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 (n1)*a(n2) since they contain a [j,n+1,j+1].
Cordnecklaces problem. For n=4 one considers the following weak two part compositions of 4: (4,0), (2,2), (1,3), and (0,4), where (3,1) does not appear because there are no necklaces with 1 bead. These compositions contribute respectively 4!*1, (binomial(4,2)*2)*sf(2), (binomial(4,1)*1)*sf(3), and 1*sf(4) with the subfactorials sf(n):=A000166(n) (see the necklace comment there). This adds up as 24 + 6*2 + 4*2 + 9 = 53 = a(4).  Wolfdieter Lang, Jun 02 2010
G.f. = 1 + x + 3*x^2 + 11*x^3 + 53*x^4 + 309*x^5 + 2119*x^6 + 16687*x^7 + ...


MAPLE

a := n > hypergeom([2, n], [], 1)*(1)^n:
seq(simplify(a(n)), n=0..19); # Peter Luschny, Sep 20 2014


MATHEMATICA

c = CoefficientList[Series[Exp[ z]/(1  z)^2, {z, 0, 30}], z] For[n = 0, n < 31, n++; Print[c[[n]]*(n  1)! ]]
Table[Subfactorial[n] + Subfactorial[n + 1], {n, 0, 20}] (* Zerinvary Lajos, Jul 09 2009 *)
RecurrenceTable[{a[n]==n a[n1]+(n1)a[n2], a[0]==1, a[1]==1}, a[n], {n, 20}] (* Harvey P. Dale, May 10 2011 *)
a[ n_] := If[ n < 0, 0, Round[ n! (n + 2) / E]] (* Michael Somos, Jun 01 2013 *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ Exp[ x] / (1  x)^2, {x, 0, n}] (* Michael Somos, Jun 01 2013 *)
a[ n_] := If[ n < 0, 0, (1)^n HypergeometricPFQ[ { n, 2}, {}, 1]] (* Michael Somos, Jun 01 2013 *)


PROG

(PARI) {a(n) = if( n<0, 0, contfracpnqn( matrix( 2, n, i, j, j  (i==1)))[1, 1])};
(PARI) {a(n) = if( n<0, 0, n! * polcoeff( exp( x + x * O(x^n)) / (1  x)^2, n))};
(Sage) from sage.combinat.sloane_functions import ExtremesOfPermanentsSequence2
e = ExtremesOfPermanentsSequence2()
it = e.gen(1, 1, 1)
[it.next() for i in range(20)]
## [Zerinvary Lajos, May 15 2009]
(Haskell)
a000255 n = a000255_list !! n
a000255_list = 1 : 1 : zipWith (+) zs (tail zs) where
zs = zipWith (*) [1..] a000255_list
 Reinhard Zumkeller, Dec 05 2011
(MAGMA) I:=[1, 3]; [1] cat [n le 2 select I[n] else n*Self(n1)+(n1)*Self(n2): n in [1..30]]; // Vincenzo Librandi, Aug 09 2018


CROSSREFS

Row sums of triangle in A046740. A diagonal of triangle in A068106.
Cf. A000153, A000166, A000261, A001909, A001910, A055790.
Cf. A090010, A090012, A090013, A090014, A090015, A090016.
A052655 gives occurrence count for nonsingular (0, 1)matrices with maximal permanent, A089475 number of different values of permanent, A089480 occurrence counts for permanents all nonsingular (0, 1)matrices, A087982, A087983.
A diagonal in triangle A010027.
Cf. A153869, A159610, A002469.
a(n) = A086764(n+1,1).
Sequence in context: A074512 A005502 A305710 * A318912 A121580 A321732
Adjacent sequences: A000252 A000253 A000254 * A000256 A000257 A000258


KEYWORD

nonn,easy,nice


AUTHOR

N. J. A. Sloane


STATUS

approved



