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

Author

Gus Wiseman, Sep 04 2023

Keywords

• nonn

Examples

			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}
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..100
• Steven R. Finch, Monoids of natural numbers, March 17, 2009.

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.

Programs

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}]

Formula

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

Extensions

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