A365544 Number of subsets of {1..n} containing two distinct elements summing to n.

0, 0, 0, 2, 4, 14, 28, 74, 148, 350, 700, 1562, 3124, 6734, 13468, 28394, 56788, 117950, 235900, 484922, 969844, 1979054, 3958108, 8034314, 16068628, 32491550, 64983100, 131029082, 262058164, 527304974, 1054609948, 2118785834, 4237571668, 8503841150, 17007682300

Offset: 0

Author

Gus Wiseman, Sep 20 2023

Keywords

• nonn
• easy

Examples

			The a(1) = 0 through a(5) = 14 subsets:
  .  .  {1,2}    {1,3}      {1,4}
        {1,2,3}  {1,2,3}    {2,3}
                 {1,3,4}    {1,2,3}
                 {1,2,3,4}  {1,2,4}
                            {1,3,4}
                            {1,4,5}
                            {2,3,4}
                            {2,3,5}
                            {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

For strict partitions we have A140106 shifted left.

The version for partitions is A004526.

The complement is counted by A068911.

For all subsets of elements we have A365376.

Main diagonal k = n of A365541.

A000009 counts subsets summing to n.

A007865/A085489/A151897 count certain types of sum-free subsets.

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

A365381 counts subsets with a subset summing to k.

Cf. A008967, A095944, A167762, A238628, A288728, A326083, A364272, A365377.

Programs

Mathematica

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

Python

def A365544(n): return (1<>1)<<1 if n&1 else 3**(n-1>>1)<<2) if n else 0 # Chai Wah Wu, Aug 30 2024

Formula

a(n) = 2^n - A068911(n).

From Alois P. Heinz, Aug 30 2024: (Start)

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

a(n) = 2 * A167762(n-1) for n>=1. (End)