A120928 - OEIS

%I #23 Jul 22 2017 08:41:54

%S 2,8,44,280,2040,16800,154560,1572480,17539200,212889600,2794176000,

%T 39437798400,595718323200,9589612032000,163895187456000,

%U 2964061900800000,56554301067264000,1135354270482432000,23923536413736960000,527939735774330880000

%N 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.

%C 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.

%H Alois P. Heinz, <a href="/A120928/b120928.txt">Table of n, a(n) for n = 2..400</a>

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

%F a(2) = 2, a(n) = n! * (3*n - 1) / 6 for n > 2. - _Jon E. Schoenfield_, Apr 18 2010

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

%p a:= n-> ceil(n!*(3*n-1)/6):

%p seq(a(n), n=2..30); # _Alois P. Heinz_, Apr 21 2012

%o (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

%Y Cf. A028399, A052582, A062119, A097971.

%K nonn,easy

%O 2,1

%A _Thomas Wieder_, Jul 16 2006

%E 4 more terms from _R. J. Mathar_, Aug 25 2008

%E More terms from _Alois P. Heinz_, Apr 21 2012