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,4

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.

Links

Table of n, a(n) for n=0..34.

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

Example

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}

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}]

Prog

(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

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.

Sequence in context: A065891 A321173 A147328 * A220770 A191527 A226106

Adjacent sequences: A364911 A364912 A364913 * A364915 A364916 A364917

Keyword

nonn,changed

Author

Gus Wiseman, Aug 17 2023

Extensions

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

Status

approved