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
A365045
Number of subsets of {1..n} containing n such that no element can be written as a positive linear combination of the others.
Original entry on oeis.org
0, 1, 1, 2, 4, 11, 23, 53, 111, 235, 483, 988, 1998, 4036, 8114, 16289, 32645, 65389, 130887, 261923, 524014, 1048251, 2096753, 4193832, 8388034, 16776544, 33553622, 67107919, 134216597, 268434140, 536869355, 1073740012, 2147481511, 4294964834, 8589931700
Offset: 0
The subset {3,4,10} has 10 = 2*3 + 1*4 so is not counted under a(10).
The a(0) = 0 through a(5) = 11 subsets:
. {1} {2} {3} {4} {5}
{2,3} {3,4} {2,5}
{2,3,4} {3,5}
{1,2,3,4} {4,5}
{2,4,5}
{3,4,5}
{1,2,3,5}
{1,2,4,5}
{1,3,4,5}
{2,3,4,5}
{1,2,3,4,5}
Without re-usable parts we have
A365071, first differences of
A151897.
A085489 and
A364755 count subsets w/o the sum of two distinct elements.
A088809 and
A364756 count subsets with the sum of two distinct elements.
A364350 counts combination-free strict partitions, complement
A364839.
A364913 counts combination-full partitions.
-
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]],MemberQ[#,n]&&And@@Table[combp[#[[k]],Union[Delete[#,k]]]=={},{k,Length[#]}]&]],{n,0,10}]
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
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
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
A365006
Number of strict integer partitions of n such that no part can be written as a (strictly) positive linear combination of the others.
Original entry on oeis.org
1, 1, 1, 1, 1, 2, 1, 3, 2, 4, 4, 8, 4, 11, 9, 16, 14, 25, 20, 37, 31, 49, 47, 73, 64, 101, 96, 135, 133, 190, 181, 256, 253, 336, 342, 453, 452, 596, 609, 771, 803, 1014, 1041, 1309, 1362, 1674, 1760, 2151, 2249, 2736, 2884, 3449, 3661, 4366, 4615, 5486, 5825
Offset: 0
The a(8) = 2 through a(13) = 11 partitions:
(8) (9) (10) (11) (12) (13)
(5,3) (5,4) (6,4) (6,5) (7,5) (7,6)
(7,2) (7,3) (7,4) (5,4,3) (8,5)
(4,3,2) (4,3,2,1) (8,3) (5,4,2,1) (9,4)
(9,2) (10,3)
(5,4,2) (11,2)
(6,3,2) (6,4,3)
(5,3,2,1) (6,5,2)
(7,4,2)
(5,4,3,1)
(6,4,2,1)
The nonnegative version for subsets appears to be
A124506.
For subsets instead of partitions we have
A365044, complement
A365043.
A364912 counts linear combinations of partitions of k.
-
combp[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,1,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&And@@Table[combp[#[[k]],Delete[#,k]]=={},{k,Length[#]}]&]],{n,0,30}]
-
from sympy.utilities.iterables import partitions
def A365006(n):
if n <= 1: return 1
alist = [set(tuple(sorted(set(p))) for p in partitions(i)) for i in range(n)]
c = 1
for p in partitions(n,k=n-1):
if max(p.values()) == 1:
s = set(p)
for q in s:
if tuple(sorted(s-{q})) in alist[q]:
break
else:
c += 1
return c # Chai Wah Wu, Sep 20 2023
A365044
Number of subsets of {1..n} whose greatest element cannot be written as a (strictly) positive linear combination of the others.
Original entry on oeis.org
1, 2, 3, 5, 9, 20, 43, 96, 207, 442, 925, 1913, 3911, 7947, 16061, 32350, 64995, 130384, 261271, 523194, 1047208, 2095459, 4192212, 8386044, 16774078, 33550622, 67104244, 134212163, 268428760, 536862900, 1073732255, 2147472267, 4294953778, 8589918612, 17179850312
Offset: 0
The subset S = {3,5,6,8} has 6 = 2*3 + 0*5 + 0*8 and 8 = 1*3 + 1*5 + 0*6 but neither of these is strictly positive, so S is counted under a(8).
The a(0) = 1 through a(5) = 20 subsets:
{} {} {} {} {} {}
{1} {1} {1} {1} {1}
{2} {2} {2} {2}
{3} {3} {3}
{2,3} {4} {4}
{2,3} {5}
{3,4} {2,3}
{2,3,4} {2,5}
{1,2,3,4} {3,4}
{3,5}
{4,5}
{2,3,4}
{2,4,5}
{3,4,5}
{1,2,3,4}
{1,2,3,5}
{1,2,4,5}
{1,3,4,5}
{2,3,4,5}
{1,2,3,4,5}
A085489 and
A364755 count subsets w/o the sum of two distinct elements.
A088809 and
A364756 count subsets with the sum of two distinct elements.
A364350 counts combination-free strict partitions, complement
A364839.
A364913 counts combination-full partitions.
Cf.
A006951,
A237113,
A237668,
A308546,
A324736,
A326020,
A326080,
A364272,
A364349,
A364534,
A365069.
-
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]],And@@Table[combp[Last[#],Union[Most[#]]]=={},{k,Length[#]}]&]],{n,0,10}]
-
from itertools import combinations
from sympy.utilities.iterables import partitions
def A365044(n):
mlist = tuple({tuple(sorted(p.keys())) for p in partitions(m,k=m-1)} for m in range(1,n+1))
return n+1+sum(1 for k in range(2,n+1) for w in combinations(range(1,n+1),k) if w[:-1] not in mlist[w[-1]-1]) # Chai Wah Wu, Nov 20 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
A365042
Number of subsets of {1..n} containing n such that some element can be written as a positive linear combination of the others.
Original entry on oeis.org
0, 0, 1, 2, 4, 5, 9, 11, 17, 21, 29, 36, 50, 60, 78, 95, 123, 147, 185, 221, 274, 325, 399, 472, 574, 672, 810, 945, 1131, 1316, 1557, 1812, 2137, 2462, 2892, 3322, 3881, 4460, 5176, 5916, 6846, 7817, 8993, 10250, 11765, 13333, 15280, 17308, 19731, 22306
Offset: 0
The subset {3,4,10} has 10 = 2*3 + 1*4 so is counted under a(10).
The a(0) = 0 through a(7) = 11 subsets:
. . {1,2} {1,3} {1,4} {1,5} {1,6} {1,7}
{1,2,3} {2,4} {1,2,5} {2,6} {1,2,7}
{1,2,4} {1,3,5} {3,6} {1,3,7}
{1,3,4} {1,4,5} {1,2,6} {1,4,7}
{2,3,5} {1,3,6} {1,5,7}
{1,4,6} {1,6,7}
{1,5,6} {2,3,7}
{2,4,6} {2,5,7}
{1,2,3,6} {3,4,7}
{1,2,3,7}
{1,2,4,7}
Without re-usable parts we have
A365069, first differences of
A364534.
A085489 and
A364755 count subsets with no sum of two distinct elements.
A088314 counts sets that can be linearly combined to obtain n.
A088809 and
A364756 count subsets with some sum of two distinct elements.
A364350 counts combination-free strict partitions, complement
A364839.
A364913 counts combination-full partitions.
-
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]],MemberQ[#,n]&&Or@@Table[combp[#[[k]],Union[Delete[#,k]]]!={},{k,Length[#]}]&]],{n,0,10}]
Comments