A120928 Number of "ups" and "downs" in the permutations of [n] if either a previous counted "up" ("down") or a "void" precedes an "up" ("down") which then will be counted also.

2, 8, 44, 280, 2040, 16800, 154560, 1572480, 17539200, 212889600, 2794176000, 39437798400, 595718323200, 9589612032000, 163895187456000, 2964061900800000, 56554301067264000, 1135354270482432000, 23923536413736960000, 527939735774330880000

Offset

2,1

Comments

An "up" ("down") is a neighboring pair of elements e_i, e_j of [n] with e_i < e_j (e_i > e_j). A "void" is a missing preceding pair, i.e., the start of [n]. We discuss two examples for [n=4]. In the permutation [3, 1, 2, 4] "void" precedes the pair 3,1 and consequently a "down" is counted. No "up" which has been counted precedes the "ups" 1,2 and 2,4 so they are not counted. In [3, 4, 1, 2] the "up" 3,4 is counted and so is the next "up" 1,2 but the down 4,1 has no preceding "down" registered and is therefore not counted.

Links

Alois P. Heinz, Table of n, a(n) for n = 2..400

Formula

E.g.f.: -(6+6*x^2-4*x^3+x^4)/(-3+12*x-18*x^2+12*x^3-3*x^4). - Thomas Wieder, May 02 2009

a(2) = 2, a(n) = n! * (3*n - 1) / 6 for n > 2. - Jon E. Schoenfield, Apr 18 2010

Example

[1, 2, 3, 4], "ups"=3, "downs"=0;
[1, 2, 4, 3], "ups"=2, "downs"=0;
[1, 3, 2, 4], "ups"=2, "downs"=0;
[1, 3, 4, 2], "ups"=2, "downs"=0;
[1, 4, 2, 3], "ups"=2, "downs"=0;
[1, 4, 3, 2], "ups"=1, "downs"=0;
[2, 1, 3, 4], "ups"=0, "downs"=1;
[2, 1, 4, 3], "ups"=0, "downs"=2;
[2, 3, 1, 4], "ups"=2, "downs"=0;
[2, 3, 4, 1], "ups"=2, "downs"=0;
[2, 4, 1, 3], "ups"=2, "downs"=0;
[2, 4, 3, 1], "ups"=1, "downs"=0;
[3, 1, 2, 4], "ups"=0, "downs"=1;
[3, 1, 4, 2], "ups"=0, "downs"=2;
[3, 2, 1, 4], "ups"=0, "downs"=2;
[3, 2, 4, 1], "ups"=0, "downs"=2;
[3, 4, 1, 2], "ups"=2, "downs"=0;
[3, 4, 2, 1], "ups"=1, "downs"=0;
[4, 1, 2, 3], "ups"=0, "downs"=1;
[4, 1, 3, 2], "ups"=0, "downs"=2;
[4, 2, 1, 3], "ups"=0, "downs"=2;
[4, 2, 3, 1], "ups"=0, "downs"=2;
[4, 3, 1, 2], "ups"=0, "downs"=2;
[4, 3, 2, 1], "ups"=0, "downs"=3.

Maple

a:= n-> ceil(n!*(3*n-1)/6):
seq(a(n), n=2..30); # Alois P. Heinz, Apr 21 2012

Prog

(C++) #include <stdio.h> #include <iostream> #include <vector> #include <algorithm> using namespace std ; class UDown { public: vector<int> perm; UDown(int n) { for(int c=0; c < n ; c++) perm.push_back(c) ; } int ups ( const vector<int> & perm) const { int sgn = perm[1]-perm[0] ; int u = 0 ; for(int i=1 ; i < perm.size() ; i++) if ( (perm[i]-perm[i-1])*sgn > 0) u++ ; return u ; } long long int cnt() { long long int a = ups(perm) ; while ( next_permutation(perm.begin(), perm.end()) ) a += ups(perm) ; return a ; } } ; int main(int argc, char *argv[]) { for(int n=2; ; n++) { UDown m(n) ; cout << n << " " << m.cnt() << endl ; } return 0 ; } // R. J. Mathar, Aug 25 2008

Crossrefs

Cf. A028399, A052582, A062119, A097971.

Sequence in context: A141147 A346626 A201374 * A286425 A260879 A179489

Adjacent sequences: A120925 A120926 A120927 * A120929 A120930 A120931

Keyword

nonn,easy

Author

Thomas Wieder, Jul 16 2006

Extensions

4 more terms from R. J. Mathar, Aug 25 2008

More terms from Alois P. Heinz, Apr 21 2012

Status

approved