A365045 Number of subsets of {1..n} containing n such that no element can be written as a positive linear combination of the others.

0, 1, 1, 2, 4, 11, 23, 53, 111, 235, 483, 988, 1998, 4036, 8114, 16289, 32645, 65389, 130887, 261923, 524014, 1048251, 2096753, 4193832, 8388034, 16776544, 33553622, 67107919, 134216597, 268434140, 536869355, 1073740012, 2147481511, 4294964834, 8589931700

Offset

0,4

Comments

Also subsets of {1..n} containing n whose greatest element cannot be written as a positive linear combination of the others.

Links

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

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

Formula

a(n) = A070880(n) + 1 for n > 0.

Example

The subset {3,4,10} has 10 = 2*3 + 1*4 so is not counted under a(10).
The a(0) = 0 through a(5) = 11 subsets:
  .  {1}  {2}  {3}    {4}        {5}
               {2,3}  {3,4}      {2,5}
                      {2,3,4}    {3,5}
                      {1,2,3,4}  {4,5}
                                 {2,4,5}
                                 {3,4,5}
                                 {1,2,3,5}
                                 {1,2,4,5}
                                 {1,3,4,5}
                                 {2,3,4,5}
                                 {1,2,3,4,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[Subsets[Range[n]], MemberQ[#, n]&&And@@Table[combp[#[[k]], Union[Delete[#, k]]]=={}, {k, Length[#]}]&]], {n, 0, 10}]

Crossrefs

The nonempty case is A070880.

The nonnegative version is A124506, first differences of A326083.

The binary version is A288728, first differences of A007865.

A subclass is A341507.

The complement is counted by A365042, first differences of A365043.

First differences of A365044.

The nonnegative complement is A365046, first differences of A364914.

The binary complement is A365070, first differences of A093971.

Without re-usable parts we have A365071, first differences of A151897.

A085489 and A364755 count subsets w/o the sum of two distinct elements.

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

A364350 counts combination-free strict partitions, complement A364839.

A364913 counts combination-full partitions.

Cf. A237113, A237668, A308546, A324736, A326020, A326080, A364272, A364349, A364534, A365069.

Sequence in context: A038047 A358082 A061152 * A307881 A006452 A104430

Adjacent sequences: A365042 A365043 A365044 * A365046 A365047 A365048

Keyword

nonn

Author

Gus Wiseman, Aug 24 2023

Status

approved