A000274 Number of permutations of length n with 2 consecutive ascending pairs.

0, 0, 1, 3, 18, 110, 795, 6489, 59332, 600732, 6674805, 80765135, 1057289046, 14890154058, 224497707343, 3607998868005, 61576514013960, 1112225784377144, 21197714949305577, 425131949816628507, 8950146311929021210, 197350726178034917670, 4548464355722328578691

Offset: 1

Author

N. J. A. Sloane, Simon Plouffe

Keywords

• easy
• nonn

Comments

From Emeric Deutsch, May 25 2009: (Start)

a(n) = number of excedances in all derangements of [n-1]. Example: a(5)=18 because the derangements of {1,2,3,4} are 4*123, 3*14*2, 3*4*12, 4*3*12, 2*14*3, 2*4*13, 2*3*4*1, 3*4*21, 4*3*21 with the 18 excedances marked. An excedance of a permutation p is a position i such that p(i)>i.

a(n) = Sum(k*A046739(n,k), k>=1).

(End)

Appears to be the inverse binomial transform of A001286 (filling the two leading zeros in there), then shifting one place to the right. - R. J. Mathar, Apr 04 2012

References

• F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.
• J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 210 (divided by 2).
• 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

• Alois P. Heinz, Table of n, a(n) for n = 1..150
• R. Mantaci and F. Rakotondrajao, Exceedingly deranging!, Advances in Appl. Math., 30 (2003), 177-188. [_Emeric Deutsch_, May 25 2009]

Crossrefs

Cf. A010027, A000255, A000166, A000313, A001260, A001261.

A diagonal in triangle A010027.

Cf. A046739. [Emeric Deutsch, May 25 2009]

Cf. A145887, A145886.

Programs

Maple

a:= n->sum((n-1)!*sum((-1)^k/k!/2, j=1..n-1), k=0..n-1): seq(a(n), n=1..23); # Zerinvary Lajos, May 17 2007

Mathematica

Table[Subfactorial[n]*n/2, {n, 2, 20}] (* Zerinvary Lajos, Jul 09 2009 *)

Formula

a(n) = (1 + n) a(n - 1) + (3 + n) a(n - 2) + (3 - n) a(n - 3) + (2 - n) a(n - 4).

E.g.f.: x^2/2*exp(-x)/(1-x)^2. - Vladeta Jovovic, Jan 03 2003

a(n) = (n-1)^2/(n-2)*a(n-1)-(-1)^n*(n-1)/2, n>2, a(2)=0. - Vladeta Jovovic, Aug 31 2003

a(n) = (1/2){[n!/e] - [(n-1)!/e]} (conjectured).

a(n) = (n-1)*GAMMA(n,-1)*exp(-1)/2 where GAMMA = incomplete Gamma function. [Mark van Hoeij, Nov 11 2009]

a(n) = A145887(n-1) + A145886(n-1). - Anton Zakharov, Aug 28 2016

Extensions

Name clarified and offset changed by N. J. A. Sloane, Apr 12 2014