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,3

Comments

a(n) is even for n > 1.

Links

Table of n, a(n) for n=0..23.

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

Adjacent sequences: A343416 A343417 A343418 * A343420 A343421 A343422

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