login
Number of subsets of {1..n} whose cardinality is equal to the sum of some subset.
24

%I #14 Nov 15 2023 08:04:22

%S 1,2,3,5,10,20,40,82,169,348,716,1471,3016,6171,12605,25710,52370,

%T 106539,216470,439310,890550,1803415,3648557,7375141,14896184,

%U 30065129,60639954,122231740,246239551

%N Number of subsets of {1..n} whose cardinality is equal to the sum of some subset.

%F a(n) = 2^n - A367217(n). - _Chai Wah Wu_, Nov 14 2023

%e The a(0) = 1 through a(4) = 10 subsets:

%e {} {} {} {} {}

%e {1} {1} {1} {1}

%e {1,2} {1,2} {1,2}

%e {2,3} {2,3}

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

%e {1,2,3}

%e {1,2,4}

%e {1,3,4}

%e {2,3,4}

%e {1,2,3,4}

%t Table[Length[Select[Subsets[Range[n]], MemberQ[Total/@Subsets[#], Length[#]]&]], {n,0,10}]

%Y The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.

%Y sum-full sum-free comb-full comb-free

%Y -------------------------------------------

%Y partitions: A367212 A367213 A367218 A367219

%Y strict: A367214 A367215 A367220 A367221

%Y subsets: A367216* A367217 A367222 A367223

%Y ranks: A367224 A367225 A367226 A367227

%Y A000009 counts subsets summing to n.

%Y A000124 counts distinct possible sums of subsets of {1..n}.

%Y A002865 counts partitions whose length is a part, complement A229816.

%Y A007865/A085489/A151897 count certain types of sum-free subsets.

%Y A088809/A093971/A364534 count certain types of sum-full subsets.

%Y A237668 counts sum-full partitions, ranks A364532.

%Y A240855 counts strict partitions whose length is a part, complement A240861.

%Y A364272 counts sum-full strict partitions, sum-free A364349.

%Y A365046 counts combination-full subsets, differences of A364914.

%Y Triangles:

%Y A365381 counts sets with a subset summing to k, without A366320.

%Y A365541 counts sets containing two distinct elements summing to k.

%Y Cf. A068911, A095944, A103580, A288728, A326080, A326083, A365376, A365544.

%K nonn,more

%O 0,2

%A _Gus Wiseman_, Nov 12 2023

%E a(16)-a(28) from _Chai Wah Wu_, Nov 14 2023