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

%I #23 Feb 25 2025 14:55:52

%S 0,0,1,2,4,8,15,27,49,90,165,301,548,998,1819,3316,6040,10986,19959,

%T 36253,65904,119986,218796,399461,729752,1333162,2434411,4441954,

%U 8097478,14746715,26830230,48773790,88605927,160900978,292140427,530487359,963610200,1751171679,3183997509

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

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

%e 3 cannot be written as a nonnegative linear combination of 2, 4, and 5, so {2,4,5} is counted under a(6).

%e The a(2) = 1 through a(6) = 15 subsets:

%e {2} {2} {2} {2} {2}

%e {3} {3} {3} {3}

%e {4} {4} {4}

%e {3,4} {5} {5}

%e {3,4} {6}

%e {3,5} {3,4}

%e {4,5} {3,5}

%e {2,4,5} {3,6}

%e {4,5}

%e {4,6}

%e {5,6}

%e {2,4,5}

%e {2,4,6}

%e {2,5,6}

%e {4,5,6}

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

%t Table[Length[Select[Subsets[Range[n]], combs[Length[#],Union[#]]=={}&]], {n,0,10}]

%o (Python)

%o from itertools import combinations

%o from sympy.utilities.iterables import partitions

%o def A367223(n):

%o c, mlist = 0, []

%o for m in range(1,n+1):

%o t = set()

%o for p in partitions(m):

%o t.add(tuple(sorted(p.keys())))

%o mlist.append([set(d) for d in t])

%o for k in range(1,n+1):

%o for w in combinations(range(1,n+1),k):

%o ws = set(w)

%o for s in mlist[k-1]:

%o if s <= ws:

%o break

%o else:

%o c += 1

%o return c # _Chai Wah Wu_, Nov 16 2023

%Y 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 sum-full sum-free comb-full comb-free

%Y -------------------------------------------

%Y partitions: A367212 A367213 A367218 A367219

%Y strict: A367214 A367215 A367220 A367221

%Y subsets: A367216 A367217 A367222 A367223*

%Y ranks: A367224 A367225 A367226 A367227

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

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

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

%Y A365046 counts combination-full subsets, differences of A364914.

%Y Triangles:

%Y A116861 counts positive linear combinations of strict partitions of k.

%Y A364916 counts linear combinations of strict partitions of k.

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

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

%K nonn,changed

%O 0,4

%A _Gus Wiseman_, Nov 14 2023

%E a(14)-a(33) from _Chai Wah Wu_, Nov 15 2023

%E a(34)-a(38) from _Max Alekseyev_, Feb 25 2025