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

1, 2, 3, 5, 10, 20, 40, 82, 169, 348, 716, 1471, 3016, 6171, 12605, 25710, 52370, 106539, 216470, 439310, 890550, 1803415, 3648557, 7375141, 14896184, 30065129, 60639954, 122231740, 246239551, 495790161, 997747182, 2006969629, 4035274292, 8110185100, 16293958314, 32724456982

Offset: 0

Author

Gus Wiseman, Nov 12 2023

Keywords

• nonn

Examples

			The a(0) = 1 through a(4) = 10 subsets:
  {}  {}   {}     {}       {}
      {1}  {1}    {1}      {1}
           {1,2}  {1,2}    {1,2}
                  {2,3}    {2,3}
                  {1,2,3}  {2,4}
                           {1,2,3}
                           {1,2,4}
                           {1,3,4}
                           {2,3,4}
                           {1,2,3,4}
		

Crossrefs

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.

sum-full sum-free comb-full comb-free

-------------------------------------------

partitions: A367212 A367213 A367218 A367219

strict: A367214 A367215 A367220 A367221

subsets: A367216* A367217 A367222 A367223

ranks: A367224 A367225 A367226 A367227

A000009 counts subsets summing to n.

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

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

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

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

A237668 counts sum-full partitions, ranks A364532.

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

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

A365046 counts combination-full subsets, differences of A364914.

Triangles:

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

A365541 counts sets containing two distinct elements summing to k.

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

Programs

Mathematica

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

Formula

a(n) = 2^n - A367217(n). - Chai Wah Wu, Nov 14 2023

Extensions

a(16)-a(28) from Chai Wah Wu, Nov 14 2023

a(29)-a(35) from Max Alekseyev, Feb 25 2025