A120928 - OEIS

This site is supported by donations to The OEIS Foundation.

A120928

Number of "ups" and "downs" in the permutations of [n] if either a previous counted "up" ("down") or a "void" proceeds an "up" ("down") which then will be counted also. 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 discus two examples for [n=4]. In the permutation [3, 1, 2, 4] "void" proceeds the pair 3,1 and consequently a "down" is counted. No "up" which has been counted proceeds 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.

2, 8, 44, 280, 2040, 16800, 154560, 1572480, 17539200, 212889600, 2794176000 (list; graph; refs; listen; history; internal format)

	OFFSET	`2,1`
	FORMULA	`E.g.f.: -(6+6x^2-4x^3+x^4)/(-3+12x-18x^2+12x^3-3x^4). [From Thomas Wieder (thomas.wieder(AT)t-online.de), May 02 2009]` `a(2) = 2, a(n) = n! * (3*n - 1) / 6 for n > 2. - Jon 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.`
	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 ; } [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Aug 25 2008]
	CROSSREFS	`Cf. A028399, A052582, A062119, A097971.` `Sequence in context: A014508 A141147 A201374 * A179489 A111537 A051045` `Adjacent sequences: A120925 A120926 A120927 * A120929 A120930 A120931`
	KEYWORD	`nonn`
	AUTHOR	`Thomas Wieder (thomas.wieder(AT)t-online.de), Jul 16 2006`
	EXTENSIONS	`4 more terms from R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Aug 25 2008`

Content is available under The OEIS End-User License Agreement .

Last modified February 16 02:30 EST 2012. Contains 205860 sequences.