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