|
%I #12 Sep 12 2023 13:59:20
%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 S. 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
|
