A367396 Number of subsets of {1..n} whose cardinality is the sum of two distinct elements.

0, 0, 0, 1, 3, 7, 17, 40, 90, 199, 435, 939, 2007, 4258, 8976, 18817, 39263, 81595, 168969, 348820, 718134, 1474863, 3022407, 6181687, 12621135, 25727686, 52369508, 106460521, 216162987, 438431215, 888359841, 1798371648, 3637518354, 7351824439, 14848255803

Offset

0,5

Links

Table of n, a(n) for n=0..34.

Formula

Conjectures from Chai Wah Wu, Nov 21 2023: (Start)

a(n) = 4*a(n-1) - 5*a(n-2) + 4*a(n-3) - 5*a(n-4) + 2*a(n-5) for n > 4.

G.f.: x^3*(x - 1)/((2*x - 1)*(x^4 - 2*x^3 + x^2 - 2*x + 1)). (End)

Example

The set s = {1,2,3,6,7,8} has the following sums of pairs of distinct elements: {3,4,5,7,8,9,10,11,13,14,15}. This does not include 6, so s is not counted under a(8).
The a(0) = 0 through a(6) = 17 subsets:
  .  .  .  {1,2,3}  {1,2,3}    {1,2,3}      {1,2,3}
                    {1,2,4}    {1,2,4}      {1,2,4}
                    {1,2,3,4}  {1,2,5}      {1,2,5}
                               {1,2,3,4}    {1,2,6}
                               {1,2,3,5}    {1,2,3,4}
                               {1,3,4,5}    {1,2,3,5}
                               {1,2,3,4,5}  {1,2,3,6}
                                            {1,3,4,5}
                                            {1,3,4,6}
                                            {1,3,5,6}
                                            {1,2,3,4,5}
                                            {1,2,3,4,6}
                                            {1,2,3,5,6}
                                            {1,2,4,5,6}
                                            {1,3,4,5,6}
                                            {2,3,4,5,6}
                                            {1,2,3,4,5,6}

Mathematica

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

Prog

(Python)
from itertools import combinations
def A367396(n): return sum(1 for k in range(3, n+1) for w in (set(d) for d in combinations(range(1, n+1), k)) if any({a, k-a}<=w for a in range(1, k+1>>1))) # Chai Wah Wu, Nov 21 2023

Crossrefs

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

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

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

partitions: A367212 A367213 A367218 A367219 A367394 A367398

strict: A367214 A367215 A367220 A367221 A367395 A367399

subsets: A367216 A367217 A367222 A367223 A367396* A367400

ranks: A367224 A367225 A367226 A367227 A367397 A367401

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

A364534 counts sum-full subsets.

A088809 and A093971 count subsets containing semi-sums.

A366738 counts semi-sums of partitions, strict A366741.

Triangles:

A365381 counts subsets with a subset summing to k, complement A366320.

A365541 counts subsets with a semi-sum k.

A367404 counts partitions with a semi-sum k, strict A367405.

Cf. A236912, A237113, A237667, A237668, A304792, A363225, A364272, A365658, A366131, A366740.

Sequence in context: A005197 A147142 A298371 * A106472 A309538 A036885

Adjacent sequences: A367393 A367394 A367395 * A367397 A367398 A367399

Keyword

nonn

Author

Gus Wiseman, Nov 21 2023

Extensions

a(18)-a(33) from Chai Wah Wu, Nov 21 2023

a(34) from Paul Muljadi, Nov 24 2023

Status

approved