A365380 Number of subsets of {1..n} that cannot be linearly combined using nonnegative coefficients to obtain n.

1, 1, 2, 2, 6, 4, 16, 12, 32, 32, 104, 48, 256, 208, 448, 448, 1568, 896, 3840, 2368, 6912, 7680, 22912, 10752, 50688, 44800, 104448, 88064, 324096, 165888, 780288, 541696, 1458176, 1519616, 4044800, 2220032, 10838016, 8744960, 20250624, 16433152, 62267392, 34865152

Offset

1,3

Links

Andrew Howroyd, Table of n, a(n) for n = 1..100

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

Formula

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

Example

The set {4,5,6} cannot be linearly combined to obtain 7 so is counted under a(7), but we have 8 = 2*4 + 0*5 + 0*6, so it is not counted under a(8).
The a(1) = 1 through a(8) = 12 subsets:
  {}  {}  {}   {}   {}     {}     {}       {}
          {2}  {3}  {2}    {4}    {2}      {3}
                    {3}    {5}    {3}      {5}
                    {4}    {4,5}  {4}      {6}
                    {2,4}         {5}      {7}
                    {3,4}         {6}      {3,6}
                                  {2,4}    {3,7}
                                  {2,6}    {5,6}
                                  {3,5}    {5,7}
                                  {3,6}    {6,7}
                                  {4,5}    {3,6,7}
                                  {4,6}    {5,6,7}
                                  {5,6}
                                  {2,4,6}
                                  {3,5,6}
                                  {4,5,6}

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-1]], combs[n, #]=={}&]], {n, 5}]

Crossrefs

The complement is counted by A365073, without n A365542.

The binary complement is A365314, positive A365315.

The binary case is A365320, positive A365321.

For positive coefficients we have A365322, complement A088314.

A124506 appears to count combination-free subsets, differences of A326083.

A179822 counts sum-closed subsets, first differences of A326080.

A288728 counts binary sum-free subsets, first differences of A007865.

A365046 counts combination-full subsets, first differences of A364914.

A365071 counts sum-free subsets, first differences of A151897.

Cf. A050291, A085489, A088528, A088809, A093971, A326020, A364350, A364534, A365043, A365045.

Sequence in context: A056463 A309694 A325263 * A005992 A085050 A329249

Adjacent sequences: A365377 A365378 A365379 * A365381 A365382 A365383

Keyword

nonn

Author

Gus Wiseman, Sep 04 2023

Extensions

Terms a(12) and beyond from Andrew Howroyd, Sep 04 2023

Status

approved