cp's OEIS Frontend

A367222 Number of subsets of {1..n} whose cardinality can be written as a nonnegative linear combination of the elements.

%I A367222 #29 Feb 25 2025 14:55:48
%S A367222 1,2,3,6,12,24,49,101,207,422,859,1747,3548,7194,14565,29452,59496,
%T A367222 120086,242185,488035,982672,1977166,3975508,7989147,16047464,
%U A367222 32221270,64674453,129775774,260337978,522124197,1046911594,2098709858,4206361369,8429033614,16887728757,33829251009,67755866536,135687781793,271693909435
%N A367222 Number of subsets of {1..n} whose cardinality can be written as a nonnegative linear combination of the elements.
%F A367222 a(n) = 2^n - A367223(n).
%e A367222 The set {1,2,4} has 3 = (2)+(1) or 3 = (1+1+1) so is counted under a(4).
%e A367222 The a(0) = 1 through a(4) = 12 subsets:
%e A367222   {}  {}   {}     {}       {}
%e A367222       {1}  {1}    {1}      {1}
%e A367222            {1,2}  {1,2}    {1,2}
%e A367222                   {1,3}    {1,3}
%e A367222                   {2,3}    {1,4}
%e A367222                   {1,2,3}  {2,3}
%e A367222                            {2,4}
%e A367222                            {1,2,3}
%e A367222                            {1,2,4}
%e A367222                            {1,3,4}
%e A367222                            {2,3,4}
%e A367222                            {1,2,3,4}
%t A367222 combs[n_,y_]:=With[{s=Table[{k,i},{k,y}, {i,0,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
%t A367222 Table[Length[Select[Subsets[Range[n]], combs[Length[#], Union[#]]!={}&]], {n,0,10}]
%o A367222 (Python)
%o A367222 from itertools import combinations
%o A367222 from sympy.utilities.iterables import partitions
%o A367222 def A367222(n):
%o A367222     c, mlist = 1, []
%o A367222     for m in range(1,n+1):
%o A367222         t = set()
%o A367222         for p in partitions(m):
%o A367222             t.add(tuple(sorted(p.keys())))
%o A367222         mlist.append([set(d) for d in t])
%o A367222     for k in range(1,n+1):
%o A367222         for w in combinations(range(1,n+1),k):
%o A367222             ws = set(w)
%o A367222             for s in mlist[k-1]:
%o A367222                 if s <= ws:
%o A367222                     c += 1
%o A367222                     break
%o A367222     return c # _Chai Wah Wu_, Nov 16 2023
%Y A367222 The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
%Y A367222                sum-full   sum-free   comb-full  comb-free
%Y A367222               -------------------------------------------
%Y A367222   partitions:  A367212    A367213    A367218    A367219
%Y A367222   strict:      A367214    A367215    A367220    A367221
%Y A367222   subsets:     A367216    A367217    A367222*   A367223
%Y A367222   ranks:       A367224    A367225    A367226    A367227
%Y A367222 A002865 counts partitions whose length is a part, complement A229816.
%Y A367222 A007865/A085489/A151897 count certain types of sum-free subsets.
%Y A367222 A088809/A093971/A364534 count certain types of sum-full subsets.
%Y A367222 A124506 appears to count combination-free subsets, differences of A326083.
%Y A367222 A326020 counts complete subsets.
%Y A367222 A365046 counts combination-full subsets, differences of A364914.
%Y A367222 Triangles:
%Y A367222 A008284 counts partitions by length, strict A008289.
%Y A367222 A365381 counts sets with a subset summing to k, without A366320.
%Y A367222 A365541 counts subsets containing two distinct elements summing to k.
%Y A367222 Cf. A068911, A088314, A103580, A116861, A326080, A364350, A365073, A365311, A365376, A365380, A365544.
%K A367222 nonn
%O A367222 0,2
%A A367222 _Gus Wiseman_, Nov 14 2023
%E A367222 a(13)-a(33) from _Chai Wah Wu_, Nov 15 2023
%E A367222 a(34)-a(38) from _Max Alekseyev_, Feb 25 2025