login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Number of subsets of {1..n} containing n such that it is not possible to choose a different prime factor of each element (non-choosable).
13

%I #5 Feb 29 2024 08:52:05

%S 0,1,1,2,6,10,24,44,116,236,468,908,1960,3776,7812,15876,32504,63744,

%T 130104

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

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

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

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

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

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

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

%e {1,2,3,4} {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]],MemberQ[#,n] && Length[Select[Tuples[If[#==1,{},First/@FactorInteger[#]]&/@#], UnsameQ@@#&]]==0&]],{n,0,10}]

%Y First differences of A370583, complement A370582, cf. A370584.

%Y The complement is counted by A370586.

%Y For a unique choice we have A370588.

%Y For binary indices instead of factors we have A370639, complement A370589.

%Y A006530 gives greatest prime factor, least A020639.

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

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

%Y A367902 counts choosable set-systems, ranks A367906, unlabeled A368095.

%Y A367903 counts non-choosable set-systems, ranks A367907, unlabeled A368094.

%Y A368098 counts choosable unlabeled multiset partitions, complement A368097.

%Y A368100 ranks choosable multisets, complement A355529.

%Y A368414 counts choosable factorizations, complement A368413.

%Y A370585 counts maximal choosable sets.

%Y A370592 counts choosable partitions, complement A370593.

%Y Cf. A000040, A000720, A005117, A045778, A133686, A355739, A355744, A355745, A367905, A370636.

%K nonn,more

%O 0,4

%A _Gus Wiseman_, Feb 28 2024