cp's OEIS Frontend

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

%I A367223 #23 Feb 25 2025 14:55:52
%S A367223 0,0,1,2,4,8,15,27,49,90,165,301,548,998,1819,3316,6040,10986,19959,
%T A367223 36253,65904,119986,218796,399461,729752,1333162,2434411,4441954,
%U A367223 8097478,14746715,26830230,48773790,88605927,160900978,292140427,530487359,963610200,1751171679,3183997509
%N A367223 Number of subsets of {1..n} whose cardinality cannot be written as a nonnegative linear combination of the elements.
%F A367223 a(n) = 2^n - A367222(n).
%e A367223 3 cannot be written as a nonnegative linear combination of 2, 4, and 5, so {2,4,5} is counted under a(6).
%e A367223 The a(2) = 1 through a(6) = 15 subsets:
%e A367223   {2}  {2}  {2}    {2}      {2}
%e A367223        {3}  {3}    {3}      {3}
%e A367223             {4}    {4}      {4}
%e A367223             {3,4}  {5}      {5}
%e A367223                    {3,4}    {6}
%e A367223                    {3,5}    {3,4}
%e A367223                    {4,5}    {3,5}
%e A367223                    {2,4,5}  {3,6}
%e A367223                             {4,5}
%e A367223                             {4,6}
%e A367223                             {5,6}
%e A367223                             {2,4,5}
%e A367223                             {2,4,6}
%e A367223                             {2,5,6}
%e A367223                             {4,5,6}
%t A367223 combs[n_,y_]:=With[{s=Table[{k,i},{k,y}, {i,0,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
%t A367223 Table[Length[Select[Subsets[Range[n]], combs[Length[#],Union[#]]=={}&]], {n,0,10}]
%o A367223 (Python)
%o A367223 from itertools import combinations
%o A367223 from sympy.utilities.iterables import partitions
%o A367223 def A367223(n):
%o A367223     c, mlist = 0, []
%o A367223     for m in range(1,n+1):
%o A367223         t = set()
%o A367223         for p in partitions(m):
%o A367223             t.add(tuple(sorted(p.keys())))
%o A367223         mlist.append([set(d) for d in t])
%o A367223     for k in range(1,n+1):
%o A367223         for w in combinations(range(1,n+1),k):
%o A367223             ws = set(w)
%o A367223             for s in mlist[k-1]:
%o A367223                 if s <= ws:
%o A367223                     break
%o A367223             else:
%o A367223                 c += 1
%o A367223     return c # _Chai Wah Wu_, Nov 16 2023
%Y A367223 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 A367223                sum-full   sum-free   comb-full  comb-free
%Y A367223               -------------------------------------------
%Y A367223   partitions:  A367212    A367213    A367218    A367219
%Y A367223   strict:      A367214    A367215    A367220    A367221
%Y A367223   subsets:     A367216    A367217    A367222    A367223*
%Y A367223   ranks:       A367224    A367225    A367226    A367227
%Y A367223 A007865/A085489/A151897 count certain types of sum-free subsets.
%Y A367223 A088809/A093971/A364534 count certain types of sum-full subsets.
%Y A367223 A124506 appears to count combination-free subsets, differences of A326083.
%Y A367223 A365046 counts combination-full subsets, differences of A364914.
%Y A367223 Triangles:
%Y A367223 A116861 counts positive linear combinations of strict partitions of k.
%Y A367223 A364916 counts linear combinations of strict partitions of k.
%Y A367223 A366320 counts subsets without a subset summing to k, with A365381.
%Y A367223 Cf. A068911, A088314, A103580, A237667, A326020, A326080, A364350, A365073, A365312, A365377, A365380.
%K A367223 nonn
%O A367223 0,4
%A A367223 _Gus Wiseman_, Nov 14 2023
%E A367223 a(14)-a(33) from _Chai Wah Wu_, Nov 15 2023
%E A367223 a(34)-a(38) from _Max Alekseyev_, Feb 25 2025