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