A263987 Number of ways of ordering integers 1 to n such that each number is either a factor of or larger than its predecessor.

1, 1, 2, 4, 14, 28, 164, 328, 2240, 9970, 63410, 126820, 1810514, 3621028, 31417838, 294911038, 3344414606, 6688829212, 121919523980, 243839047960, 5307482547686, 56885719183654, 468469574780468, 936939149560936, 33136077712470338, 249693200433310492

Offset: 0

Author

Matthew Scroggs, Oct 31 2015

Keywords

• nonn

Examples

			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).
		

Crossrefs

Cf. A333710.

Programs

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 *)

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

Python

from itertools import permutations
def a(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(0, 10):
    print(a(i), end=", ")

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

Formula

a(p) = 2 * a(p-1) for prime p. - Alois P. Heinz, Feb 25 2024

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