A364913
Number of integer partitions of n having a part that can be written as a nonnegative linear combination of the other (possibly equal) parts.
Original entry on oeis.org
0, 0, 1, 2, 4, 5, 10, 12, 20, 27, 39, 51, 74, 95, 130, 169, 225, 288, 378, 479, 617, 778, 990, 1239, 1560, 1938, 2419, 2986, 3696, 4538, 5575, 6810, 8319, 10102, 12274, 14834, 17932, 21587, 25963, 31120, 37275, 44513, 53097, 63181, 75092, 89030, 105460, 124647
Offset: 0
The a(0) = 0 through a(7) = 12 partitions:
. . (11) (21) (22) (41) (33) (61)
(111) (31) (221) (42) (322)
(211) (311) (51) (331)
(1111) (2111) (222) (421)
(11111) (321) (511)
(411) (2221)
(2211) (3211)
(3111) (4111)
(21111) (22111)
(111111) (31111)
(211111)
(1111111)
The partition (5,4,3) has no part that can be written as a nonnegative linear combination of the others, so is not counted under a(12).
The partition (6,4,3,2) has 6 = 4+2, or 6 = 3+3, or 6 = 2+2+2, or 4 = 2+2, so is counted under a(15).
The complement in strict partitions is
A364350.
For subsets instead of partitions we have
A364914, complement
A326083.
A365006 = no strict partitions w/ pos linear combination.
-
combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[IntegerPartitions[n],!UnsameQ@@#||Or@@Table[combs[#[[k]],Delete[#,k]]!={},{k,Length[#]}]&]],{n,0,15}]
A365073
Number of subsets of {1..n} that can be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
1, 1, 3, 6, 14, 26, 60, 112, 244, 480, 992, 1944, 4048, 7936, 16176, 32320, 65088, 129504, 261248, 520448, 1046208, 2090240, 4186624, 8365696, 16766464, 33503744, 67064064, 134113280, 268347392, 536546816, 1073575936, 2146703360, 4294425600, 8588476416, 17178349568
Offset: 0
The subset {2,3,6} has 7 = 2*2 + 1*3 + 0*6 so is counted under a(7).
The a(1) = 1 through a(4) = 14 subsets:
{1} {1} {1} {1}
{2} {3} {2}
{1,2} {1,2} {4}
{1,3} {1,2}
{2,3} {1,3}
{1,2,3} {1,4}
{2,3}
{2,4}
{3,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
The case of positive coefficients is
A088314.
The case of subsets containing n is
A131577.
The positive complement is counted by
A365322.
The complement is counted by
A365380.
The case of subsets without n is
A365542.
A364350 counts combination-free strict partitions.
Cf.
A007865,
A088809,
A093971,
A151897,
A237668,
A308546,
A326020,
A364534,
A364839,
A365043,
A365381.
-
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[n,#]!={}&]],{n,0,5}]
-
a(n)={
my(comb(k,b)=while(b>>k, b=bitor(b, b>>k); k*=2); b);
my(recurse(k,b)=
if(bittest(b,0), 2^(n+1-k),
if(2*k>n, 2^(n+1-k) - 2^sum(j=k, n, !bittest(b,j)),
self()(k+1, b) + self()(k+1, comb(k,b)) )));
recurse(1, 1<Andrew Howroyd, Sep 04 2023
A365541
Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} containing two distinct elements summing to k = 3..2n-1.
Original entry on oeis.org
1, 2, 2, 2, 4, 4, 7, 4, 4, 8, 8, 14, 14, 14, 8, 8, 16, 16, 28, 28, 37, 28, 28, 16, 16, 32, 32, 56, 56, 74, 74, 74, 56, 56, 32, 32, 64, 64, 112, 112, 148, 148, 175, 148, 148, 112, 112, 64, 64, 128, 128, 224, 224, 296, 296, 350, 350, 350, 296, 296, 224, 224, 128, 128
Offset: 2
Triangle begins:
1
2 2 2
4 4 7 4 4
8 8 14 14 14 8 8
16 16 28 28 37 28 28 16 16
32 32 56 56 74 74 74 56 56 32 32
Row n = 4 counts the following subsets:
{1,2} {1,3} {1,4} {2,4} {3,4}
{1,2,3} {1,2,3} {2,3} {1,2,4} {1,3,4}
{1,2,4} {1,3,4} {1,2,3} {2,3,4} {2,3,4}
{1,2,3,4} {1,2,3,4} {1,2,4} {1,2,3,4} {1,2,3,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
The case counting only length-2 subsets is
A008967.
Column k = n + 1 appears to be
A167762.
The version for all subsets (instead of just pairs) is
A365381.
A000009 counts subsets summing to n.
A046663 counts partitions with no submultiset summing to k, strict
A365663.
A365543 counts partitions with a submultiset summing to k, strict
A365661.
-
Table[Length[Select[Subsets[Range[n]], MemberQ[Total/@Subsets[#,{2}],k]&]], {n,2,11}, {k,3,2n-1}]
A367213
Number of integer partitions of n whose length (number of parts) is not equal to the sum of any submultiset.
Original entry on oeis.org
0, 0, 1, 1, 2, 2, 5, 4, 7, 8, 12, 13, 19, 21, 29, 33, 45, 49, 67, 73, 97, 108, 139, 152, 196, 217, 274, 303, 379, 420, 523, 579, 709, 786, 960, 1061, 1285, 1423, 1714, 1885, 2265, 2498, 2966, 3280, 3881, 4268, 5049, 5548, 6507, 7170, 8391, 9194, 10744, 11778, 13677
Offset: 0
The a(3) = 1 through a(9) = 8 partitions:
(3) (4) (5) (6) (7) (8) (9)
(3,1) (4,1) (3,3) (4,3) (4,4) (5,4)
(5,1) (6,1) (5,3) (6,3)
(2,2,2) (5,1,1) (7,1) (8,1)
(4,1,1) (4,2,2) (4,4,1)
(6,1,1) (5,2,2)
(5,1,1,1) (7,1,1)
(6,1,1,1)
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
-------------------------------------------
Triangles:
A046663 counts partitions of n without a subset-sum k, strict
A365663.
-
Table[Length[Select[IntegerPartitions[n], FreeQ[Total/@Subsets[#], Length[#]]&]], {n,0,10}]
A288728
Number of sum-free sets that can be created by adding n to all sum-free sets [1..n-1].
Original entry on oeis.org
1, 1, 3, 3, 7, 8, 18, 19, 47, 43, 102, 116, 238, 240, 553, 554, 1185, 1259, 2578, 2607, 5873, 5526, 11834, 12601, 24692, 24390, 53735, 52534, 107445, 107330, 218727, 215607, 461367, 427778, 891039, 910294, 1804606, 1706828, 3695418, 3411513, 7136850, 6892950
Offset: 1
1 can be added to {};
2 can be added to {} but not {1};
3 can be added to {},{1},{2};
4 can be added to {},{1},{3} but not {2},{1,3},{2,3}.
From _Gus Wiseman_, Aug 12 2023: (Start)
The a(1) = 1 through a(7) = 18 sum-free sets with maximum n:
{1} {2} {3} {4} {5} {6} {7}
{1,3} {1,4} {1,5} {1,6} {1,7}
{2,3} {3,4} {2,5} {2,6} {2,7}
{3,5} {4,6} {3,7}
{4,5} {5,6} {4,7}
{1,3,5} {1,4,6} {5,7}
{3,4,5} {2,5,6} {6,7}
{4,5,6} {1,3,7}
{1,4,7}
{1,5,7}
{2,3,7}
{2,6,7}
{3,5,7}
{4,5,7}
{4,6,7}
{5,6,7}
{1,3,5,7}
{4,5,6,7}
(End)
For non-binary sum-free subsets of {1..n} we have
A237667.
For sum-free partitions we have
A364345, without re-using parts
A236912.
The complement without re-using parts is
A364756, differences of
A088809.
-
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&Intersection[#,Total/@Tuples[#,2]]=={}&]],{n,10}] (* Gus Wiseman, Aug 12 2023 *)
A365380
Number of subsets of {1..n} that cannot be linearly combined using nonnegative coefficients to obtain n.
Original entry on oeis.org
1, 1, 2, 2, 6, 4, 16, 12, 32, 32, 104, 48, 256, 208, 448, 448, 1568, 896, 3840, 2368, 6912, 7680, 22912, 10752, 50688, 44800, 104448, 88064, 324096, 165888, 780288, 541696, 1458176, 1519616, 4044800, 2220032, 10838016, 8744960, 20250624, 16433152, 62267392, 34865152
Offset: 1
The set {4,5,6} cannot be linearly combined to obtain 7 so is counted under a(7), but we have 8 = 2*4 + 0*5 + 0*6, so it is not counted under a(8).
The a(1) = 1 through a(8) = 12 subsets:
{} {} {} {} {} {} {} {}
{2} {3} {2} {4} {2} {3}
{3} {5} {3} {5}
{4} {4,5} {4} {6}
{2,4} {5} {7}
{3,4} {6} {3,6}
{2,4} {3,7}
{2,6} {5,6}
{3,5} {5,7}
{3,6} {6,7}
{4,5} {3,6,7}
{4,6} {5,6,7}
{5,6}
{2,4,6}
{3,5,6}
{4,5,6}
A124506 appears to count combination-free subsets, differences of
A326083.
A365046 counts combination-full subsets, first differences of
A364914.
-
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-1]],combs[n,#]=={}&]],{n,5}]
A367215
Number of strict integer partitions of n whose length (number of parts) is not equal to the sum of any subset.
Original entry on oeis.org
0, 0, 1, 1, 2, 2, 2, 3, 3, 4, 5, 7, 8, 10, 12, 15, 18, 21, 25, 29, 34, 40, 46, 53, 62, 71, 82, 95, 109, 124, 143, 162, 185, 210, 240, 270, 308, 347, 393, 443, 500, 562, 634, 711, 798, 895, 1002, 1120, 1252, 1397, 1558, 1735, 1930, 2146, 2383, 2644, 2930, 3245
Offset: 0
The a(2) = 1 through a(11) = 7 strict partitions:
(2) (3) (4) (5) (6) (7) (8) (9) (10) (11)
(3,1) (4,1) (5,1) (4,3) (5,3) (5,4) (6,4) (6,5)
(6,1) (7,1) (6,3) (7,3) (7,4)
(8,1) (9,1) (8,3)
(5,4,1) (10,1)
(5,4,2)
(6,4,1)
The a(2) = 1 through a(15) = 15 strict partitions (A..F = 10..15):
2 3 4 5 6 7 8 9 A B C D E F
31 41 51 43 53 54 64 65 75 76 86 87
61 71 63 73 74 84 85 95 96
81 91 83 93 94 A4 A5
541 A1 B1 A3 B3 B4
542 642 C1 D1 C3
641 651 652 752 E1
741 742 761 654
751 842 762
841 851 852
941 861
6521 942
951
A41
7521
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.
A240861 counts strict partitions with length not a part, complement
A240855.
Triangles:
A365661 counts strict partitions with a subset-sum k, non-strict
A365543.
A365663 counts strict partitions without a subset-sum k, non-strict
A046663.
-
Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&FreeQ[Total/@Subsets[#], Length[#]]&]], {n,0,30}]
A367216
Number of subsets of {1..n} whose cardinality is equal to the sum of some subset.
Original entry on oeis.org
1, 2, 3, 5, 10, 20, 40, 82, 169, 348, 716, 1471, 3016, 6171, 12605, 25710, 52370, 106539, 216470, 439310, 890550, 1803415, 3648557, 7375141, 14896184, 30065129, 60639954, 122231740, 246239551, 495790161, 997747182, 2006969629, 4035274292, 8110185100, 16293958314, 32724456982
Offset: 0
The a(0) = 1 through a(4) = 10 subsets:
{} {} {} {} {}
{1} {1} {1} {1}
{1,2} {1,2} {1,2}
{2,3} {2,3}
{1,2,3} {2,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
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
-------------------------------------------
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A240855 counts strict partitions whose length is a part, complement
A240861.
Triangles:
A365541 counts sets containing two distinct elements summing to k.
-
Table[Length[Select[Subsets[Range[n]], MemberQ[Total/@Subsets[#], Length[#]]&]], {n,0,10}]
A367217
Number of subsets of {1..n} whose cardinality is not equal to the sum of any subset.
Original entry on oeis.org
0, 0, 1, 3, 6, 12, 24, 46, 87, 164, 308, 577, 1080, 2021, 3779, 7058, 13166, 24533, 45674, 84978, 158026, 293737, 545747, 1013467, 1881032, 3489303, 6468910, 11985988, 22195905, 41080751, 75994642, 140514019, 259693004, 479749492, 885910870, 1635281386
Offset: 0
The a(2) = 1 through a(5) = 12 subsets:
{2} {2} {2} {2}
{3} {3} {3}
{1,3} {4} {4}
{1,3} {5}
{1,4} {1,3}
{3,4} {1,4}
{1,5}
{3,4}
{3,5}
{4,5}
{1,4,5}
{2,4,5}
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
-------------------------------------------
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A229816 counts partitions whose length is not a part, complement
A002865.
A124506 appears to count combination-free subsets, differences of
A326083.
Triangles:
A046663 counts partitions of n without a subset-sum k, strict
A365663.
A365541 counts sets containing two distinct elements summing to k.
Cf.
A068911,
A103580,
A240861,
A288728,
A326080,
A326083,
A364346,
A364349,
A365046,
A365376,
A365377.
-
Table[Length[Select[Subsets[Range[n]], FreeQ[Total/@Subsets[#], Length[#]]&]], {n,0,15}]
A367222
Number of subsets of {1..n} whose cardinality can be written as a nonnegative linear combination of the elements.
Original entry on oeis.org
1, 2, 3, 6, 12, 24, 49, 101, 207, 422, 859, 1747, 3548, 7194, 14565, 29452, 59496, 120086, 242185, 488035, 982672, 1977166, 3975508, 7989147, 16047464, 32221270, 64674453, 129775774, 260337978, 522124197, 1046911594, 2098709858, 4206361369, 8429033614, 16887728757, 33829251009, 67755866536, 135687781793, 271693909435
Offset: 0
The set {1,2,4} has 3 = (2)+(1) or 3 = (1+1+1) so is counted under a(4).
The a(0) = 1 through a(4) = 12 subsets:
{} {} {} {} {}
{1} {1} {1} {1}
{1,2} {1,2} {1,2}
{1,3} {1,3}
{2,3} {1,4}
{1,2,3} {2,3}
{2,4}
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}
{1,2,3,4}
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:
A365541 counts subsets containing two distinct elements summing to k.
Cf.
A068911,
A088314,
A103580,
A116861,
A326080,
A364350,
A365073,
A365311,
A365376,
A365380,
A365544.
-
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}]
-
from itertools import combinations
from sympy.utilities.iterables import partitions
def A367222(n):
c, mlist = 1, []
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:
c += 1
break
return c # Chai Wah Wu, Nov 16 2023
Comments