A365044 - OEIS

%I #21 Dec 20 2023 14:56:23

%S 1,2,3,5,9,20,43,96,207,442,925,1913,3911,7947,16061,32350,64995,

%T 130384,261271,523194,1047208,2095459,4192212,8386044,16774078,

%U 33550622,67104244,134212163,268428760,536862900,1073732255,2147472267,4294953778,8589918612,17179850312

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

%C Sets of this type may be called "positive combination-free".

%C Also subsets of {1..n} such that no element can be written as a (strictly) positive linear combination of the others.

%H S. R. Finch, <a href="/A066062/a066062.pdf">Monoids of natural numbers</a>, March 17, 2009.

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

%e 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 The a(0) = 1 through a(5) = 20 subsets:

%e   {}  {}   {}   {}     {}         {}

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

%e            {2}  {2}    {2}        {2}

%e                 {3}    {3}        {3}

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

%e                        {2,3}      {5}

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

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

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

%e                                   {3,5}

%e                                   {4,5}

%e                                   {2,3,4}

%e                                   {2,4,5}

%e                                   {3,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 combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];

%t Table[Length[Select[Subsets[Range[n]],And@@Table[combp[Last[#],Union[Most[#]]]=={},{k,Length[#]}]&]],{n,0,10}]

%o (Python)

%o from itertools import combinations

%o from sympy.utilities.iterables import partitions

%o def A365044(n):

%o     mlist = tuple({tuple(sorted(p.keys())) for p in partitions(m,k=m-1)} for m in range(1,n+1))

%o     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 The binary version is A007865, first differences A288728.

%Y The binary complement is A093971, first differences A365070.

%Y Without re-usable parts we have A151897, first differences A365071.

%Y The nonnegative version is A326083, first differences A124506.

%Y A subclass is A341507.

%Y The nonnegative complement is A364914, first differences A365046.

%Y The complement is counted by A365043, first differences A365042.

%Y First differences are A365045.

%Y A085489 and A364755 count subsets w/o the sum of two distinct elements.

%Y A088809 and A364756 count subsets with the sum of two distinct elements.

%Y A364350 counts combination-free strict partitions, complement A364839.

%Y A364913 counts combination-full partitions.

%Y Cf. A006951, A237113, A237668, A308546, A324736, A326020, A326080, A364272, A364349, A364534, A365069.

%K nonn

%O 0,2

%A _Gus Wiseman_, Aug 26 2023

%E a(15)-a(34) from _Chai Wah Wu_, Nov 20 2023