cp's OEIS Frontend

A366131 Number of subsets of {1..n} with two elements (possibly the same) summing to n.

%I A366131 #21 Dec 04 2023 06:39:47
%S A366131 0,0,2,2,10,14,46,74,202,350,862,1562,3610,6734,14926,28394,61162,
%T A366131 117950,249022,484922,1009210,1979054,4076206,8034314,16422922,
%U A366131 32491550,66045982,131029082,265246810,527304974,1064175886,2118785834,4266269482,8503841150,17093775742,34101458042,68461196410,136664112494
%N A366131 Number of subsets of {1..n} with two elements (possibly the same) summing to n.
%H A366131 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,3,-6).
%F A366131 From _Chai Wah Wu_, Nov 14 2023: (Start)
%F A366131 a(n) = 2*a(n-1) + 3*a(n-2) - 6*a(n-3) for n > 3.
%F A366131 G.f.: 2*x^2*(1 - x)/((2*x - 1)*(3*x^2 - 1)). (End)
%e A366131 The a(0) = 0 through a(5) = 14 subsets:
%e A366131   .  .  {1}    {1,2}    {2}        {1,4}
%e A366131         {1,2}  {1,2,3}  {1,2}      {2,3}
%e A366131                         {1,3}      {1,2,3}
%e A366131                         {2,3}      {1,2,4}
%e A366131                         {2,4}      {1,3,4}
%e A366131                         {1,2,3}    {1,4,5}
%e A366131                         {1,2,4}    {2,3,4}
%e A366131                         {1,3,4}    {2,3,5}
%e A366131                         {2,3,4}    {1,2,3,4}
%e A366131                         {1,2,3,4}  {1,2,3,5}
%e A366131                                    {1,2,4,5}
%e A366131                                    {1,3,4,5}
%e A366131                                    {2,3,4,5}
%e A366131                                    {1,2,3,4,5}
%t A366131 Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Tuples[#,2],n]&]],{n,0,10}]
%o A366131 (Python)
%o A366131 def A366131(n): return (1<<n)-(3**(n-1>>1)<<1) if n else 0 # _Chai Wah Wu_, Nov 14 2023
%Y A366131 The complement is counted by A117855.
%Y A366131 For pairs summing to n + 1 we have A167936.
%Y A366131 A068911 counts subsets of {1..n} w/o two distinct elements summing to n.
%Y A366131 A093971/A088809/A364534 count certain types of sum-full subsets.
%Y A366131 Cf. A008967, A167762, A238628, A365376, A365377, A365381, A365541, A365544.
%K A366131 nonn,easy
%O A366131 0,3
%A A366131 _Gus Wiseman_, Oct 07 2023