|
%I #11 Jul 26 2012 10:23:16
%S 2,10,56,360,2640,21840,201600,2056320,22982400,279417600,3672345600,
%T 51891840000,784604620800,12640852224000,216202162176000,
%U 3912561709056000,74694359900160000,1500289571708928000,31627726106296320000,698242876346695680000
%N Number of alternating runs in all permutations of [n] (the permutation 732569148 has four alternating runs: 732, 2569, 91 and 148).
%C 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)|}.
%D M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, FL, 2004, pp. 24-30.
%D D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973, Vol. 3, pp. 46 and 587-8.
%F a(n) = n!(2n-1)/3. E.g.f.: x^2*(3-x)/[3(1-x)^2]. a(n) = 2*A006157(n).
%e 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.
%p seq(n!*(2*n-1)/3, n=2..20);
%Y Cf. A006157.
%K nonn
%O 2,1
%A _Emeric Deutsch_ and _Ira M. Gessel_, Sep 07 2004
|
