A343419 Number of distinct sets { p(i) - p(j) : 1 <= i <= j <= n } where p ranges over all permutations of [n].
1, 1, 2, 4, 8, 12, 24, 34, 62, 88, 148, 208, 360, 466, 784, 1082, 1718, 2278, 3744, 4902, 7914, 10486, 16334, 21728
Offset: 0
Examples
a(1) = 1: [[0]]. a(2) = 2: [[-1, 0], [0, 1]]. a(3) = 4: [[-2, -1, 0], [-2, -1, 0, 1], [-1, 0, 1, 2], [0, 1, 2]]. 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]]. 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]].
Crossrefs
Cf. A000142.
Programs
-
Maple
b:= proc(s) option remember; `if`(s={}, {{}}, {seq(map(x-> {seq(j-i, j=s)} union x, b(s minus {i}))[], i=s)}) end: a:= n-> nops(b({$1..n})): seq(a(n), n=0..12); # Alois P. Heinz, Apr 15 2021 -
Python
def perm(pmt,begin,end): global k global a_n if begin>=end: a=[] for x in range(1,len(pmt)): for y in range(0,x+1): a.append(pmt[y]-pmt[x]) new_list=[] for j in a: if j not in new_list: new_list.append(j) new_list.sort() k.append(new_list) m=[] for ss in k: if ss not in m: m.append(ss) k=m a_n=len(m) else: i=begin for num in range(begin,end): pmt[num],pmt[i]=pmt[i],pmt[num] perm(pmt,begin+1,end) pmt[num],pmt[i]=pmt[i],pmt[num] N=1 while True: k=[] a_n=0 pmt=[] for p in range(0,N): pmt.append(p+1) perm(pmt,0,len(pmt)) print("a(",N,")=",a_n) N=N+1 -
Python
from itertools import permutations 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)))) print([a(n) for n in range(10)]) # Michael S. Branicky, Apr 17 2021
Formula
a(n) < 2 + 74*3^(n-6).
a(n) <= 2*a(n-1) (conjectured).
Extensions
a(11)-a(16) from Alois P. Heinz, Apr 15 2021
a(17)-a(23) from Bert Dobbelaere, Apr 21 2021
Comments