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

0, 0, 2, 2, 10, 14, 46, 74, 202, 350, 862, 1562, 3610, 6734, 14926, 28394, 61162, 117950, 249022, 484922, 1009210, 1979054, 4076206, 8034314, 16422922, 32491550, 66045982, 131029082, 265246810, 527304974, 1064175886, 2118785834, 4266269482, 8503841150, 17093775742, 34101458042, 68461196410, 136664112494

Offset: 0

Author

Gus Wiseman, Oct 07 2023

Keywords

• nonn
• easy

Examples

			The a(0) = 0 through a(5) = 14 subsets:
  .  .  {1}    {1,2}    {2}        {1,4}
        {1,2}  {1,2,3}  {1,2}      {2,3}
                        {1,3}      {1,2,3}
                        {2,3}      {1,2,4}
                        {2,4}      {1,3,4}
                        {1,2,3}    {1,4,5}
                        {1,2,4}    {2,3,4}
                        {1,3,4}    {2,3,5}
                        {2,3,4}    {1,2,3,4}
                        {1,2,3,4}  {1,2,3,5}
                                   {1,2,4,5}
                                   {1,3,4,5}
                                   {2,3,4,5}
                                   {1,2,3,4,5}
		

Links

• Index entries for linear recurrences with constant coefficients, signature (2,3,-6).

Crossrefs

The complement is counted by A117855.

For pairs summing to n + 1 we have A167936.

A068911 counts subsets of {1..n} w/o two distinct elements summing to n.

A093971/A088809/A364534 count certain types of sum-full subsets.

Cf. A008967, A167762, A238628, A365376, A365377, A365381, A365541, A365544.

Programs

Mathematica

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

Python

def A366131(n): return (1<>1)<<1) if n else 0 # Chai Wah Wu, Nov 14 2023

Formula

From Chai Wah Wu, Nov 14 2023: (Start)

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

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