A365380 - OEIS

%I #15 Dec 13 2024 09:42:12

%S 1,1,2,2,6,4,16,12,32,32,104,48,256,208,448,448,1568,896,3840,2368,

%T 6912,7680,22912,10752,50688,44800,104448,88064,324096,165888,780288,

%U 541696,1458176,1519616,4044800,2220032,10838016,8744960,20250624,16433152,62267392,34865152

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

%H Andrew Howroyd, <a href="/A365380/b365380.txt">Table of n, a(n) for n = 1..100</a>

%H Steven R. Finch, <a href="/A066062/a066062.pdf">Monoids of natural numbers</a>, March 17, 2009.

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

%e 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).

%e The a(1) = 1 through a(8) = 12 subsets:

%e   {}  {}  {}   {}   {}     {}     {}       {}

%e           {2}  {3}  {2}    {4}    {2}      {3}

%e                     {3}    {5}    {3}      {5}

%e                     {4}    {4,5}  {4}      {6}

%e                     {2,4}         {5}      {7}

%e                     {3,4}         {6}      {3,6}

%e                                   {2,4}    {3,7}

%e                                   {2,6}    {5,6}

%e                                   {3,5}    {5,7}

%e                                   {3,6}    {6,7}

%e                                   {4,5}    {3,6,7}

%e                                   {4,6}    {5,6,7}

%e                                   {5,6}

%e                                   {2,4,6}

%e                                   {3,5,6}

%e                                   {4,5,6}

%t combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];

%t Table[Length[Select[Subsets[Range[n-1]],combs[n,#]=={}&]],{n,5}]

%Y The complement is counted by A365073, without n A365542.

%Y The binary complement is A365314, positive A365315.

%Y The binary case is A365320, positive A365321.

%Y For positive coefficients we have A365322, complement A088314.

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

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

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

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

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

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

%K nonn

%O 1,3

%A _Gus Wiseman_, Sep 04 2023

%E Terms a(12) and beyond from _Andrew Howroyd_, Sep 04 2023