cp's OEIS Frontend

A333517 Number of set partitions of {1, 2, ..., n} such that, for any two numbers in the same part, one divides the other.

%I A333517 #50 Jul 31 2024 11:27:01
%S A333517 1,1,2,3,7,9,25,30,78,138,342,386,1307,1448,3406,6818,18907,20478,
%T A333517 65901,70781,213704,397874,885118,939377,3624495,5034048,11032794,
%U A333517 20966732,59398560,62307000,225641196,235937708,682530590,1183122260,2540294162,4026533578,15943721982,16555409210,35301649136,59929463166
%N A333517 Number of set partitions of {1, 2, ..., n} such that, for any two numbers in the same part, one divides the other.
%C A333517 a(n) <= A000110(n) for all n since a(n) counts set partitions.
%C A333517 a(n) >= n for all n, since the singletons form a suitable partition and separately moving 1 into each set creates n - 1 new suitable partitions.
%H A333517 Alois P. Heinz, <a href="/A333517/b333517.txt">Table of n, a(n) for n = 0..48</a> (terms n = 0..45 from Giovanni Resta)
%H A333517 Luc Rousseau, <a href="/A333517/a333517.pl.txt">A Prolog program</a>.
%e A333517 For n = 3, the suitable partitions are {{1}, {2}, {3}}, {{1, 3}, {2}}, and {{1, 2}, {3}}, so a(3) = 3.
%p A333517 g:= proc(n, s) `if`(n<2, 1+nops(s),
%p A333517       b(n, sort(map(i-> `if`(isprime(i), 1, i), s))))
%p A333517     end:
%p A333517 b:= proc(n, s) option remember; add(`if`(irem(s[j], n)>0, 0,
%p A333517       g(n-1, subsop(j=n, s))), j=1..nops(s))+g(n-1, [s[], n])
%p A333517     end:
%p A333517 a:= n-> g(n, []):
%p A333517 seq(a(n), n=0..28);  # _Alois P. Heinz_, Mar 26 2020
%t A333517 g[n_, s_] := If[n<2, 1+Length[s], b[n, Sort[If[PrimeQ[#], 1, #]& /@ s]]];
%t A333517 b[n_, s_] := b[n, s] = Sum[If[Mod[s[[j]], n] > 0, 0, g[n-1, ReplacePart[s, j -> n]]], {j, 1, Length[s]}] + g[n-1, Append[s, n]];
%t A333517 a[n_] := g[n, {}];
%t A333517 a /@ Range[0, 28] (* _Jean-François Alcover_, Nov 14 2020, after _Alois P. Heinz_ *)
%o A333517 (SWI-Prolog) % see link - _Luc Rousseau_, Jul 31 2024
%Y A333517 Cf. A000110, A320430.
%K A333517 nonn
%O A333517 0,3
%A A333517 _Robert Dougherty-Bliss_, Mar 26 2020
%E A333517 a(25)-a(39) from _Alois P. Heinz_, Mar 26 2020