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,3

Links

Table of n, a(n) for n=0..37.

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

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)

Example

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}

Mathematica

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

Prog

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

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.

Sequence in context: A015623 A164124 A003609 * A307538 A316200 A360636

Adjacent sequences: A366128 A366129 A366130 * A366132 A366133 A366134

Keyword

nonn,easy

Author

Gus Wiseman, Oct 07 2023

Status

approved