login
A343419
Number of distinct sets { p(i) - p(j) : 1 <= i <= j <= n } where p ranges over all permutations of [n].
0
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,3
COMMENTS
a(n) is even for n > 1.
FORMULA
a(n) < 2 + 74*3^(n-6).
a(n) <= 2*a(n-1) (conjectured).
EXAMPLE
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]].
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
PROG
(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
CROSSREFS
Cf. A000142.
Sequence in context: A293601 A171647 A089821 * A353796 A377141 A294067
KEYWORD
nonn,more
AUTHOR
Baohua Tian, Apr 15 2021
EXTENSIONS
a(11)-a(16) from Alois P. Heinz, Apr 15 2021
a(17)-a(23) from Bert Dobbelaere, Apr 21 2021
STATUS
approved