|
|
A325867
|
|
Number of maximal subsets of {1..n} containing n such that every subset has a different sum.
|
|
9
|
|
|
1, 1, 2, 2, 4, 8, 10, 12, 17, 34, 45, 77, 99, 136, 166, 200, 238, 328, 402, 660, 674, 1166, 1331, 1966, 2335, 3286, 3527, 4762, 5383, 6900, 7543, 9087, 10149, 12239, 13569, 16452, 17867, 22869, 23977, 33881, 33820, 43423, 48090, 68683, 67347, 95176, 97917, 131666, 136205
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
These are maximal strict knapsack partitions (A275972, A326015) organized by maximum rather than sum.
|
|
LINKS
|
|
|
EXAMPLE
|
The a(1) = 1 through a(8) = 12 subsets:
{1} {1,2} {1,3} {1,2,4} {1,2,5} {1,2,6} {1,2,7} {1,3,8}
{2,3} {2,3,4} {1,3,5} {1,3,6} {1,3,7} {1,5,8}
{2,4,5} {1,4,6} {1,4,7} {5,7,8}
{3,4,5} {2,3,6} {1,5,7} {1,2,4,8}
{2,5,6} {2,3,7} {1,4,6,8}
{3,4,6} {2,4,7} {2,3,4,8}
{3,5,6} {2,6,7} {2,4,5,8}
{4,5,6} {4,5,7} {2,4,7,8}
{4,6,7} {3,4,6,8}
{3,5,6,7} {3,6,7,8}
{4,5,6,8}
{4,6,7,8}
|
|
MATHEMATICA
|
fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&)/@y];
Table[Length[fasmax[Select[Subsets[Range[n]], MemberQ[#, n]&&UnsameQ@@Plus@@@Subsets[#]&]]], {n, 15}]
|
|
PROG
|
(Python)
def f(p0, n, m, cm):
full, t, p = True, 0, p0
while p<n:
sm = m<<p
if (m & sm) == 0:
t += f(p+1, n, m|sm, cm|(1<<p))
full=False
p+=1
if full:
for k in range(1, p0):
if ((cm>>k)&1)==0 and ((m<<k)&m)==0:
full=False
break
return 1 if full else t
def a325867(n):
return f(1, n, (1<<n)+1, 0)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|