A365043 Number of subsets of {1..n} whose greatest element can be written as a (strictly) positive linear combination of the others.

0, 0, 1, 3, 7, 12, 21, 32, 49, 70, 99, 135, 185, 245, 323, 418, 541, 688, 873, 1094, 1368, 1693, 2092, 2564, 3138, 3810, 4620, 5565, 6696, 8012, 9569, 11381, 13518, 15980, 18872, 22194

Offset

0,4

Comments

Sets of this type may be called "positive combination-full".

Also subsets of {1..n} such that some element can be written as a (strictly) positive linear combination of the others.

Links

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

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

Formula

a(n) = 2^n - A365044(n).

Example

The subset S = {3,4,9} has 9 = 3*3 + 0*4, but this is not strictly positive, so S is not counted under a(9).
The subset S = {3,4,10} has 10 = 2*3 + 1*4, so S is counted under a(10).
The a(0) = 0 through a(5) = 12 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}
                                 {1,2,5}
                                 {1,3,4}
                                 {1,3,5}
                                 {1,4,5}
                                 {2,3,5}

Mathematica

combp[n_, y_]:=With[{s=Table[{k, i}, {k, y}, {i, 1, Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[Rest[Subsets[Range[n]]], combp[Last[#], Union[Most[#]]]!={}&]], {n, 0, 10}]

Prog

(Python)
from itertools import combinations
from sympy.utilities.iterables import partitions
def A365043(n):
    mlist = tuple({tuple(sorted(p.keys())) for p in partitions(m, k=m-1)} for m in range(1, n+1))
    return sum(1 for k in range(2, n+1) for w in combinations(range(1, n+1), k) if w[:-1] in mlist[w[-1]-1]) # Chai Wah Wu, Nov 20 2023

Crossrefs

The binary complement is A007865, first differences A288728.

The binary version is A093971, first differences A365070.

The nonnegative complement is A326083, first differences A124506.

The nonnegative version is A364914, first differences A365046.

First differences are A365042.

The complement is counted by A365044, first differences A365045.

Without re-usable parts we have A364534, first differences A365069.

A085489 and A364755 count subsets with no sum of two distinct elements.

A088809 and A364756 count subsets with some sum of two distinct elements.

A364350 counts combination-free strict partitions, complement A364839.

A364913 counts combination-full partitions.

Cf. A151897, A237113, A237668, A308546, A324736, A326020, A326080, A364272.

Sequence in context: A337656 A029452 A367892 * A294422 A034434 A243190

Adjacent sequences: A365040 A365041 A365042 * A365044 A365045 A365046

Keyword

nonn,more

Author

Gus Wiseman, Aug 25 2023

Extensions

a(15)-a(35) from Chai Wah Wu, Nov 20 2023

Status

approved