login
Number of subsets of {1..n} such that it is not possible to choose a different prime factor of each element.
25

%I #9 Feb 27 2024 14:25:39

%S 0,1,2,4,10,20,44,88,204,440,908,1816,3776,7552,15364,31240,63744,

%T 127488,257592,515184,1036336,2079312,4166408,8332816,16709632,

%U 33470464,66978208,134067488,268236928,536473856,1073233840,2146467680,4293851680,8588355424,17177430640

%N Number of subsets of {1..n} such that it is not possible to choose a different prime factor of each element.

%F a(n) = 2^n - A370582(n).

%e The a(0) = 0 through a(5) = 20 subsets:

%e . {1} {1} {1} {1} {1}

%e {1,2} {1,2} {1,2} {1,2}

%e {1,3} {1,3} {1,3}

%e {1,2,3} {1,4} {1,4}

%e {2,4} {1,5}

%e {1,2,3} {2,4}

%e {1,2,4} {1,2,3}

%e {1,3,4} {1,2,4}

%e {2,3,4} {1,2,5}

%e {1,2,3,4} {1,3,4}

%e {1,3,5}

%e {1,4,5}

%e {2,3,4}

%e {2,4,5}

%e {1,2,3,4}

%e {1,2,3,5}

%e {1,2,4,5}

%e {1,3,4,5}

%e {2,3,4,5}

%e {1,2,3,4,5}

%t Table[Length[Select[Subsets[Range[n]], Length[Select[Tuples[If[#==1,{},First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]==0&]],{n,0,10}]

%Y Multisets of this type are ranked by A355529, complement A368100.

%Y For divisors instead of factors we have A355740, complement A368110.

%Y The complement for set-systems is A367902, ranks A367906, unlabeled A368095.

%Y The version for set-systems is A367903, ranks A367907, unlabeled A368094.

%Y For non-isomorphic multiset partitions we have A368097, complement A368098.

%Y The version for factorizations is A368413, complement A368414.

%Y The complement is counted by A370582.

%Y For a unique choice we have A370584.

%Y Partial sums of A370587, complement A370586.

%Y The minimal case is A370591.

%Y The version for partitions is A370593, complement A370592.

%Y For binary indices instead of factors we have A370637, complement A370636.

%Y A006530 gives greatest prime factor, least A020639.

%Y A027746 lists prime factors, A112798 indices, length A001222.

%Y A355741 counts choices of a prime factor of each prime index.

%Y Cf. A000040, A000720, A001055, A001414, A003963, A005117, A045778, A355739, A355745, A367867, A367905, A368187.

%K nonn

%O 0,3

%A _Gus Wiseman_, Feb 26 2024

%E a(19)-a(34) from _Alois P. Heinz_, Feb 27 2024