cp's OEIS Frontend

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

%I A131529 #19 Mar 08 2015 18:24:16
%S A131529 1,2,4,12,44,176,788,3936,23264,152112,1104876,8725320,74715908,
%T A131529 687915040,6782261964,71294227456,796138700016,9409401651840,
%U A131529 117378774461812
%N A131529 Number of permutations of {1,2,...n} for which differences of adjacent numbers are all distinct.
%H A131529 Joerg Arndt, <a href="/A131529/a131529.txt">lexicopraphically first permutation</a> with distinct differences for n=1..30 (permutations of {0,1,2,..,n-1}, i.e., zero based).
%o A131529 (C++)  /* gcc -O2 -Wall -lstdc++ A131529.cc */
%o A131529 #include <iostream>
%o A131529 #include <vector>
%o A131529 #include <set>
%o A131529 #include <algorithm>
%o A131529 using namespace std;
%o A131529 inline int k(const vector<int> & s)
%o A131529 {
%o A131529     const int n = s.size();
%o A131529     set<int> diffs;
%o A131529     for (int i=1; i<n; i++)
%o A131529     {
%o A131529         const int thisdiff = s[i]-s[i-1];
%o A131529         if ( diffs.find(thisdiff) != diffs.end() ) return 0;
%o A131529         diffs.insert(thisdiff);
%o A131529     }
%o A131529     return 1;
%o A131529 }
%o A131529 int main(int argc, char *argv[])
%o A131529 {
%o A131529     for(int n=1; ; n++)
%o A131529     {
%o A131529         vector<int> s;
%o A131529         for(int i=1; i<=n; i++) s.push_back(i);
%o A131529         unsigned long long resul=0;
%o A131529         do { resul += k(s); }
%o A131529         while ( next_permutation(s.begin(), s.end()) );
%o A131529         cout << n << " " << resul << endl;
%o A131529     }
%o A131529     return 0;
%o A131529 }
%o A131529 /* _R. J. Mathar_, Oct 25 2007 */
%Y A131529 Cf. A040018, A091217, A006967.
%K A131529 more,nonn
%O A131529 1,2
%A A131529 _Vladeta Jovovic_, Aug 26 2007
%E A131529 2 more terms from _R. J. Mathar_, Oct 25 2007
%E A131529 7 more terms from _R. H. Hardin_, Nov 26 2009