login
A131529
Number of permutations of {1,2,...n} for which differences of adjacent numbers are all distinct.
4
1, 2, 4, 12, 44, 176, 788, 3936, 23264, 152112, 1104876, 8725320, 74715908, 687915040, 6782261964, 71294227456, 796138700016, 9409401651840, 117378774461812
OFFSET
1,2
LINKS
Joerg Arndt, lexicopraphically first permutation with distinct differences for n=1..30 (permutations of {0,1,2,..,n-1}, i.e., zero based).
PROG
(C++) /* gcc -O2 -Wall -lstdc++ A131529.cc */
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
inline int k(const vector<int> & s)
{
const int n = s.size();
set<int> diffs;
for (int i=1; i<n; i++)
{
const int thisdiff = s[i]-s[i-1];
if ( diffs.find(thisdiff) != diffs.end() ) return 0;
diffs.insert(thisdiff);
}
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;
}
/* R. J. Mathar, Oct 25 2007 */
CROSSREFS
KEYWORD
more,nonn
AUTHOR
Vladeta Jovovic, Aug 26 2007
EXTENSIONS
2 more terms from R. J. Mathar, Oct 25 2007
7 more terms from R. H. Hardin, Nov 26 2009
STATUS
approved