A325878 Number of maximal subsets of {1..n} such that every orderless pair of distinct elements has a different sum.

1, 1, 1, 1, 4, 5, 8, 22, 40, 56, 78, 124, 222, 390, 616, 892, 1220, 1620, 2182, 3042, 4392, 6364, 9054, 12608, 16980, 22244, 28482, 36208, 45864, 58692, 75804, 98440, 128694, 168250, 218558, 281210, 357594, 449402, 560034, 693332, 853546, 1050118, 1293458, 1596144, 1975394

Offset

0,5

Links

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

Example

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

Mathematica

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

Prog

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

Crossrefs

The subset case is A196723.

The integer partition case is A325857.

The strict integer partition case is A325877.

Heinz numbers of the counterexamples are given by A325991.

Cf. A002033, A108917, A143823, A143824, A276024.

Cf. A325858, A325859, A325864, A325865, A325867, A325879, A325880, A382398.

Sequence in context: A275929 A240794 A171938 * A352396 A072808 A104884

Adjacent sequences: A325875 A325876 A325877 * A325879 A325880 A325881

Keyword

nonn

Author

Gus Wiseman, Jun 02 2019

Extensions

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

Status

approved