A325867 - OEIS

A325867

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

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

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..150 (terms 1..121 from Bert Dobbelaere)

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)

# Bert Dobbelaere, Mar 07 2021

CROSSREFS

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

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

Sequence in context: A217662 A085619 A085620 * A333045 A050047 A056381

Adjacent sequences: A325864 A325865 A325866 * A325868 A325869 A325870

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jun 01 2019

EXTENSIONS

More terms from Bert Dobbelaere, Mar 07 2021

STATUS

approved