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

0, 0, 1, 3, 9, 20, 48, 101, 219, 454, 944, 1917, 3925, 7915, 16004, 32188, 64751, 129822, 260489, 521672, 1045060, 2091808, 4187047, 8377255, 16762285, 33531228, 67077485, 134170217, 268371678, 536772231, 1073611321, 2147282291, 4294697258, 8589527163, 17179321094

Offset: 0

Author

Gus Wiseman, Aug 17 2023

Keywords

• nonn

Comments

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.

Examples

			The set {3,4,5,17} has 17 = 1*3 + 1*4 + 2*5, so is counted under a(17).
The a(0) = 0 through a(5) = 20 subsets:
  .  .  {1,2}  {1,2}    {1,2}      {1,2}
               {1,3}    {1,3}      {1,3}
               {1,2,3}  {1,4}      {1,4}
                        {2,4}      {1,5}
                        {1,2,3}    {2,4}
                        {1,2,4}    {1,2,3}
                        {1,3,4}    {1,2,4}
                        {2,3,4}    {1,2,5}
                        {1,2,3,4}  {1,3,4}
                                   {1,3,5}
                                   {1,4,5}
                                   {2,3,4}
                                   {2,3,5}
                                   {2,4,5}
                                   {1,2,3,4}
                                   {1,2,3,5}
                                   {1,2,4,5}
                                   {1,3,4,5}
                                   {2,3,4,5}
                                   {1,2,3,4,5}
		

Links

• Steven R. Finch, Monoids of natural numbers, March 17, 2009.

Crossrefs

The binary complement is A007865.

The binary version without re-usable parts is A088809.

The binary version is A093971.

The complement without re-usable parts is A151897.

The complement is counted by A326083.

The version without re-usable parts is A364534.

The version for strict partitions is A364839, complement A364350.

The version for partitions is A364913.

The version for positive combinations is A365043, complement A365044.

First differences are A365046.

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

Programs

Mathematica

combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],Or@@Table[combs[#[[k]],Delete[#,k]]!={},{k,Length[#]}]&]],{n,0,10}]

Python

from itertools import combinations
from sympy.utilities.iterables import partitions
def A364914(n):
    c, mlist = 0, []
    for m in range(1,n+1):
        t = set()
        for p in partitions(m,k=m-1):
            t.add(tuple(sorted(p.keys())))
        mlist.append([set(d) for d in t])
    for k in range(2,n+1):
        for w in combinations(range(1,n+1),k):
            ws = set(w)
            for d in w:
                for s in mlist[d-1]:
                    if s <= ws:
                        c += 1
                        break
                else:
                    continue
                break
    return c # Chai Wah Wu, Nov 17 2023

Extensions

a(12)-a(34) from Chai Wah Wu, Nov 17 2023