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