cp's OEIS Frontend

A070880 Consider the 2^(n-1)-1 nonempty subsets S of {1, 2, ..., n-1}; a(n) gives number of such S for which it is impossible to partition n into parts from S such that each s in S is used at least once.

%I A070880 #36 Sep 12 2023 08:32:09
%S A070880 0,0,1,3,10,22,52,110,234,482,987,1997,4035,8113,16288,32644,65388,
%T A070880 130886,261922,524013,1048250,2096752,4193831,8388033,16776543,
%U A070880 33553621,67107918,134216596,268434139,536869354,1073740011,2147481510,4294964833,8589931699
%N A070880 Consider the 2^(n-1)-1 nonempty subsets S of {1, 2, ..., n-1}; a(n) gives number of such S for which it is impossible to partition n into parts from S such that each s in S is used at least once.
%C A070880 Also the number of nonempty subsets of {1..n-1} that cannot be linearly combined using all positive coefficients to obtain n. - _Gus Wiseman_, Sep 10 2023
%H A070880 Alois P. Heinz, <a href="/A070880/b070880.txt">Table of n, a(n) for n = 1..100</a>
%F A070880 a(n) = 2^(n-1) - A088314(n). - _Charlie Neder_, Feb 08 2019
%F A070880 a(n) = A365045(n) - 1. - _Gus Wiseman_, Sep 10 2023
%e A070880 a(4)=3 because there are three different subsets S of {1,2,3} satisfying the condition: {3}, {2,3} & {1,2,3}. For the other subsets S, such as {1,2}, there is a partition of 4 which uses them all (such as 4 = 1+1+2).
%e A070880 From _Gus Wiseman_, Sep 10 2023: (Start)
%e A070880 The a(6) = 22 subsets:
%e A070880   {4}  {2,3}  {1,2,4}  {1,2,3,4}  {1,2,3,4,5}
%e A070880   {5}  {2,5}  {1,2,5}  {1,2,3,5}
%e A070880        {3,4}  {1,3,4}  {1,2,4,5}
%e A070880        {3,5}  {1,3,5}  {1,3,4,5}
%e A070880        {4,5}  {1,4,5}  {2,3,4,5}
%e A070880               {2,3,4}
%e A070880               {2,3,5}
%e A070880               {2,4,5}
%e A070880               {3,4,5}
%e A070880 (End)
%t A070880 combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s], Total[Times@@@#]==n&]];
%t A070880 Table[Length[Select[Rest[Subsets[Range[n-1]]], combp[n,#]=={}&]],{n,7}] (* _Gus Wiseman_, Sep 10 2023 *)
%o A070880 (Python)
%o A070880 from sympy.utilities.iterables import partitions
%o A070880 def A070880(n): return (1<<n-1)-len({tuple(sorted(set(p))) for p in partitions(n)}) # _Chai Wah Wu_, Sep 10 2023
%Y A070880 For sets with sum < n instead of maximum < n we have A088528.
%Y A070880 The complement is counted by A365042, including empty set A088314.
%Y A070880 Allowing empty sets gives A365045, nonnegative version apparently A124506.
%Y A070880 Without re-usable parts we have A365377(n) - 1.
%Y A070880 For nonnegative (instead of positive) coefficients we have A365380(n) - 1.
%Y A070880 A326083 counts combination-free subsets, complement A364914.
%Y A070880 A364350 counts combination-free strict partitions, complement A364913.
%Y A070880 Cf. A007865, A085489, A093971, A151897, A326020, A326080, A364534, A365044.
%K A070880 easy,nonn
%O A070880 1,4
%A A070880 _Naohiro Nomoto_, Nov 16 2003
%E A070880 Edited by _N. J. A. Sloane_, Sep 09 2017
%E A070880 a(20)-a(34) from _Alois P. Heinz_, Feb 08 2019