cp's OEIS Frontend

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

%I A365043 #19 Apr 28 2025 15:10:58
%S A365043 0,0,1,3,7,12,21,32,49,70,99,135,185,245,323,418,541,688,873,1094,
%T A365043 1368,1693,2092,2564,3138,3810,4620,5565,6696,8012,9569,11381,13518,
%U A365043 15980,18872,22194,26075,30535,35711,41627,48473,56290,65283,75533,87298,100631,115911,133219
%N A365043 Number of subsets of {1..n} whose greatest element can be written as a (strictly) positive linear combination of the others.
%C A365043 Sets of this type may be called "positive combination-full".
%C A365043 Also subsets of {1..n} such that some element can be written as a (strictly) positive linear combination of the others.
%H A365043 Bert Dobbelaere, <a href="/A365043/b365043.txt">Table of n, a(n) for n = 0..100</a>
%H A365043 Steven R. Finch, <a href="/A066062/a066062.pdf">Monoids of natural numbers</a>, March 17, 2009.
%F A365043 a(n) = 2^n - A365044(n).
%e A365043 The subset S = {3,4,9} has 9 = 3*3 + 0*4, but this is not strictly positive, so S is not counted under a(9).
%e A365043 The subset S = {3,4,10} has 10 = 2*3 + 1*4, so S is counted under a(10).
%e A365043 The a(0) = 0 through a(5) = 12 subsets:
%e A365043   .  .  {1,2}  {1,2}    {1,2}    {1,2}
%e A365043                {1,3}    {1,3}    {1,3}
%e A365043                {1,2,3}  {1,4}    {1,4}
%e A365043                         {2,4}    {1,5}
%e A365043                         {1,2,3}  {2,4}
%e A365043                         {1,2,4}  {1,2,3}
%e A365043                         {1,3,4}  {1,2,4}
%e A365043                                  {1,2,5}
%e A365043                                  {1,3,4}
%e A365043                                  {1,3,5}
%e A365043                                  {1,4,5}
%e A365043                                  {2,3,5}
%t A365043 combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
%t A365043 Table[Length[Select[Rest[Subsets[Range[n]]],combp[Last[#],Union[Most[#]]]!={}&]],{n,0,10}]
%o A365043 (Python)
%o A365043 from itertools import combinations
%o A365043 from sympy.utilities.iterables import partitions
%o A365043 def A365043(n):
%o A365043     mlist = tuple({tuple(sorted(p.keys())) for p in partitions(m,k=m-1)} for m in range(1,n+1))
%o A365043     return sum(1 for k in range(2,n+1) for w in combinations(range(1,n+1),k) if w[:-1] in mlist[w[-1]-1]) # _Chai Wah Wu_, Nov 20 2023
%Y A365043 The binary complement is A007865, first differences A288728.
%Y A365043 The binary version is A093971, first differences A365070.
%Y A365043 The nonnegative complement is A326083, first differences A124506.
%Y A365043 The nonnegative version is A364914, first differences A365046.
%Y A365043 First differences are A365042.
%Y A365043 The complement is counted by A365044, first differences A365045.
%Y A365043 Without re-usable parts we have A364534, first differences A365069.
%Y A365043 A085489 and A364755 count subsets with no sum of two distinct elements.
%Y A365043 A088809 and A364756 count subsets with some sum of two distinct elements.
%Y A365043 A364350 counts combination-free strict partitions, complement A364839.
%Y A365043 A364913 counts combination-full partitions.
%Y A365043 Cf. A151897, A237113, A237668, A308546, A324736, A326020, A326080, A364272.
%K A365043 nonn
%O A365043 0,4
%A A365043 _Gus Wiseman_, Aug 25 2023
%E A365043 a(15)-a(35) from _Chai Wah Wu_, Nov 20 2023
%E A365043 More terms from _Bert Dobbelaere_, Apr 28 2025