cp's OEIS Frontend

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

%I A325867 #22 Jan 13 2022 18:44:07
%S A325867 1,1,2,2,4,8,10,12,17,34,45,77,99,136,166,200,238,328,402,660,674,
%T A325867 1166,1331,1966,2335,3286,3527,4762,5383,6900,7543,9087,10149,12239,
%U A325867 13569,16452,17867,22869,23977,33881,33820,43423,48090,68683,67347,95176,97917,131666,136205
%N A325867 Number of maximal subsets of {1..n} containing n such that every subset has a different sum.
%C A325867 These are maximal strict knapsack partitions (A275972, A326015) organized by maximum rather than sum.
%H A325867 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 A325867 The a(1) = 1 through a(8) = 12 subsets:
%e A325867   {1}  {1,2}  {1,3}  {1,2,4}  {1,2,5}  {1,2,6}  {1,2,7}    {1,3,8}
%e A325867               {2,3}  {2,3,4}  {1,3,5}  {1,3,6}  {1,3,7}    {1,5,8}
%e A325867                               {2,4,5}  {1,4,6}  {1,4,7}    {5,7,8}
%e A325867                               {3,4,5}  {2,3,6}  {1,5,7}    {1,2,4,8}
%e A325867                                        {2,5,6}  {2,3,7}    {1,4,6,8}
%e A325867                                        {3,4,6}  {2,4,7}    {2,3,4,8}
%e A325867                                        {3,5,6}  {2,6,7}    {2,4,5,8}
%e A325867                                        {4,5,6}  {4,5,7}    {2,4,7,8}
%e A325867                                                 {4,6,7}    {3,4,6,8}
%e A325867                                                 {3,5,6,7}  {3,6,7,8}
%e A325867                                                            {4,5,6,8}
%e A325867                                                            {4,6,7,8}
%t A325867 fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&)/@y];
%t A325867 Table[Length[fasmax[Select[Subsets[Range[n]],MemberQ[#,n]&&UnsameQ@@Plus@@@Subsets[#]&]]],{n,15}]
%o A325867 (Python)
%o A325867 def f(p0, n, m, cm):
%o A325867     full, t, p = True, 0, p0
%o A325867     while p<n:
%o A325867         sm = m<<p
%o A325867         if (m & sm) == 0:
%o A325867             t += f(p+1, n, m|sm, cm|(1<<p))
%o A325867             full=False
%o A325867         p+=1
%o A325867     if full:
%o A325867         for k in range(1, p0):
%o A325867             if ((cm>>k)&1)==0 and ((m<<k)&m)==0:
%o A325867                 full=False
%o A325867                 break
%o A325867     return 1 if full else t
%o A325867 def a325867(n):
%o A325867     return f(1, n, (1<<n)+1, 0)
%o A325867 # _Bert Dobbelaere_, Mar 07 2021
%Y A325867 Cf. A002033, A108917, A143823, A143824, A196723, A275972.
%Y A325867 Cf. A325860, A325861, A325864, A325865, A325866, A325867, A325880.
%K A325867 nonn
%O A325867 1,3
%A A325867 _Gus Wiseman_, Jun 01 2019
%E A325867 More terms from _Bert Dobbelaere_, Mar 07 2021