login
Let m = number of ways of partitioning n into parts using all the parts of a subset of {1, 2, ..., n-1} whose sum of all parts of a subset is less than n; a(n) gives number of different subsets of {1, 2, ..., n-1} whose m is 0.
12

%I #19 Sep 12 2023 20:49:10

%S 0,0,1,1,3,3,6,6,10,12,17,18,26,30,40,44,58,66,84,95,120,135,166,186,

%T 230,257,314,350,421,476,561,626,749,831,986,1095,1276,1424,1666,1849,

%U 2138,2388,2741,3042,3522,3879,4441,4928,5617,6222,7084,7802,8852,9800

%N Let m = number of ways of partitioning n into parts using all the parts of a subset of {1, 2, ..., n-1} whose sum of all parts of a subset is less than n; a(n) gives number of different subsets of {1, 2, ..., n-1} whose m is 0.

%C Note that {2, 3} is counted for n = 6 because although 6 = 2+2+2 = 3+3, there is no partition that includes both 2 and 3. - _David Wasserman_, Aug 09 2005

%C Said differently, a(n) is the number of finite nonempty sets of positive integers with sum < n that cannot be linearly combined using all positive coefficients to obtain n. - _Gus Wiseman_, Sep 10 2023

%e a(5)=3 because there are three different subsets, {2}, {3} & {4}; a(6)=3 because there are three different subsets, {4}, {5} & {2,3}.

%e From _Gus Wiseman_, Sep 10 2023: (Start)

%e The set {3,5} is not counted under a(8) because 1*3 + 1*5 = 8, but it is counted under a(9) and a(10), and it is not counted under a(11) because 2*3 + 1*5 = 11.

%e The a(3) = 1 through a(11) = 17 subsets:

%e {2} {3} {2} {4} {2} {3} {2} {3} {2}

%e {3} {5} {3} {5} {4} {4} {3}

%e {4} {2,3} {4} {6} {5} {6} {4}

%e {5} {7} {6} {7} {5}

%e {6} {2,5} {7} {8} {6}

%e {2,4} {3,4} {8} {9} {7}

%e {2,4} {2,5} {8}

%e {2,6} {2,7} {9}

%e {3,4} {3,5} {10}

%e {3,5} {3,6} {2,4}

%e {4,5} {2,6}

%e {2,3,4} {2,8}

%e {3,6}

%e {3,7}

%e {4,5}

%e {4,6}

%e {2,3,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[Select[Subsets[Range[n]],0<Total[#]<n&],combp[n,#]=={}&]],{n,15}] (* _Gus Wiseman_, Sep 12 2023 *)

%Y The complement is A088571, allowing sum n A088314.

%Y For sets with max < n instead of sum < n we have A365045, nonempty A070880.

%Y For nonnegative coefficients we have A365312, complement A365311.

%Y For sets with max <= n we have A365322.

%Y For partitions we have A365323, nonnegative A365378.

%Y A116861 and A364916 count linear combinations of strict partitions.

%Y A326083 and A124506 appear to count combination-free subsets.

%Y Cf. A000009, A326080, A364350, A364534, A365043, A365321, A365380.

%K easy,nonn

%O 1,5

%A _Naohiro Nomoto_, Nov 16 2003

%E More terms from _David Wasserman_, Aug 09 2005