Date: Mon, 10 Dec 2007 19:12:25 +0100 From: Richard Mathar <mathar(AT)strw.leidenuniv.nl> The terms 1,2,4,10,26,80,272,1076,4848,24832,142340,902440 were found with a brute force C++ program which scans all permutations: #include <iostream> #include <vector> #include <algorithm> using namespace std; // return inverse permutation of s vector<int> invsPerm( const vector<int> & s) { vector<int> inv(s.size() ) ; for(int i=0; i < s.size() ; i++) inv[ s[i]-1 ] = i+1 ; return inv ; } inline int k(const vector<int> & s) { const int n = s.size() ; const vector<int> sInv = invsPerm(s) ; for(int i=1; i<n; i++) { // no hit if signs differ, ie, if product is less than zero if ( (s[i]-s[i-1])*(sInv[i]-sInv[i-1]) < 0 ) return 0 ; } return 1 ; } int main(int argc, char *argv[]) { for(int n=1 ;;n++) { vector<int> s; for(int i=1;i<=n;i++) s.push_back(i) ; unsigned long long resul=0 ; do { resul += k(s) ; } while( next_permutation(s.begin(),s.end()) ) ; cout << n << " " << resul << endl ; } return 0 ; }