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

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..21.

Formula

a(n) = n!(2n-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);

Crossrefs

Cf. A006157.

Sequence in context: A165817 A243644 A000172 * A191277 A290443 A336961

Adjacent sequences: A097968 A097969 A097970 * A097972 A097973 A097974

Keyword

nonn

Author

Emeric Deutsch and Ira M. Gessel, Sep 07 2004

Status

approved