A365376
Number of subsets of {1..n} with a subset summing to n.
Original entry on oeis.org
1, 1, 2, 5, 10, 23, 47, 102, 207, 440, 890, 1847, 3730, 7648, 15400, 31332, 62922, 127234, 255374, 514269, 1030809, 2071344, 4148707, 8321937, 16660755, 33384685, 66812942, 133789638, 267685113, 535784667, 1071878216, 2144762139, 4290261840, 8583175092, 17168208940, 34342860713
Offset: 0
The a(1) = 1 through a(4) = 10 sets:
{1} {2} {3} {4}
{1,2} {1,2} {1,3}
{1,3} {1,4}
{2,3} {2,4}
{1,2,3} {3,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
The case containing n is counted by
A131577.
The version with re-usable parts is
A365073.
The complement is counted by
A365377.
The complement w/ 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.
-
Table[Length[Select[Subsets[Range[n]],MemberQ[Total/@Subsets[#],n]&]],{n,0,10}]
-
isok(s, n) = forsubset(#s, ss, if (vecsum(vector(#ss, k, s[ss[k]])) == n, 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 A365376(n):
if n == 0: return 1
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 c # Chai Wah Wu, Sep 09 2023
A366320
Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} without a subset summing to k.
Original entry on oeis.org
1, 2, 2, 3, 4, 4, 3, 6, 6, 7, 8, 8, 6, 6, 9, 11, 11, 14, 14, 15, 16, 16, 12, 12, 9, 17, 17, 20, 20, 24, 27, 27, 30, 30, 31, 32, 32, 24, 24, 18, 17, 26, 31, 29, 35, 36, 43, 47, 50, 51, 56, 59, 59, 62, 62, 63
Offset: 1
Triangle begins:
1
2 2 3
4 4 3 6 6 7
8 8 6 6 9 11 11 14 14 15
16 16 12 12 9 17 17 20 20 24 27 27 30 30 31
32 32 24 24 18 17 26 31 29 35 36 43 47 50 51 56 59 59 62 62 63
Row n = 3 counts the following subsets:
{} {} {} {} {} {}
{2} {1} {1} {1} {1} {1}
{3} {3} {2} {2} {2} {2}
{2,3} {1,3} {3} {3} {3}
{1,2} {1,2} {1,2}
{2,3} {1,3} {1,3}
{2,3}
The complement is counted by
A365381.
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
-
Table[Length[Select[Subsets[Range[n]],FreeQ[Total/@Subsets[#],k]&]],{n,8},{k,n*(n+1)/2}]
A365312
Number of strict integer partitions with sum <= n that cannot be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
0, 0, 0, 1, 1, 3, 2, 6, 4, 8, 7, 16, 6, 24, 17, 24, 20, 46, 22, 62, 31, 63, 57, 106, 35, 122, 90, 137, 88, 212, 74, 262, 134, 267, 206, 345, 121, 476, 294, 484, 232, 698, 242, 837, 389, 763, 571, 1185, 318, 1327, 634, 1392, 727, 1927, 640, 2056, 827, 2233, 1328
Offset: 0
The strict partition (7,3,2) has 19 = 1*7 + 2*3 + 3*2 so is not counted under a(19).
The strict partition (9,6,3) cannot be linearly combined to obtain 19, so is counted under a(19).
The a(0) = 0 through a(11) = 16 strict partitions:
. . . (2) (3) (2) (4) (2) (3) (2) (3) (2)
(3) (5) (3) (5) (4) (4) (3)
(4) (4) (6) (5) (6) (4)
(5) (7) (6) (7) (5)
(6) (7) (8) (6)
(4,2) (8) (9) (7)
(4,2) (6,3) (8)
(6,2) (9)
(10)
(4,2)
(5,4)
(6,2)
(6,3)
(6,4)
(7,3)
(8,2)
The complement for positive coefficients is counted by
A088314.
For positive coefficients we have
A088528.
The complement is counted by
A365311.
A364350 counts combination-free strict partitions, non-strict
A364915.
A364839 counts combination-full strict partitions, non-strict
A364913.
Cf.
A093971,
A237113,
A237668,
A326080,
A363225,
A364272,
A364534,
A364914,
A365043,
A365314,
A365320.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Select[Join@@Array[IntegerPartitions,n], UnsameQ@@#&],combs[n,#]=={}&]],{n,0,10}]
-
from math import isqrt
from sympy.utilities.iterables import partitions
def A365312(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,m=isqrt(1+(n<<3))>>1) if max(b.values()) == 1 and not any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 13 2023
A365311
Number of strict integer partitions with sum <= n that can be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
0, 1, 2, 3, 5, 6, 11, 12, 20, 24, 35, 38, 63, 63, 92, 112, 148, 160, 230, 244, 339, 383, 478, 533, 726, 781, 978, 1123, 1394, 1526, 1960, 2112, 2630, 2945, 3518, 3964, 4856, 5261, 6307, 7099, 8464, 9258, 11140, 12155, 14419, 16093, 18589, 20565, 24342, 26597, 30948
Offset: 0
The strict partition (6,3) cannot be linearly combined to obtain 10, so is not counted under a(10).
The strict partition (4,2) has 6 = 1*4 + 1*2 so is counted under a(6), but (4,2) cannot be linearly combined to obtain 7 so is not counted under a(7).
The a(1) = 1 through a(7) = 12 strict partitions:
(1) (1) (1) (1) (1) (1) (1)
(2) (3) (2) (5) (2) (7)
(2,1) (4) (2,1) (3) (2,1)
(2,1) (3,1) (6) (3,1)
(3,1) (3,2) (2,1) (3,2)
(4,1) (3,1) (4,1)
(3,2) (4,3)
(4,1) (5,1)
(4,2) (5,2)
(5,1) (6,1)
(3,2,1) (3,2,1)
(4,2,1)
For positive coefficients we have
A088314.
The positive complement is counted by
A088528.
The version for subsets is
A365073.
The complement is counted by
A365312.
For non-strict partitions we have
A365379.
A364350 counts combination-free strict partitions, non-strict
A364915.
A364839 counts combination-full strict partitions, non-strict
A364913.
Cf.
A093971,
A237113,
A237668,
A326080,
A363225,
A364272,
A364534,
A364914,
A365043,
A365314,
A365320.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[Select[Join@@Array[IntegerPartitions,n],UnsameQ@@#&],combs[n,#]!={}&]],{n,10}]
-
from math import isqrt
from sympy.utilities.iterables import partitions
def A365311(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,m=isqrt(1+(n<<3))>>1) if max(b.values()) == 1 and any(set(d).issubset(set(b)) for d in a)) # Chai Wah Wu, Sep 13 2023
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
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
Comments