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

%I #17 Aug 30 2024 21:28:21

%S 0,0,0,2,4,14,28,74,148,350,700,1562,3124,6734,13468,28394,56788,

%T 117950,235900,484922,969844,1979054,3958108,8034314,16068628,

%U 32491550,64983100,131029082,262058164,527304974,1054609948,2118785834,4237571668,8503841150,17007682300

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

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (2,3,-6).

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

%F From _Alois P. Heinz_, Aug 30 2024: (Start)

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

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

%e The a(1) = 0 through a(5) = 14 subsets:

%e . . {1,2} {1,3} {1,4}

%e {1,2,3} {1,2,3} {2,3}

%e {1,3,4} {1,2,3}

%e {1,2,3,4} {1,2,4}

%e {1,3,4}

%e {1,4,5}

%e {2,3,4}

%e {2,3,5}

%e {1,2,3,4}

%e {1,2,3,5}

%e {1,2,4,5}

%e {1,3,4,5}

%e {2,3,4,5}

%e {1,2,3,4,5}

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

%o (Python)

%o 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

%Y For strict partitions we have A140106 shifted left.

%Y The version for partitions is A004526.

%Y The complement is counted by A068911.

%Y For all subsets of elements we have A365376.

%Y Main diagonal k = n of A365541.

%Y A000009 counts subsets summing to n.

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

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

%Y A365381 counts subsets with a subset summing to k.

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

%K nonn,easy

%O 0,4

%A _Gus Wiseman_, Sep 20 2023