A097971 Number of alternating runs in all permutations of [n] (the permutation 732569148 has four alternating runs: 732, 2569, 91 and 148).

2, 10, 56, 360, 2640, 21840, 201600, 2056320, 22982400, 279417600, 3672345600, 51891840000, 784604620800, 12640852224000, 216202162176000, 3912561709056000, 74694359900160000, 1500289571708928000, 31627726106296320000, 698242876346695680000, 16110677098145710080000

Offset

2,1

Comments

a(n) is also equal to the sum over all permutations p in S(n) of the number of elements in the set {(i, j): 0 < i < j < n+1 and |i - j| = |p(i) - p(j)|}.

References

M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, FL, 2004, pp. 24-30.

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973, Vol. 3, pp. 46 and 587-8.

Links

Table of n, a(n) for n=2..22.

Formula

a(n) = n!*(2*n-1)/3.

E.g.f.: x^2*(3-x)/(3*(1-x)^2).

a(n) = 2*A006157(n).

Example

a(3) = 10 because the permutations 123, 132, 312, 213, 231, 321 have the following alternating runs: 123, 13, 32, 31, 12, 21, 13, 23, 31 and 321.

Maple

seq(n!*(2*n-1)/3, n=2..20);

Mathematica

a[n_]:=n!*(2*n-1)/3; Array[a, 20, 2] (* Stefano Spezia, Sep 11 2025 *)

Crossrefs

Cf. A006157.

Sequence in context: A165817 A243644 A000172 * A390147 A191277 A290443

Adjacent sequences: A097968 A097969 A097970 * A097972 A097973 A097974

Keyword

nonn

Author

Emeric Deutsch and Ira M. Gessel, Sep 07 2004

Extensions

a(22) from Stefano Spezia, Sep 11 2025

Status

approved