A367400 - OEIS

%I #10 Nov 21 2023 16:42:49

%S 1,2,4,7,13,25,47,88,166,313,589,1109,2089,3934,7408,13951,26273,

%T 49477,93175,175468,330442,622289,1171897,2206921,4156081,7826746,

%U 14739356,27757207,52272469,98439697,185381983,349112000,657448942,1238110153

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

%F Conjectures from _Chai Wah Wu_, Nov 21 2023: (Start)

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

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

%e 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 counted under a(8).

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

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

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

%e            {2}    {2}    {2}

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

%e                   {1,2}  {4}

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

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

%e                          {1,4}

%e                          {2,3}

%e                          {2,4}

%e                          {3,4}

%e                          {1,3,4}

%e                          {2,3,4}

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

%o (Python)

%o from itertools import combinations

%o def A367400(n): return (n*(n+1)>>1)+1+sum(1 for k in range(3,n+1) for w in (set(d) for d in combinations(range(1,n+1),k)) if not any({a,k-a}<=w for a in range(1,k+1>>1))) # _Chai Wah Wu_, Nov 21 2023

%Y The version containing n appears to be A112575.

%Y 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.

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

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

%Y partitions:  A367212   A367213   A367218   A367219   A367394   A367398

%Y strict:      A367214   A367215   A367220   A367221   A367395   A367399

%Y subsets:     A367216   A367217   A367222   A367223   A367396   A367400*

%Y ranks:       A367224   A367225   A367226   A367227   A367397   A367401

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

%Y A364534 counts sum-full subsets.

%Y A088809 and A093971 count subsets containing semi-sums.

%Y A236912 counts partitions with no semi-sum of the parts, ranks A364461.

%Y A366738 counts semi-sums of partitions, strict A366741.

%Y Triangles:

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

%Y A365541 counts subsets with a semi-sum k.

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

%Y Cf. A237113, A237667, A238628, A304792, A363225, A364272, A365543, A365658, A365918, A366131, A366740.

%K nonn,more

%O 0,2

%A _Gus Wiseman_, Nov 21 2023

%E a(18)-a(33) from _Chai Wah Wu_, Nov 21 2023