A364914 - OEIS

%I #23 Dec 13 2024 09:39:31

%S 0,0,1,3,9,20,48,101,219,454,944,1917,3925,7915,16004,32188,64751,

%T 129822,260489,521672,1045060,2091808,4187047,8377255,16762285,

%U 33531228,67077485,134170217,268371678,536772231,1073611321,2147282291,4294697258,8589527163,17179321094

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

%C 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 Steven R. Finch, <a href="/A066062/a066062.pdf">Monoids of natural numbers</a>, March 17, 2009.

%e The set {3,4,5,17} has 17 = 1*3 + 1*4 + 2*5, so is counted under a(17).

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

%e   .  .  {1,2}  {1,2}    {1,2}      {1,2}

%e                {1,3}    {1,3}      {1,3}

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

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

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

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

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

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

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

%e                                    {1,3,5}

%e                                    {1,4,5}

%e                                    {2,3,4}

%e                                    {2,3,5}

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

%t Table[Length[Select[Subsets[Range[n]],Or@@Table[combs[#[[k]],Delete[#,k]]!={},{k,Length[#]}]&]],{n,0,10}]

%o (Python)

%o from itertools import combinations

%o from sympy.utilities.iterables import partitions

%o def A364914(n):

%o     c, mlist = 0, []

%o     for m in range(1,n+1):

%o         t = set()

%o         for p in partitions(m,k=m-1):

%o             t.add(tuple(sorted(p.keys())))

%o         mlist.append([set(d) for d in t])

%o     for k in range(2,n+1):

%o         for w in combinations(range(1,n+1),k):

%o             ws = set(w)

%o             for d in w:

%o                 for s in mlist[d-1]:

%o                     if s <= ws:

%o                         c += 1

%o                         break

%o                 else:

%o                     continue

%o                 break

%o     return c # _Chai Wah Wu_, Nov 17 2023

%Y The binary complement is A007865.

%Y The binary version without re-usable parts is A088809.

%Y The binary version is A093971.

%Y The complement without re-usable parts is A151897.

%Y The complement is counted by A326083.

%Y The version without re-usable parts is A364534.

%Y The version for strict partitions is A364839, complement A364350.

%Y The version for partitions is A364913.

%Y The version for positive combinations is A365043, complement A365044.

%Y First differences are A365046.

%Y Cf. A011782, A085489, A103580, A116861, A124506, A237113, A237668, A308546, A324736, A326020, A326080, A364272, A364349, A364756.

%K nonn

%O 0,4

%A _Gus Wiseman_, Aug 17 2023

%E a(12)-a(34) from _Chai Wah Wu_, Nov 17 2023