cp's OEIS Frontend

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

%I A367396 #28 Dec 30 2023 17:00:53
%S A367396 0,0,0,1,3,7,17,40,90,199,435,939,2007,4258,8976,18817,39263,81595,
%T A367396 168969,348820,718134,1474863,3022407,6181687,12621135,25727686,
%U A367396 52369508,106460521,216162987,438431215,888359841,1798371648,3637518354,7351824439,14848255803
%N A367396 Number of subsets of {1..n} whose cardinality is the sum of two distinct elements.
%F A367396 Conjectures from _Chai Wah Wu_, Nov 21 2023: (Start)
%F A367396 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.
%F A367396 G.f.: x^3*(x - 1)/((2*x - 1)*(x^4 - 2*x^3 + x^2 - 2*x + 1)). (End)
%e A367396 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).
%e A367396 The a(0) = 0 through a(6) = 17 subsets:
%e A367396   .  .  .  {1,2,3}  {1,2,3}    {1,2,3}      {1,2,3}
%e A367396                     {1,2,4}    {1,2,4}      {1,2,4}
%e A367396                     {1,2,3,4}  {1,2,5}      {1,2,5}
%e A367396                                {1,2,3,4}    {1,2,6}
%e A367396                                {1,2,3,5}    {1,2,3,4}
%e A367396                                {1,3,4,5}    {1,2,3,5}
%e A367396                                {1,2,3,4,5}  {1,2,3,6}
%e A367396                                             {1,3,4,5}
%e A367396                                             {1,3,4,6}
%e A367396                                             {1,3,5,6}
%e A367396                                             {1,2,3,4,5}
%e A367396                                             {1,2,3,4,6}
%e A367396                                             {1,2,3,5,6}
%e A367396                                             {1,2,4,5,6}
%e A367396                                             {1,3,4,5,6}
%e A367396                                             {2,3,4,5,6}
%e A367396                                             {1,2,3,4,5,6}
%t A367396 Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Subsets[#,{2}],Length[#]]&]],{n,0,10}]
%o A367396 (Python)
%o A367396 from itertools import combinations
%o A367396 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
%Y A367396 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 A367396              sum-full  sum-free  comb-full comb-free semi-full semi-free
%Y A367396             -----------------------------------------------------------
%Y A367396 partitions:  A367212   A367213   A367218   A367219   A367394   A367398
%Y A367396 strict:      A367214   A367215   A367220   A367221   A367395   A367399
%Y A367396 subsets:     A367216   A367217   A367222   A367223   A367396*  A367400
%Y A367396 ranks:       A367224   A367225   A367226   A367227   A367397   A367401
%Y A367396 A002865 counts partitions whose length is a part, complement A229816.
%Y A367396 A364534 counts sum-full subsets.
%Y A367396 A088809 and A093971 count subsets containing semi-sums.
%Y A367396 A366738 counts semi-sums of partitions, strict A366741.
%Y A367396 Triangles:
%Y A367396 A365381 counts subsets with a subset summing to k, complement A366320.
%Y A367396 A365541 counts subsets with a semi-sum k.
%Y A367396 A367404 counts partitions with a semi-sum k, strict A367405.
%Y A367396 Cf. A236912, A237113, A237667, A237668, A304792, A363225, A364272, A365658, A366131, A366740.
%K A367396 nonn
%O A367396 0,5
%A A367396 _Gus Wiseman_, Nov 21 2023
%E A367396 a(18)-a(33) from _Chai Wah Wu_, Nov 21 2023
%E A367396 a(34) from _Paul Muljadi_, Nov 24 2023