A364914 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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.

S. 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

AUTHOR

Gus Wiseman, Aug 17 2023

EXTENSIONS

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

STATUS

approved