cp's OEIS Frontend

A343419 Number of distinct sets { p(i) - p(j) : 1 <= i <= j <= n } where p ranges over all permutations of [n].

%I A343419 #37 Apr 22 2021 03:42:43
%S A343419 1,1,2,4,8,12,24,34,62,88,148,208,360,466,784,1082,1718,2278,3744,
%T A343419 4902,7914,10486,16334,21728
%N A343419 Number of distinct sets { p(i) - p(j) : 1 <= i <= j <= n } where p ranges over all permutations of [n].
%C A343419 a(n) is even for n > 1.
%F A343419 a(n) < 2 + 74*3^(n-6).
%F A343419 a(n) <= 2*a(n-1) (conjectured).
%e A343419 a(1) = 1: [[0]].
%e A343419 a(2) = 2: [[-1, 0], [0, 1]].
%e A343419 a(3) = 4: [[-2, -1, 0], [-2, -1, 0, 1], [-1, 0, 1, 2], [0, 1, 2]].
%e A343419 a(4) = 8: [[-3, -2, -1, 0], [-3, -2, -1, 0, 1], [-3, -2, -1, 0, 1, 2], [-2, -1, 0, 1, 2, 3], [-2, -1, 0, 1, 3], [-3, -1, 0, 1, 2], [-1, 0, 1, 2, 3], [0, 1, 2, 3]].
%e A343419 a(5) = 12: [[-4, -3, -2, -1, 0], [-4, -3, -2, -1, 0, 1], [-4, -3, -2, -1, 0, 1, 2], [-4, -3, -2, -1, 0, 1, 2, 3], [-4, -3, -2, -1, 0, 1, 3], [-3, -2, -1, 0, 1, 2, 3, 4], [-3, -2, -1, 0, 1, 2, 4], [-4, -2, -1, 0, 1, 2, 3], [-2, -1, 0, 1, 2, 3, 4], [-3, -1, 0, 1, 2, 3, 4], [-1, 0, 1, 2, 3, 4], [0, 1, 2, 3, 4]].
%p A343419 b:= proc(s) option remember; `if`(s={}, {{}}, {seq(map(x->
%p A343419       {seq(j-i, j=s)} union x, b(s minus {i}))[], i=s)})
%p A343419     end:
%p A343419 a:= n-> nops(b({$1..n})):
%p A343419 seq(a(n), n=0..12);  # _Alois P. Heinz_, Apr 15 2021
%o A343419 (Python)
%o A343419 def perm(pmt,begin,end):
%o A343419     global k
%o A343419     global a_n
%o A343419     if begin>=end:
%o A343419         a=[]
%o A343419         for x in range(1,len(pmt)):
%o A343419             for y in range(0,x+1):
%o A343419                 a.append(pmt[y]-pmt[x])
%o A343419         new_list=[]
%o A343419         for j in a:
%o A343419             if j not in new_list:
%o A343419                 new_list.append(j)
%o A343419         new_list.sort()
%o A343419         k.append(new_list)
%o A343419         m=[]
%o A343419         for ss in k:
%o A343419             if ss not in m:
%o A343419                 m.append(ss)
%o A343419         k=m
%o A343419         a_n=len(m)
%o A343419     else:
%o A343419         i=begin
%o A343419         for num in range(begin,end):
%o A343419             pmt[num],pmt[i]=pmt[i],pmt[num]
%o A343419             perm(pmt,begin+1,end)
%o A343419             pmt[num],pmt[i]=pmt[i],pmt[num]
%o A343419 N=1
%o A343419 while True:
%o A343419     k=[]
%o A343419     a_n=0
%o A343419     pmt=[]
%o A343419     for p in range(0,N):
%o A343419         pmt.append(p+1)
%o A343419     perm(pmt,0,len(pmt))
%o A343419     print("a(",N,")=",a_n)
%o A343419     N=N+1
%o A343419 (Python)
%o A343419 from itertools import permutations
%o A343419 def a(n): return len(set(tuple(sorted(set(p[i] - p[j] for i in range(n) for j in range(i, n)))) for p in permutations(range(1, n+1))))
%o A343419 print([a(n) for n in range(10)]) # _Michael S. Branicky_, Apr 17 2021
%Y A343419 Cf. A000142.
%K A343419 nonn,more
%O A343419 0,3
%A A343419 _Baohua Tian_, Apr 15 2021
%E A343419 a(11)-a(16) from _Alois P. Heinz_, Apr 15 2021
%E A343419 a(17)-a(23) from _Bert Dobbelaere_, Apr 21 2021