cp's OEIS Frontend

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

%I A365380 #15 Dec 13 2024 09:42:12
%S A365380 1,1,2,2,6,4,16,12,32,32,104,48,256,208,448,448,1568,896,3840,2368,
%T A365380 6912,7680,22912,10752,50688,44800,104448,88064,324096,165888,780288,
%U A365380 541696,1458176,1519616,4044800,2220032,10838016,8744960,20250624,16433152,62267392,34865152
%N A365380 Number of subsets of {1..n} that cannot be linearly combined using nonnegative coefficients to obtain n.
%H A365380 Andrew Howroyd, <a href="/A365380/b365380.txt">Table of n, a(n) for n = 1..100</a>
%H A365380 Steven R. Finch, <a href="/A066062/a066062.pdf">Monoids of natural numbers</a>, March 17, 2009.
%F A365380 a(n) = 2^n - A365073(n).
%e A365380 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 A365380 The a(1) = 1 through a(8) = 12 subsets:
%e A365380   {}  {}  {}   {}   {}     {}     {}       {}
%e A365380           {2}  {3}  {2}    {4}    {2}      {3}
%e A365380                     {3}    {5}    {3}      {5}
%e A365380                     {4}    {4,5}  {4}      {6}
%e A365380                     {2,4}         {5}      {7}
%e A365380                     {3,4}         {6}      {3,6}
%e A365380                                   {2,4}    {3,7}
%e A365380                                   {2,6}    {5,6}
%e A365380                                   {3,5}    {5,7}
%e A365380                                   {3,6}    {6,7}
%e A365380                                   {4,5}    {3,6,7}
%e A365380                                   {4,6}    {5,6,7}
%e A365380                                   {5,6}
%e A365380                                   {2,4,6}
%e A365380                                   {3,5,6}
%e A365380                                   {4,5,6}
%t A365380 combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
%t A365380 Table[Length[Select[Subsets[Range[n-1]],combs[n,#]=={}&]],{n,5}]
%Y A365380 The complement is counted by A365073, without n A365542.
%Y A365380 The binary complement is A365314, positive A365315.
%Y A365380 The binary case is A365320, positive A365321.
%Y A365380 For positive coefficients we have A365322, complement A088314.
%Y A365380 A124506 appears to count combination-free subsets, differences of A326083.
%Y A365380 A179822 counts sum-closed subsets, first differences of A326080.
%Y A365380 A288728 counts binary sum-free subsets, first differences of A007865.
%Y A365380 A365046 counts combination-full subsets, first differences of A364914.
%Y A365380 A365071 counts sum-free subsets, first differences of A151897.
%Y A365380 Cf. A050291, A085489, A088528, A088809, A093971, A326020, A364350, A364534, A365043, A365045.
%K A365380 nonn
%O A365380 1,3
%A A365380 _Gus Wiseman_, Sep 04 2023
%E A365380 Terms a(12) and beyond from _Andrew Howroyd_, Sep 04 2023