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

0, 0, 1, 2, 4, 5, 9, 11, 17, 21, 29, 36, 50, 60, 78, 95, 123, 147, 185, 221, 274, 325, 399, 472, 574, 672, 810, 945, 1131, 1316, 1557, 1812, 2137, 2462, 2892, 3322, 3881, 4460, 5176, 5916, 6846, 7817, 8993, 10250, 11765, 13333, 15280, 17308, 19731, 22306

Offset

0,4

Comments

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

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

Links

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

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

Formula

a(n) = A088314(n) - 1.

Example

The subset {3,4,10} has 10 = 2*3 + 1*4 so is counted under a(10).
The a(0) = 0 through a(7) = 11 subsets:
  .  .  {1,2}  {1,3}    {1,4}    {1,5}    {1,6}      {1,7}
               {1,2,3}  {2,4}    {1,2,5}  {2,6}      {1,2,7}
                        {1,2,4}  {1,3,5}  {3,6}      {1,3,7}
                        {1,3,4}  {1,4,5}  {1,2,6}    {1,4,7}
                                 {2,3,5}  {1,3,6}    {1,5,7}
                                          {1,4,6}    {1,6,7}
                                          {1,5,6}    {2,3,7}
                                          {2,4,6}    {2,5,7}
                                          {1,2,3,6}  {3,4,7}
                                                     {1,2,3,7}
                                                     {1,2,4,7}

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]&&Or@@Table[combp[#[[k]], Union[Delete[#, k]]]!={}, {k, Length[#]}]&]], {n, 0, 10}]

Crossrefs

The nonnegative complement is A124506, first differences of A326083.

The binary complement is A288728, first differences of A007865.

First differences of A365043.

The complement is counted by A365045, first differences of A365044.

The nonnegative version is A365046, first differences of A364914.

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

The binary version is A365070, first differences of A093971.

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

A088314 counts sets that can be linearly combined to obtain n.

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: A211521 A396834 A039871 * A161375 A241408 A039021

Adjacent sequences: A365039 A365040 A365041 * A365043 A365044 A365045

Keyword

nonn

Author

Gus Wiseman, Aug 23 2023

Status

approved