login
Number of maximal subsets of {1..n} containing n such that every subset has a different sum.
9

%I #22 Jan 13 2022 18:44:07

%S 1,1,2,2,4,8,10,12,17,34,45,77,99,136,166,200,238,328,402,660,674,

%T 1166,1331,1966,2335,3286,3527,4762,5383,6900,7543,9087,10149,12239,

%U 13569,16452,17867,22869,23977,33881,33820,43423,48090,68683,67347,95176,97917,131666,136205

%N Number of maximal subsets of {1..n} containing n such that every subset has a different sum.

%C These are maximal strict knapsack partitions (A275972, A326015) organized by maximum rather than sum.

%H Fausto A. C. Cariboni, <a href="/A325867/b325867.txt">Table of n, a(n) for n = 1..150</a> (terms 1..121 from Bert Dobbelaere)

%e The a(1) = 1 through a(8) = 12 subsets:

%e {1} {1,2} {1,3} {1,2,4} {1,2,5} {1,2,6} {1,2,7} {1,3,8}

%e {2,3} {2,3,4} {1,3,5} {1,3,6} {1,3,7} {1,5,8}

%e {2,4,5} {1,4,6} {1,4,7} {5,7,8}

%e {3,4,5} {2,3,6} {1,5,7} {1,2,4,8}

%e {2,5,6} {2,3,7} {1,4,6,8}

%e {3,4,6} {2,4,7} {2,3,4,8}

%e {3,5,6} {2,6,7} {2,4,5,8}

%e {4,5,6} {4,5,7} {2,4,7,8}

%e {4,6,7} {3,4,6,8}

%e {3,5,6,7} {3,6,7,8}

%e {4,5,6,8}

%e {4,6,7,8}

%t fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&)/@y];

%t Table[Length[fasmax[Select[Subsets[Range[n]],MemberQ[#,n]&&UnsameQ@@Plus@@@Subsets[#]&]]],{n,15}]

%o (Python)

%o def f(p0, n, m, cm):

%o full, t, p = True, 0, p0

%o while p<n:

%o sm = m<<p

%o if (m & sm) == 0:

%o t += f(p+1, n, m|sm, cm|(1<<p))

%o full=False

%o p+=1

%o if full:

%o for k in range(1, p0):

%o if ((cm>>k)&1)==0 and ((m<<k)&m)==0:

%o full=False

%o break

%o return 1 if full else t

%o def a325867(n):

%o return f(1, n, (1<<n)+1, 0)

%o # _Bert Dobbelaere_, Mar 07 2021

%Y Cf. A002033, A108917, A143823, A143824, A196723, A275972.

%Y Cf. A325860, A325861, A325864, A325865, A325866, A325867, A325880.

%K nonn

%O 1,3

%A _Gus Wiseman_, Jun 01 2019

%E More terms from _Bert Dobbelaere_, Mar 07 2021