A325865 Number of maximal subsets of {1..n} of which every subset has a different sum.

1, 1, 1, 3, 3, 6, 14, 23, 27, 40, 64, 104, 180, 275, 399, 554, 679, 872, 1117, 1431, 1920, 2520, 3530, 4751, 6644, 8855, 12021, 15461, 19939, 25109, 31656, 38750, 46204, 55650, 65942, 78045, 91304, 106592, 124761, 145701, 172343, 201217, 238739, 280601, 339746, 400394

Offset

0,4

Links

Andrew Howroyd, Table of n, a(n) for n = 0..60

Example

The a(1) = 1 through a(6) = 14 subsets:
  {1}  {1,2}  {1,2}  {1,3}    {1,2,4}  {1,2,4}
              {1,3}  {1,2,4}  {1,2,5}  {1,2,5}
              {2,3}  {2,3,4}  {1,3,5}  {1,2,6}
                              {2,3,4}  {1,3,5}
                              {2,4,5}  {1,3,6}
                              {3,4,5}  {1,4,6}
                                       {2,3,4}
                                       {2,3,6}
                                       {2,4,5}
                                       {2,5,6}
                                       {3,4,5}
                                       {3,4,6}
                                       {3,5,6}
                                       {4,5,6}

Mathematica

fasmax[y_]:=Complement[y, Union@@(Most[Subsets[#]]&)/@y];
Table[Length[fasmax[Select[Subsets[Range[n]], UnsameQ@@Plus@@@Subsets[#]&]]], {n, 0, 10}]

Prog

(PARI)
a(n)={
  my(ismaxl(w)=for(k=1, n, if(!bitand(w, w<<k), return(0))); 1);
  my(recurse(k, b, w)=
      if(k > n, ismaxl(w),
         my(s=self()(k+1, b, w));
         if(!bitand(w, w<<k), s+=self()(k+1, b+(1<<k), w + (w<<k)));
         s);
  );
  recurse(1, 0, 1);
} \\ Andrew Howroyd, Mar 23 2025

Crossrefs

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

Cf. A325860, A325864, A325866, A325867, A325877, A325878, A325879, A325880.

Sequence in context: A096572 A318540 A325879 * A110523 A145597 A143418

Adjacent sequences: A325862 A325863 A325864 * A325866 A325867 A325868

Keyword

nonn

Author

Gus Wiseman, Jun 01 2019

Extensions

a(18) onwards from Andrew Howroyd, Mar 23 2025

Status

approved