cp's OEIS Frontend

A364914 Number of subsets of {1..n} such that some element can be written as a nonnegative linear combination of the others.

%I A364914 #23 Dec 13 2024 09:39:31
%S A364914 0,0,1,3,9,20,48,101,219,454,944,1917,3925,7915,16004,32188,64751,
%T A364914 129822,260489,521672,1045060,2091808,4187047,8377255,16762285,
%U A364914 33531228,67077485,134170217,268371678,536772231,1073611321,2147282291,4294697258,8589527163,17179321094
%N A364914 Number of subsets of {1..n} such that some element can be written as a nonnegative linear combination of the others.
%C A364914 A variation of non-binary combination-full sets where parts can be re-used. The complement is counted by A326083. The binary version is A093971. For non-re-usable parts we have A364534. First differences are A365046.
%H A364914 Steven R. Finch, <a href="/A066062/a066062.pdf">Monoids of natural numbers</a>, March 17, 2009.
%e A364914 The set {3,4,5,17} has 17 = 1*3 + 1*4 + 2*5, so is counted under a(17).
%e A364914 The a(0) = 0 through a(5) = 20 subsets:
%e A364914   .  .  {1,2}  {1,2}    {1,2}      {1,2}
%e A364914                {1,3}    {1,3}      {1,3}
%e A364914                {1,2,3}  {1,4}      {1,4}
%e A364914                         {2,4}      {1,5}
%e A364914                         {1,2,3}    {2,4}
%e A364914                         {1,2,4}    {1,2,3}
%e A364914                         {1,3,4}    {1,2,4}
%e A364914                         {2,3,4}    {1,2,5}
%e A364914                         {1,2,3,4}  {1,3,4}
%e A364914                                    {1,3,5}
%e A364914                                    {1,4,5}
%e A364914                                    {2,3,4}
%e A364914                                    {2,3,5}
%e A364914                                    {2,4,5}
%e A364914                                    {1,2,3,4}
%e A364914                                    {1,2,3,5}
%e A364914                                    {1,2,4,5}
%e A364914                                    {1,3,4,5}
%e A364914                                    {2,3,4,5}
%e A364914                                    {1,2,3,4,5}
%t A364914 combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
%t A364914 Table[Length[Select[Subsets[Range[n]],Or@@Table[combs[#[[k]],Delete[#,k]]!={},{k,Length[#]}]&]],{n,0,10}]
%o A364914 (Python)
%o A364914 from itertools import combinations
%o A364914 from sympy.utilities.iterables import partitions
%o A364914 def A364914(n):
%o A364914     c, mlist = 0, []
%o A364914     for m in range(1,n+1):
%o A364914         t = set()
%o A364914         for p in partitions(m,k=m-1):
%o A364914             t.add(tuple(sorted(p.keys())))
%o A364914         mlist.append([set(d) for d in t])
%o A364914     for k in range(2,n+1):
%o A364914         for w in combinations(range(1,n+1),k):
%o A364914             ws = set(w)
%o A364914             for d in w:
%o A364914                 for s in mlist[d-1]:
%o A364914                     if s <= ws:
%o A364914                         c += 1
%o A364914                         break
%o A364914                 else:
%o A364914                     continue
%o A364914                 break
%o A364914     return c # _Chai Wah Wu_, Nov 17 2023
%Y A364914 The binary complement is A007865.
%Y A364914 The binary version without re-usable parts is A088809.
%Y A364914 The binary version is A093971.
%Y A364914 The complement without re-usable parts is A151897.
%Y A364914 The complement is counted by A326083.
%Y A364914 The version without re-usable parts is A364534.
%Y A364914 The version for strict partitions is A364839, complement A364350.
%Y A364914 The version for partitions is A364913.
%Y A364914 The version for positive combinations is A365043, complement A365044.
%Y A364914 First differences are A365046.
%Y A364914 Cf. A011782, A085489, A103580, A116861, A124506, A237113, A237668, A308546, A324736, A326020, A326080, A364272, A364349, A364756.
%K A364914 nonn
%O A364914 0,4
%A A364914 _Gus Wiseman_, Aug 17 2023
%E A364914 a(12)-a(34) from _Chai Wah Wu_, Nov 17 2023