cp's OEIS Frontend

A365044 Number of subsets of {1..n} whose greatest element cannot be written as a (strictly) positive linear combination of the others.

%I A365044 #24 Dec 13 2024 09:37:45
%S A365044 1,2,3,5,9,20,43,96,207,442,925,1913,3911,7947,16061,32350,64995,
%T A365044 130384,261271,523194,1047208,2095459,4192212,8386044,16774078,
%U A365044 33550622,67104244,134212163,268428760,536862900,1073732255,2147472267,4294953778,8589918612,17179850312
%N A365044 Number of subsets of {1..n} whose greatest element cannot be written as a (strictly) positive linear combination of the others.
%C A365044 Sets of this type may be called "positive combination-free".
%C A365044 Also subsets of {1..n} such that no element can be written as a (strictly) positive linear combination of the others.
%H A365044 Steven R. Finch, <a href="/A066062/a066062.pdf">Monoids of natural numbers</a>, March 17, 2009.
%F A365044 a(n) = 2^n - A365043(n).
%e A365044 The subset S = {3,5,6,8} has 6 = 2*3 + 0*5 + 0*8 and 8 = 1*3 + 1*5 + 0*6 but neither of these is strictly positive, so S is counted under a(8).
%e A365044 The a(0) = 1 through a(5) = 20 subsets:
%e A365044   {}  {}   {}   {}     {}         {}
%e A365044       {1}  {1}  {1}    {1}        {1}
%e A365044            {2}  {2}    {2}        {2}
%e A365044                 {3}    {3}        {3}
%e A365044                 {2,3}  {4}        {4}
%e A365044                        {2,3}      {5}
%e A365044                        {3,4}      {2,3}
%e A365044                        {2,3,4}    {2,5}
%e A365044                        {1,2,3,4}  {3,4}
%e A365044                                   {3,5}
%e A365044                                   {4,5}
%e A365044                                   {2,3,4}
%e A365044                                   {2,4,5}
%e A365044                                   {3,4,5}
%e A365044                                   {1,2,3,4}
%e A365044                                   {1,2,3,5}
%e A365044                                   {1,2,4,5}
%e A365044                                   {1,3,4,5}
%e A365044                                   {2,3,4,5}
%e A365044                                   {1,2,3,4,5}
%t A365044 combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
%t A365044 Table[Length[Select[Subsets[Range[n]],And@@Table[combp[Last[#],Union[Most[#]]]=={},{k,Length[#]}]&]],{n,0,10}]
%o A365044 (Python)
%o A365044 from itertools import combinations
%o A365044 from sympy.utilities.iterables import partitions
%o A365044 def A365044(n):
%o A365044     mlist = tuple({tuple(sorted(p.keys())) for p in partitions(m,k=m-1)} for m in range(1,n+1))
%o A365044     return n+1+sum(1 for k in range(2,n+1) for w in combinations(range(1,n+1),k) if w[:-1] not in mlist[w[-1]-1]) # _Chai Wah Wu_, Nov 20 2023
%Y A365044 The binary version is A007865, first differences A288728.
%Y A365044 The binary complement is A093971, first differences A365070.
%Y A365044 Without re-usable parts we have A151897, first differences A365071.
%Y A365044 The nonnegative version is A326083, first differences A124506.
%Y A365044 A subclass is A341507.
%Y A365044 The nonnegative complement is A364914, first differences A365046.
%Y A365044 The complement is counted by A365043, first differences A365042.
%Y A365044 First differences are A365045.
%Y A365044 A085489 and A364755 count subsets w/o the sum of two distinct elements.
%Y A365044 A088809 and A364756 count subsets with the sum of two distinct elements.
%Y A365044 A364350 counts combination-free strict partitions, complement A364839.
%Y A365044 A364913 counts combination-full partitions.
%Y A365044 Cf. A006951, A237113, A237668, A308546, A324736, A326020, A326080, A364272, A364349, A364534, A365069.
%K A365044 nonn
%O A365044 0,2
%A A365044 _Gus Wiseman_, Aug 26 2023
%E A365044 a(15)-a(34) from _Chai Wah Wu_, Nov 20 2023