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

Links

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

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

Cf. A333710.

Sequence in context: A365544 A360791 A304341 * A333710 A295909 A347701

Adjacent sequences: A263984 A263985 A263986 * A263988 A263989 A263990

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