A365377
Number of subsets of {1..n} without a subset summing to n.
Original entry on oeis.org
0, 1, 2, 3, 6, 9, 17, 26, 49, 72, 134, 201, 366, 544, 984, 1436, 2614, 3838, 6770, 10019, 17767, 25808, 45597, 66671, 116461, 169747, 295922, 428090, 750343, 1086245, 1863608, 2721509, 4705456, 6759500, 11660244, 16877655, 28879255, 41778027, 71384579, 102527811, 176151979
Offset: 0
The a(1) = 1 through a(6) = 17 subsets:
{} {} {} {} {} {}
{1} {1} {1} {1} {1}
{2} {2} {2} {2}
{3} {3} {3}
{1,2} {4} {4}
{2,3} {1,2} {5}
{1,3} {1,2}
{2,4} {1,3}
{3,4} {1,4}
{2,3}
{2,5}
{3,4}
{3,5}
{4,5}
{1,3,4}
{2,3,5}
{3,4,5}
The complement w/ re-usable parts is
A365073.
The complement is counted by
A365376.
The version with re-usable parts is
A365380.
A000124 counts distinct possible sums of subsets of {1..n}.
A124506 appears to count combination-free subsets, differences of
A326083.
A364350 counts combination-free strict partitions, complement
A364839.
A365381 counts subsets of {1..n} with a subset summing to k.
Cf.
A007865,
A085489,
A088809,
A093971,
A103580,
A151897,
A236912,
A237113,
A237668,
A326080,
A364349,
A364534.
-
Table[Length[Select[Subsets[Range[n]], FreeQ[Total/@Subsets[#],n]&]],{n,0,10}]
-
isok(s, n) = forsubset(#s, ss, if (vecsum(vector(#ss, k, s[ss[k]])) == n, return(0))); return(1);
a(n) = my(nb=0); forsubset(n, s, if (isok(s, n), nb++)); nb; \\ Michel Marcus, Sep 09 2023
-
from itertools import combinations, chain
from sympy.utilities.iterables import partitions
def A365377(n):
if n == 0: return 0
nset = set(range(1,n+1))
s, c = [set(p) for p in partitions(n,m=n,k=n) if max(p.values(),default=1) == 1], 1
for a in chain.from_iterable(combinations(nset,m) for m in range(2,n+1)):
if sum(a) >= n:
aset = set(a)
for p in s:
if p.issubset(aset):
c += 1
break
return (1<Chai Wah Wu, Sep 09 2023
A365320
Number of pairs of distinct positive integers <= n that cannot be linearly combined with nonnegative coefficients to obtain n.
Original entry on oeis.org
0, 0, 0, 0, 0, 2, 1, 7, 5, 12, 12, 27, 14, 42, 36, 47, 47, 83, 58, 109, 80, 116, 126, 172, 111, 195, 192, 219, 202, 294, 210, 342, 286, 354, 369, 409, 324, 509, 480, 523, 452, 640, 507, 711, 622, 675, 747, 865, 654, 916, 842, 964, 922, 1124, 940, 1147, 1029
Offset: 0
The pair p = (3,6) cannot be linearly combined to obtain 8 or 10, so p is counted under a(8) and a(10), but we have 9 = 1*3 + 1*6 or 9 = 3*3 + 0*6, so p not counted under a(9).
The a(5) = 2 through a(10) = 12 pairs:
(2,4) (4,5) (2,4) (3,6) (2,4) (3,6)
(3,4) (2,6) (3,7) (2,6) (3,8)
(3,5) (5,6) (2,8) (3,9)
(3,6) (5,7) (4,6) (4,7)
(4,5) (6,7) (4,7) (4,8)
(4,6) (4,8) (4,9)
(5,6) (5,6) (6,7)
(5,7) (6,8)
(5,8) (6,9)
(6,7) (7,8)
(6,8) (7,9)
(7,8) (8,9)
The case of positive coefficients is
A365321, for all subsets
A365322.
For all subsets instead of just pairs we have
A365380, complement
A365073.
A004526 counts partitions of length 2, shift right for strict.
A364350 counts combination-free strict partitions.
-
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],{2}],combs[n,#]=={}&]],{n,0,30}]
-
from itertools import count
from sympy import divisors
def A365320(n):
a = set()
for i in range(1,n+1):
if not n%i:
a.update(tuple(sorted((i,j))) for j in range(1,n+1) if j!=i)
else:
for j in count(0,i):
if j > n:
break
k = n-j
for d in divisors(k):
if d>=i:
break
a.add((d,i))
return (n*(n-1)>>1)-len(a) # Chai Wah Wu, Sep 13 2023
A088528
Let m = number of ways of partitioning n into parts using all the parts of a subset of {1, 2, ..., n-1} whose sum of all parts of a subset is less than n; a(n) gives number of different subsets of {1, 2, ..., n-1} whose m is 0.
Original entry on oeis.org
0, 0, 1, 1, 3, 3, 6, 6, 10, 12, 17, 18, 26, 30, 40, 44, 58, 66, 84, 95, 120, 135, 166, 186, 230, 257, 314, 350, 421, 476, 561, 626, 749, 831, 986, 1095, 1276, 1424, 1666, 1849, 2138, 2388, 2741, 3042, 3522, 3879, 4441, 4928, 5617, 6222, 7084, 7802, 8852, 9800
Offset: 1
a(5)=3 because there are three different subsets, {2}, {3} & {4}; a(6)=3 because there are three different subsets, {4}, {5} & {2,3}.
From _Gus Wiseman_, Sep 10 2023: (Start)
The set {3,5} is not counted under a(8) because 1*3 + 1*5 = 8, but it is counted under a(9) and a(10), and it is not counted under a(11) because 2*3 + 1*5 = 11.
The a(3) = 1 through a(11) = 17 subsets:
{2} {3} {2} {4} {2} {3} {2} {3} {2}
{3} {5} {3} {5} {4} {4} {3}
{4} {2,3} {4} {6} {5} {6} {4}
{5} {7} {6} {7} {5}
{6} {2,5} {7} {8} {6}
{2,4} {3,4} {8} {9} {7}
{2,4} {2,5} {8}
{2,6} {2,7} {9}
{3,4} {3,5} {10}
{3,5} {3,6} {2,4}
{4,5} {2,6}
{2,3,4} {2,8}
{3,6}
{3,7}
{4,5}
{4,6}
{2,3,5}
(End)
For sets with max < n instead of sum < n we have
A365045, nonempty
A070880.
For sets with max <= n we have
A365322.
-
combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Select[Subsets[Range[n]],0Gus Wiseman, Sep 12 2023 *)
A365322
Number of subsets of {1..n} that cannot be linearly combined using positive coefficients to obtain n.
Original entry on oeis.org
0, 1, 2, 5, 11, 26, 54, 116, 238, 490, 994, 2011, 4045, 8131, 16305, 32672, 65412, 130924, 261958, 524066, 1048301, 2096826, 4193904, 8388135, 16776641, 33553759, 67108053, 134216782, 268434324, 536869595, 1073740266, 2147481835, 4294965158, 8589932129
Offset: 0
The set {1,3} has 4 = 1 + 3 so is not counted under a(4). However, 3 cannot be written as a linear combination of {1,3} using all positive coefficients, so it is counted under a(3).
The a(1) = 1 through a(4) = 11 subsets:
{} {} {} {}
{1,2} {2} {3}
{1,3} {1,4}
{2,3} {2,3}
{1,2,3} {2,4}
{3,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
The complement is counted by
A088314.
The version for strict partitions is
A088528.
For nonnegative coefficients we have
A365380.
A085489 and
A364755 count subsets without the sum of two distinct elements.
A124506 appears to count combination-free subsets, differences of
A326083.
A364350 counts combination-free strict partitions, non-strict
A364915.
A365046 counts combination-full subsets, first differences of
A364914.
-
b:= proc(n, i) option remember; `if`(n=0, {{}}, `if`(i<1, {},
{b(n, i-1)[], seq(map(x->{x[], i}, b(n-i*j, i-1))[], j=1..n/i)}))
end:
a:= n-> 2^n-nops(b(n$2)):
seq(a(n), n=0..33); # Alois P. Heinz, Sep 04 2023
-
cpu[n_,y_]:=With[{s=Table[{k,i},{k,Union[y]},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n]],cpu[n,#]=={}&]],{n,0,10}]
-
from sympy.utilities.iterables import partitions
def A365322(n): return (1<Chai Wah Wu, Sep 14 2023
A365314
Number of unordered pairs of distinct positive integers <= n that can be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
0, 0, 1, 3, 6, 8, 14, 14, 23, 24, 33, 28, 52, 36, 55, 58, 73, 53, 95, 62, 110, 94, 105, 81, 165, 105, 133, 132, 176, 112, 225, 123, 210, 174, 192, 186, 306, 157, 223, 218, 328, 180, 354, 192, 324, 315, 288, 216, 474, 260, 383, 311, 404, 254, 491, 338, 511, 360
Offset: 0
We have 19 = 4*3 + 1*7, so the pair (3,7) is counted under a(19).
The a(2) = 1 through a(7) = 14 pairs:
(1,2) (1,2) (1,2) (1,2) (1,2) (1,2)
(1,3) (1,3) (1,3) (1,3) (1,3)
(2,3) (1,4) (1,4) (1,4) (1,4)
(2,3) (1,5) (1,5) (1,5)
(2,4) (2,3) (1,6) (1,6)
(3,4) (2,5) (2,3) (1,7)
(3,5) (2,4) (2,3)
(4,5) (2,5) (2,5)
(2,6) (2,7)
(3,4) (3,4)
(3,5) (3,7)
(3,6) (4,7)
(4,6) (5,7)
(5,6) (6,7)
For all subsets instead of just pairs we have
A365073, complement
A365380.
The case of positive coefficients is
A365315, for all subsets
A088314.
A004526 counts partitions of length 2, shift right for strict.
A364350 counts combination-free strict partitions.
-
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],{2}], combs[n,#]!={}&]],{n,0,30}]
-
from itertools import count
from sympy import divisors
def A365314(n):
a = set()
for i in range(1,n+1):
if not n%i:
a.update(tuple(sorted((i,j))) for j in range(1,n+1) if j!=i)
else:
for j in count(0,i):
if j > n:
break
k = n-j
for d in divisors(k):
if d>=i:
break
a.add((d,i))
return len(a) # Chai Wah Wu, Sep 12 2023
A365378
Number of integer partitions with sum < n whose distinct parts cannot be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
0, 0, 0, 1, 1, 4, 2, 9, 5, 13, 10, 28, 7, 45, 25, 51, 32, 101, 31, 148, 50, 166, 106, 291, 47, 374, 176, 450, 179, 721, 121, 963, 285, 1080, 474, 1534, 200, 2140, 712, 2407, 599, 3539, 481, 4546, 1014, 4885
Offset: 0
The partition (5,2,2) has distinct parts {2,5} and has 11 = 3*2 + 1*5, so is not counted under a(11).
The partition (4,2,2) cannot be linearly combined to obtain 9, so is counted under a(9).
The partition (4,2,2) has distinct parts {2,4} and has 10 = 5*2 + 0*4, so is not counted under a(10).
The a(3) = 1 through a(10) = 10 partitions:
(2) (3) (2) (4) (2) (3) (2) (3)
(3) (5) (3) (5) (4) (4)
(4) (4) (6) (5) (6)
(22) (5) (7) (6) (7)
(6) (33) (7) (8)
(22) (8) (9)
(33) (22) (33)
(42) (42) (44)
(222) (44) (63)
(62) (333)
(222)
(422)
(2222)
For positive coefficients we have
A365323.
The complement is counted by
A365379.
The relatively prime case is
A365382.
A364350 counts combination-free strict partitions, non-strict
A364915.
A364839 counts combination-full strict partitions, non-strict
A364913.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Join@@IntegerPartitions/@Range[n-1],combs[n,Union[#]]=={}&]],{n,0,10}]
-
from sympy.utilities.iterables import partitions
def A365378(n):
a = {tuple(sorted(set(p))) for p in partitions(n)}
return sum(1 for m in range(1,n) for b in partitions(m) if not any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 13 2023
A365321
Number of pairs of distinct positive integers <= n that cannot be linearly combined with positive coefficients to obtain n.
Original entry on oeis.org
0, 0, 1, 2, 4, 6, 10, 13, 18, 24, 30, 37, 46, 54, 63, 77, 85, 99, 111, 127, 141, 161, 171, 194, 210, 235, 246, 277, 293, 322, 342, 372, 389, 428, 441, 491, 504, 545, 561, 612, 635, 680, 701, 753, 773, 836, 846, 911, 932, 1000, 1017, 1082, 1103, 1176, 1193
Offset: 0
For the pair p = (2,3) we have 4 = 2*2 + 0*3, so p is not counted under A365320(4), but it is not possible to write 4 as a positive linear combination of 2 and 3, so p is counted under a(4).
The a(2) = 1 through a(7) = 13 pairs:
(1,2) (1,3) (1,4) (1,5) (1,6) (1,7)
(2,3) (2,3) (2,4) (2,3) (2,4)
(2,4) (2,5) (2,5) (2,6)
(3,4) (3,4) (2,6) (2,7)
(3,5) (3,4) (3,5)
(4,5) (3,5) (3,6)
(3,6) (3,7)
(4,5) (4,5)
(4,6) (4,6)
(5,6) (4,7)
(5,6)
(5,7)
(6,7)
For all subsets instead of just pairs we have
A365322, complement
A088314.
A004526 counts partitions of length 2, shift right for strict.
A364350 counts combination-free strict partitions.
Cf.
A070880,
A088571,
A088809,
A151897,
A326020,
A365043,
A365073,
A365311,
A365312,
A365378,
A365380.
-
combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n],{2}], combp[n,#]=={}&]],{n,0,30}]
-
from itertools import count
from sympy import divisors
def A365321(n):
a = set()
for i in range(1,n+1):
for j in count(i,i):
if j >= n:
break
for d in divisors(n-j):
if d>=i:
break
a.add((d,i))
return (n*(n-1)>>1)-len(a) # Chai Wah Wu, Sep 12 2023
A365379
Number of integer partitions with sum <= n whose distinct parts can be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
0, 1, 3, 5, 10, 14, 27, 35, 61, 83, 128, 166, 264, 327, 482, 632, 882, 1110, 1565, 1938, 2663, 3339, 4401, 5471, 7290, 8921, 11555, 14291, 18280, 22303, 28507, 34507, 43534, 52882, 65798, 79621, 98932, 118629, 146072, 175562, 214708, 256351, 312583, 371779
Offset: 0
The partition (4,2,2) cannot be linearly combined to obtain 9, so is not counted under a(9). On the other hand, the same partition (4,2,2) has distinct parts {2,4} and has 10 = 1*2 + 2*4, so is counted under a(10).
The a(1) = 1 through a(5) = 14 partitions:
(1) (1) (1) (1) (1)
(2) (3) (2) (5)
(11) (11) (4) (11)
(21) (11) (21)
(111) (21) (31)
(22) (32)
(31) (41)
(111) (111)
(211) (211)
(1111) (221)
(311)
(1111)
(2111)
(11111)
For subsets with positive coefficients we have
A088314, complement
A088528.
The case of strict partitions with positive coefficients is also
A088314.
The complement is counted by
A365378.
A364350 counts combination-free strict partitions, non-strict
A364915.
A364839 counts combination-full strict partitions, non-strict
A364913.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Join@@Array[IntegerPartitions,n],combs[n,Union[#]]!={}&]],{n,0,10}]
-
from sympy.utilities.iterables import partitions
def A365379(n):
a = {tuple(sorted(set(p))) for p in partitions(n)}
return sum(1 for m in range(1,n+1) for b in partitions(m) if any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 13 2023
A070880
Consider the 2^(n-1)-1 nonempty subsets S of {1, 2, ..., n-1}; a(n) gives number of such S for which it is impossible to partition n into parts from S such that each s in S is used at least once.
Original entry on oeis.org
0, 0, 1, 3, 10, 22, 52, 110, 234, 482, 987, 1997, 4035, 8113, 16288, 32644, 65388, 130886, 261922, 524013, 1048250, 2096752, 4193831, 8388033, 16776543, 33553621, 67107918, 134216596, 268434139, 536869354, 1073740011, 2147481510, 4294964833, 8589931699
Offset: 1
a(4)=3 because there are three different subsets S of {1,2,3} satisfying the condition: {3}, {2,3} & {1,2,3}. For the other subsets S, such as {1,2}, there is a partition of 4 which uses them all (such as 4 = 1+1+2).
From _Gus Wiseman_, Sep 10 2023: (Start)
The a(6) = 22 subsets:
{4} {2,3} {1,2,4} {1,2,3,4} {1,2,3,4,5}
{5} {2,5} {1,2,5} {1,2,3,5}
{3,4} {1,3,4} {1,2,4,5}
{3,5} {1,3,5} {1,3,4,5}
{4,5} {1,4,5} {2,3,4,5}
{2,3,4}
{2,3,5}
{2,4,5}
{3,4,5}
(End)
For sets with sum < n instead of maximum < n we have
A088528.
Allowing empty sets gives
A365045, nonnegative version apparently
A124506.
Without re-usable parts we have
A365377(n) - 1.
For nonnegative (instead of positive) coefficients we have
A365380(n) - 1.
A364350 counts combination-free strict partitions, complement
A364913.
-
combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s], Total[Times@@@#]==n&]];
Table[Length[Select[Rest[Subsets[Range[n-1]]], combp[n,#]=={}&]],{n,7}] (* Gus Wiseman, Sep 10 2023 *)
-
from sympy.utilities.iterables import partitions
def A070880(n): return (1<Chai Wah Wu, Sep 10 2023
A365315
Number of unordered pairs of distinct positive integers <= n that can be linearly combined using positive coefficients to obtain n.
Original entry on oeis.org
0, 0, 0, 1, 2, 4, 5, 8, 10, 12, 15, 18, 20, 24, 28, 28, 35, 37, 42, 44, 49, 49, 60, 59, 66, 65, 79, 74, 85, 84, 93, 93, 107, 100, 120, 104, 126, 121, 142, 129, 145, 140, 160, 150, 173, 154, 189, 170, 196, 176, 208, 193, 223, 202, 238, 203, 241, 227, 267, 235
Offset: 0
We have 19 = 4*3 + 1*7, so the pair (3,7) is counted under a(19).
For the pair p = (2,3), we have 4 = 2*2 + 0*3, so p is counted under A365314(4), but it is not possible to write 4 as a positive linear combination of 2 and 3, so p is not counted under a(4).
The a(3) = 1 through a(10) = 15 pairs:
(1,2) (1,2) (1,2) (1,2) (1,2) (1,2) (1,2) (1,2)
(1,3) (1,3) (1,3) (1,3) (1,3) (1,3) (1,3)
(1,4) (1,4) (1,4) (1,4) (1,4) (1,4)
(2,3) (1,5) (1,5) (1,5) (1,5) (1,5)
(2,4) (1,6) (1,6) (1,6) (1,6)
(2,3) (1,7) (1,7) (1,7)
(2,5) (2,3) (1,8) (1,8)
(3,4) (2,4) (2,3) (1,9)
(2,6) (2,5) (2,3)
(3,5) (2,7) (2,4)
(3,6) (2,6)
(4,5) (2,8)
(3,4)
(3,7)
(4,6)
For all subsets instead of just pairs we have
A088314, complement
A365322.
The case of nonnegative coefficients is
A365314, for all subsets
A365073.
A004526 counts partitions of length 2, shift right for strict.
A364350 counts combination-free strict partitions.
Cf.
A070880,
A088809,
A326020,
A364534,
A365043,
A365311,
A365312,
A365378,
A365379,
A365380,
A365383.
-
combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Subsets[Range[n],{2}],combp[n,#]!={}&]],{n,0,30}]
-
from itertools import count
from sympy import divisors
def A365315(n):
a = set()
for i in range(1,n+1):
for j in count(i,i):
if j >= n:
break
for d in divisors(n-j):
if d>=i:
break
a.add((d,i))
return len(a) # Chai Wah Wu, Sep 13 2023
Comments