cp's OEIS Frontend

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

%I A367400 #10 Nov 21 2023 16:42:49
%S A367400 1,2,4,7,13,25,47,88,166,313,589,1109,2089,3934,7408,13951,26273,
%T A367400 49477,93175,175468,330442,622289,1171897,2206921,4156081,7826746,
%U A367400 14739356,27757207,52272469,98439697,185381983,349112000,657448942,1238110153
%N A367400 Number of subsets of {1..n} whose cardinality is not the sum of two distinct elements.
%F A367400 Conjectures from _Chai Wah Wu_, Nov 21 2023: (Start)
%F A367400 a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) - a(n-4) for n > 3.
%F A367400 G.f.: (-x^3 + x^2 + 1)/(x^4 - 2*x^3 + x^2 - 2*x + 1). (End)
%e A367400 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 A367400 The a(0) = 1 through a(4) = 13 subsets:
%e A367400   {}  {}   {}     {}     {}
%e A367400       {1}  {1}    {1}    {1}
%e A367400            {2}    {2}    {2}
%e A367400            {1,2}  {3}    {3}
%e A367400                   {1,2}  {4}
%e A367400                   {1,3}  {1,2}
%e A367400                   {2,3}  {1,3}
%e A367400                          {1,4}
%e A367400                          {2,3}
%e A367400                          {2,4}
%e A367400                          {3,4}
%e A367400                          {1,3,4}
%e A367400                          {2,3,4}
%t A367400 Table[Length[Select[Subsets[Range[n]], FreeQ[Total/@Subsets[#, {2}], Length[#]]&]], {n,0,10}]
%o A367400 (Python)
%o A367400 from itertools import combinations
%o A367400 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 A367400 The version containing n appears to be A112575.
%Y A367400 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 A367400              sum-full  sum-free  comb-full comb-free semi-full semi-free
%Y A367400             -----------------------------------------------------------
%Y A367400 partitions:  A367212   A367213   A367218   A367219   A367394   A367398
%Y A367400 strict:      A367214   A367215   A367220   A367221   A367395   A367399
%Y A367400 subsets:     A367216   A367217   A367222   A367223   A367396   A367400*
%Y A367400 ranks:       A367224   A367225   A367226   A367227   A367397   A367401
%Y A367400 A002865 counts partitions whose length is a part, complement A229816.
%Y A367400 A364534 counts sum-full subsets.
%Y A367400 A088809 and A093971 count subsets containing semi-sums.
%Y A367400 A236912 counts partitions with no semi-sum of the parts, ranks A364461.
%Y A367400 A366738 counts semi-sums of partitions, strict A366741.
%Y A367400 Triangles:
%Y A367400 A365381 counts subsets with a subset summing to k, complement A366320.
%Y A367400 A365541 counts subsets with a semi-sum k.
%Y A367400 A367404 counts partitions with a semi-sum k, strict A367405.
%Y A367400 Cf. A237113, A237667, A238628, A304792, A363225, A364272, A365543, A365658, A365918, A366131, A366740.
%K A367400 nonn,more
%O A367400 0,2
%A A367400 _Gus Wiseman_, Nov 21 2023
%E A367400 a(18)-a(33) from _Chai Wah Wu_, Nov 21 2023