A131529 Number of permutations of {1,2,...n} for which differences of adjacent numbers are all distinct.

1, 2, 4, 12, 44, 176, 788, 3936, 23264, 152112, 1104876, 8725320, 74715908, 687915040, 6782261964, 71294227456, 796138700016, 9409401651840, 117378774461812

Offset

1,2

Links

Table of n, a(n) for n=1..19.

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

Cf. A040018, A091217, A006967.

Sequence in context: A039301 A346505 A180205 * A238111 A165901 A074449

Adjacent sequences: A131526 A131527 A131528 * A131530 A131531 A131532

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