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

%I #37 Apr 22 2021 03:42:43

%S 1,1,2,4,8,12,24,34,62,88,148,208,360,466,784,1082,1718,2278,3744,

%T 4902,7914,10486,16334,21728

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

%C a(n) is even for n > 1.

%F a(n) < 2 + 74*3^(n-6).

%F a(n) <= 2*a(n-1) (conjectured).

%e a(1) = 1: [[0]].

%e a(2) = 2: [[-1, 0], [0, 1]].

%e a(3) = 4: [[-2, -1, 0], [-2, -1, 0, 1], [-1, 0, 1, 2], [0, 1, 2]].

%e 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 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 b:= proc(s) option remember; `if`(s={}, {{}}, {seq(map(x->

%p {seq(j-i, j=s)} union x, b(s minus {i}))[], i=s)})

%p end:

%p a:= n-> nops(b({$1..n})):

%p seq(a(n), n=0..12); # _Alois P. Heinz_, Apr 15 2021

%o (Python)

%o def perm(pmt,begin,end):

%o global k

%o global a_n

%o if begin>=end:

%o a=[]

%o for x in range(1,len(pmt)):

%o for y in range(0,x+1):

%o a.append(pmt[y]-pmt[x])

%o new_list=[]

%o for j in a:

%o if j not in new_list:

%o new_list.append(j)

%o new_list.sort()

%o k.append(new_list)

%o m=[]

%o for ss in k:

%o if ss not in m:

%o m.append(ss)

%o k=m

%o a_n=len(m)

%o else:

%o i=begin

%o for num in range(begin,end):

%o pmt[num],pmt[i]=pmt[i],pmt[num]

%o perm(pmt,begin+1,end)

%o pmt[num],pmt[i]=pmt[i],pmt[num]

%o N=1

%o while True:

%o k=[]

%o a_n=0

%o pmt=[]

%o for p in range(0,N):

%o pmt.append(p+1)

%o perm(pmt,0,len(pmt))

%o print("a(",N,")=",a_n)

%o N=N+1

%o (Python)

%o from itertools import permutations

%o 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 print([a(n) for n in range(10)]) # _Michael S. Branicky_, Apr 17 2021

%Y Cf. A000142.

%K nonn,more

%O 0,3

%A _Baohua Tian_, Apr 15 2021

%E a(11)-a(16) from _Alois P. Heinz_, Apr 15 2021

%E a(17)-a(23) from _Bert Dobbelaere_, Apr 21 2021