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

Links

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

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

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)

Example

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}

Mathematica

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

Prog

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

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.

Sequence in context: A283353 A323656 A338740 * A360791 A304341 A372941

Adjacent sequences: A365541 A365542 A365543 * A365545 A365546 A365547

Keyword

nonn,easy,changed

Author

Gus Wiseman, Sep 20 2023

Status

approved