|
|
A186371
|
|
Number of up-down runs in all permutations of {1,2,...,n}.
|
|
1
|
|
|
0, 1, 3, 13, 68, 420, 3000, 24360, 221760, 2237760, 24796800, 299376000, 3911846400, 55005350400, 828193766400, 13294689408000, 226663557120000, 4090405423104000, 77895546753024000, 1561112121913344000, 32844177110384640000, 723788347432550400000
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
The up-down runs of a permutation p are the alternating runs of the permutation p endowed with a 0 in the front. For example, 75814632 has 6 up-down runs: 07, 75, 58, 81, 146, and 632.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k=1..n} k*A186370(n,k).
a(n) = n!*(4n+1)/6 for n>=2.
E.g.f.: g(z) = z(6-3z+z^2)/[6(1-z)^2].
D-finite with recurrence 4*a(n) +(-4*n-7)*a(n-1) +3*(n-1)*a(n-2)=0. - R. J. Mathar, Jul 22 2022
|
|
EXAMPLE
|
a(3)=13 because the permutations 123, 132, 213, 231, 312, and 321 have a total of 1 + 2 + 3 + 2 + 3 + 2 = 13 up-down runs.
|
|
MAPLE
|
0, 1, seq((1/6)*factorial(n)*(4*n+1), n = 2 .. 20);
|
|
MATHEMATICA
|
|
|
PROG
|
(Magma) [0, 1] cat [Factorial(n)*(4*n+1)/6: n in [2..30]]; // Vincenzo Librandi, Sep 11 2015
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|