cp's OEIS Frontend

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

%I A365322 #22 Dec 13 2024 09:42:08
%S A365322 0,1,2,5,11,26,54,116,238,490,994,2011,4045,8131,16305,32672,65412,
%T A365322 130924,261958,524066,1048301,2096826,4193904,8388135,16776641,
%U A365322 33553759,67108053,134216782,268434324,536869595,1073740266,2147481835,4294965158,8589932129
%N A365322 Number of subsets of {1..n} that cannot be linearly combined using positive coefficients to obtain n.
%C A365322 We consider (for example) that 2x + y + 3z is a positive linear combination of (x,y,z), but 2x + y is not, as the coefficient of z is 0.
%H A365322 Steven R. Finch, <a href="/A066062/a066062.pdf">Monoids of natural numbers</a>, March 17, 2009.
%F A365322 a(n) = 2^n - A088314(n).
%F A365322 a(n) = A070880(n) + 2^(n-1) for n>=1.
%e A365322 The set {1,3} has 4 = 1 + 3 so is not counted under a(4). However, 3 cannot be written as a linear combination of {1,3} using all positive coefficients, so it is counted under a(3).
%e A365322 The a(1) = 1 through a(4) = 11 subsets:
%e A365322   {}  {}     {}       {}
%e A365322       {1,2}  {2}      {3}
%e A365322              {1,3}    {1,4}
%e A365322              {2,3}    {2,3}
%e A365322              {1,2,3}  {2,4}
%e A365322                       {3,4}
%e A365322                       {1,2,3}
%e A365322                       {1,2,4}
%e A365322                       {1,3,4}
%e A365322                       {2,3,4}
%e A365322                       {1,2,3,4}
%p A365322 b:= proc(n, i) option remember; `if`(n=0, {{}}, `if`(i<1, {},
%p A365322       {b(n, i-1)[], seq(map(x->{x[], i}, b(n-i*j, i-1))[], j=1..n/i)}))
%p A365322     end:
%p A365322 a:= n-> 2^n-nops(b(n$2)):
%p A365322 seq(a(n), n=0..33);  # _Alois P. Heinz_, Sep 04 2023
%t A365322 cpu[n_,y_]:=With[{s=Table[{k,i},{k,Union[y]},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
%t A365322 Table[Length[Select[Subsets[Range[n]],cpu[n,#]=={}&]],{n,0,10}]
%o A365322 (Python)
%o A365322 from sympy.utilities.iterables import partitions
%o A365322 def A365322(n): return (1<<n)-len({tuple(sorted(set(p))) for p in partitions(n)}) # _Chai Wah Wu_, Sep 14 2023
%Y A365322 The complement is counted by A088314.
%Y A365322 The version for strict partitions is A088528.
%Y A365322 The nonnegative complement is counted by A365073, without n A365542.
%Y A365322 The binary complement is A365315, nonnegative A365314.
%Y A365322 The binary version is A365321, nonnegative A365320.
%Y A365322 For nonnegative coefficients we have A365380.
%Y A365322 A085489 and A364755 count subsets without the sum of two distinct elements.
%Y A365322 A124506 appears to count combination-free subsets, differences of A326083.
%Y A365322 A179822 counts sum-closed subsets, first differences of A326080.
%Y A365322 A364350 counts combination-free strict partitions, non-strict A364915.
%Y A365322 A365046 counts combination-full subsets, first differences of A364914.
%Y A365322 Cf. A070880, A088809, A093971, A151897, A326020, A364272, A364839, A365043, A365381.
%K A365322 nonn
%O A365322 0,3
%A A365322 _Gus Wiseman_, Sep 04 2023
%E A365322 More terms from _Alois P. Heinz_, Sep 04 2023