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