|
| |
|
|
A367223
|
|
Number of subsets of {1..n} whose cardinality cannot be written as a nonnegative linear combination of the elements.
|
|
24
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
The complement is counted by A367222.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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}
|
|
|
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}]
|
|
|
PROG
|
(Python)
from itertools import combinations
from sympy.utilities.iterables import partitions
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
|
|
|
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
-------------------------------------------
A124506 appears to count combination-free subsets, differences of A326083.
Triangles:
A116861 counts positive linear combinations of strict partitions of k.
A364916 counts linear combinations of strict partitions of k.
Cf. A068911, A088314, A103580, A237667, A326020, A326080, A364350, A365073, A365312, A365377, A365380.
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
