|
|
A367400
|
|
Number of subsets of {1..n} whose cardinality is not the sum of two distinct elements.
|
|
8
|
|
|
1, 2, 4, 7, 13, 25, 47, 88, 166, 313, 589, 1109, 2089, 3934, 7408, 13951, 26273, 49477, 93175, 175468, 330442, 622289, 1171897, 2206921, 4156081, 7826746, 14739356, 27757207, 52272469, 98439697, 185381983, 349112000, 657448942, 1238110153
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) - a(n-4) for n > 3.
G.f.: (-x^3 + x^2 + 1)/(x^4 - 2*x^3 + x^2 - 2*x + 1). (End)
|
|
EXAMPLE
|
The set s = {1,2,3,6,7,8} has the following sums of pairs of distinct elements: {3,4,5,7,8,9,10,11,13,14,15}. This does not include 6, so s is counted under a(8).
The a(0) = 1 through a(4) = 13 subsets:
{} {} {} {} {}
{1} {1} {1} {1}
{2} {2} {2}
{1,2} {3} {3}
{1,2} {4}
{1,3} {1,2}
{2,3} {1,3}
{1,4}
{2,3}
{2,4}
{3,4}
{1,3,4}
{2,3,4}
|
|
MATHEMATICA
|
Table[Length[Select[Subsets[Range[n]], FreeQ[Total/@Subsets[#, {2}], Length[#]]&]], {n, 0, 10}]
|
|
PROG
|
(Python)
from itertools import combinations
def A367400(n): return (n*(n+1)>>1)+1+sum(1 for k in range(3, n+1) for w in (set(d) for d in combinations(range(1, n+1), k)) if not any({a, k-a}<=w for a in range(1, k+1>>1))) # Chai Wah Wu, Nov 21 2023
|
|
CROSSREFS
|
The version containing n appears to be A112575.
The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum, linear combination, or semi-sum of the parts. The current sequence is starred.
sum-full sum-free comb-full comb-free semi-full semi-free
-----------------------------------------------------------
A236912 counts partitions with no semi-sum of the parts, ranks A364461.
Triangles:
A365381 counts subsets with a subset summing to k, complement A366320.
A365541 counts subsets with a semi-sum k.
Cf. A237113, A237667, A238628, A304792, A363225, A364272, A365543, A365658, A365918, A366131, A366740.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|