OFFSET
0,3
FORMULA
a(p) = 2 * a(p-1) for prime p. - Alois P. Heinz, Feb 25 2024
EXAMPLE
For n=4, the allowable sequences are: (1,2,3,4), (1,3,4,2), (1,4,2,3), (2,1,3,4), (2,3,1,4), (2,3,4,1), (2,4,1,3), (3,1,2,4), (3,1,4,2), (3,4,1,2), (3,4,2,1), (4,1,2,3), (4,2,1,3), (4,2,3,1).
MAPLE
b:= proc(i, s) option remember; `if`(s={}, 1, add(
`if`(j>i or irem(i, j)=0, b(j, s minus {j}), 0), j=s))
end:
a:= n-> add(b(i, {$1..n} minus {i}), i=signum(n)..n):
seq(a(n), n=0..15); # Alois P. Heinz, Oct 31 2015
MATHEMATICA
b[i_, s_] := b[i, s] = If[s == {}, 1, Sum[If[j > i || Mod[i, j] == 0, b[j, s ~Complement~ {j}], 0], {j, s}]];
a[n_] := Sum[b[i, Range[n] ~Complement~ {i}], {i, 1, n}];
Array[a, 12] (* Jean-François Alcover, Nov 28 2020, after Alois P. Heinz *)
PROG
(Python)#
def p(n):
....count = 0
....for i in permutations(range(1, n+1), r=n):
........for j in range(len(i)-1):
............if i[j]%i[j+1]!=0 and i[j]>i[j+1]:
................break
........else:
............count+=1
....return count
for i in range(1, 100):
....print(p(i))
(Python)
from functools import cache
@cache
def b(i, s): return 1 if s == tuple() else sum(b(j, tuple(sorted(set(s)-{j}))) if j>i or i%j==0 else 0 for j in s)
def a(n): return 1 if n==0 else sum(b(i, tuple(sorted(set(range(1, n+1))-{i}))) for i in range(1, n+1))
print([a(n) for n in range(15)]) # Michael S. Branicky, Feb 25 2024 after Alois P. Heinz
(PARI) a(n) = {nb = 0; for (k=0, n!-1, perm = numtoperm(n, k); ok = 1; for (j=2, n, if ((perm[j] % perm[j-1]) && (perm[j] > perm[j-1]), ok=0; break); ); if (ok, nb++); ); nb; } \\ Michel Marcus, Nov 02 2015
CROSSREFS
KEYWORD
nonn
AUTHOR
Matthew Scroggs, Oct 31 2015
EXTENSIONS
a(11)-a(21) from Alois P. Heinz, Oct 31 2015
a(22)-a(24) from Michael S. Branicky, Feb 25 2024
a(0)=1 prepended and a(25) added by Alois P. Heinz, Feb 25 2024
STATUS
approved