cp's OEIS Frontend

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

%I A263987 #47 Nov 12 2024 16:14:04
%S A263987 1,1,2,4,14,28,164,328,2240,9970,63410,126820,1810514,3621028,
%T A263987 31417838,294911038,3344414606,6688829212,121919523980,243839047960,
%U A263987 5307482547686,56885719183654,468469574780468,936939149560936,33136077712470338,249693200433310492
%N A263987 Number of ways of ordering integers 1 to n such that each number is either a factor of or larger than its predecessor.
%F A263987 a(p) = 2 * a(p-1) for prime p. - _Alois P. Heinz_, Feb 25 2024
%e A263987 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).
%p A263987 b:= proc(i, s) option remember; `if`(s={}, 1, add(
%p A263987       `if`(j>i or irem(i, j)=0, b(j, s minus {j}), 0), j=s))
%p A263987     end:
%p A263987 a:= n-> add(b(i, {$1..n} minus {i}), i=signum(n)..n):
%p A263987 seq(a(n), n=0..15);  # _Alois P. Heinz_, Oct 31 2015
%t A263987 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}]];
%t A263987 a[n_] := Sum[b[i, Range[n] ~Complement~ {i}], {i, 1, n}];
%t A263987 Array[a, 12] (* _Jean-François Alcover_, Nov 28 2020, after _Alois P. Heinz_ *)
%o A263987 (Python)
%o A263987 from itertools import permutations
%o A263987 def a(n):
%o A263987     count = 0
%o A263987     for i in permutations(range(1, n+1), r=n):
%o A263987         for j in range(len(i)-1):
%o A263987             if i[j]%i[j+1]!=0 and i[j]>i[j+1]:
%o A263987                 break
%o A263987         else:
%o A263987             count+=1
%o A263987     return count
%o A263987 for i in range(0, 10):
%o A263987     print(a(i), end=", ")
%o A263987 (Python)
%o A263987 from functools import cache
%o A263987 @cache
%o A263987 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)
%o A263987 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))
%o A263987 print([a(n) for n in range(15)]) # _Michael S. Branicky_, Feb 25 2024 after _Alois P. Heinz_
%o A263987 (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
%Y A263987 Cf. A333710.
%K A263987 nonn
%O A263987 0,3
%A A263987 _Matthew Scroggs_, Oct 31 2015
%E A263987 a(11)-a(21) from _Alois P. Heinz_, Oct 31 2015
%E A263987 a(22)-a(24) from _Michael S. Branicky_, Feb 25 2024
%E A263987 a(0)=1 prepended and a(25) added by _Alois P. Heinz_, Feb 25 2024