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

0, 0, 1, 2, 4, 8, 15, 27, 49, 90, 165, 301, 548, 998, 1819, 3316, 6040, 10986, 19959, 36253, 65904, 119986, 218796, 399461, 729752, 1333162, 2434411, 4441954, 8097478, 14746715, 26830230, 48773790, 88605927, 160900978, 292140427, 530487359, 963610200, 1751171679, 3183997509

Offset: 0

Author

Gus Wiseman, Nov 14 2023

Keywords

• nonn

Examples

			3 cannot be written as a nonnegative linear combination of 2, 4, and 5, so {2,4,5} is counted under a(6).
The a(2) = 1 through a(6) = 15 subsets:
  {2}  {2}  {2}    {2}      {2}
       {3}  {3}    {3}      {3}
            {4}    {4}      {4}
            {3,4}  {5}      {5}
                   {3,4}    {6}
                   {3,5}    {3,4}
                   {4,5}    {3,5}
                   {2,4,5}  {3,6}
                            {4,5}
                            {4,6}
                            {5,6}
                            {2,4,5}
                            {2,4,6}
                            {2,5,6}
                            {4,5,6}
		

Crossrefs

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.

sum-full sum-free comb-full comb-free

-------------------------------------------

partitions: A367212 A367213 A367218 A367219

strict: A367214 A367215 A367220 A367221

subsets: A367216 A367217 A367222 A367223*

ranks: A367224 A367225 A367226 A367227

A007865/A085489/A151897 count certain types of sum-free subsets.

A088809/A093971/A364534 count certain types of sum-full subsets.

A124506 appears to count combination-free subsets, differences of A326083.

A365046 counts combination-full subsets, differences of A364914.

Triangles:

A116861 counts positive linear combinations of strict partitions of k.

A364916 counts linear combinations of strict partitions of k.

A366320 counts subsets without a subset summing to k, with A365381.

Cf. A068911, A088314, A103580, A237667, A326020, A326080, A364350, A365073, A365312, A365377, A365380.

Programs

Mathematica

combs[n_,y_]:=With[{s=Table[{k,i},{k,y}, {i,0,Floor[n/k]}]}, Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]], combs[Length[#],Union[#]]=={}&]], {n,0,10}]

Python

from itertools import combinations
from sympy.utilities.iterables import partitions
def A367223(n):
    c, mlist = 0, []
    for m in range(1,n+1):
        t = set()
        for p in partitions(m):
            t.add(tuple(sorted(p.keys())))
        mlist.append([set(d) for d in t])
    for k in range(1,n+1):
        for w in combinations(range(1,n+1),k):
            ws = set(w)
            for s in mlist[k-1]:
                if s <= ws:
                    break
            else:
                c += 1
    return c # Chai Wah Wu, Nov 16 2023

Formula

a(n) = 2^n - A367222(n).

Extensions

a(14)-a(33) from Chai Wah Wu, Nov 15 2023

a(34)-a(38) from Max Alekseyev, Feb 25 2025