login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A097971 Number of alternating runs in all permutations of [n] (the permutation 732569148 has four alternating runs: 732, 2569, 91 and 148). 2
2, 10, 56, 360, 2640, 21840, 201600, 2056320, 22982400, 279417600, 3672345600, 51891840000, 784604620800, 12640852224000, 216202162176000, 3912561709056000, 74694359900160000, 1500289571708928000, 31627726106296320000, 698242876346695680000 (list; graph; refs; listen; history; text; internal format)
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 A265954

Adjacent sequences:  A097968 A097969 A097970 * A097972 A097973 A097974

KEYWORD

nonn

AUTHOR

Emeric Deutsch and Ira M. Gessel, Sep 07 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 24 10:10 EDT 2019. Contains 324323 sequences. (Running on oeis4.)